Представление кольца вычетов в виде прямой суммы

Пусть числа — попарно взаимно простые, и Тогда система.

имеет единственное решение среди чисел, и это решение может быть представлено в одном из следующих видов: 1. либо.

и обозначающем число, обратное числу относительно умножения по модулю :

2. либо и числах последовательно определяемых из сравнений.

Задача логарифмирования в конечном поле как математически трудная задача

Пусть в некоторой конечной мультипликативной абелевой группе задано уравнение.

Решение задачи дискретного логарифмирования состоит в нахождении некоторого целого неотрицательного числа, удовлетворяющего уравнению (1). Если оно разрешимо, у него должно быть хотя бы одно натуральное решение, не превышающее порядок группы. Это сразу даёт грубую оценку сложности алгоритма поиска решений сверху — алгоритм полного перебора нашел бы решение за число шагов не выше порядка данной группы.

Чаще всего рассматривается случай, когда, то есть группа является циклической, порождённой элементом. В этом случае уравнение всегда имеет решение. В случае же произвольной группы вопрос о разрешимости задачи дискретного логарифмирования, то есть вопрос о существовании решений уравнения (1), требует отдельного рассмотрения.

В произвольном конечном поле Задача рассматривается в поле GF (q), где , — простое.

1. Алгоритм исчисления индексов (index-calculus) эффективен, если невелико. В этом случае он имеет эвристическую оценку сложности .

• 2. Алгоритм Эль-Гамаля, появившийся в 1985 году, применим при и имеет сложность арифметических операций.
• 3. Алгоритм Копперсмита дискретного логарифмирования в конечном поле характеристики 2 стал первым субэкспоненциальным алгоритмом дискретного логарифмирования с константой в оценке сложности. Данный алгоритм появился в 1984 году — до изобретения решета числового поля.

Задача дискретного логарифмирования является одной из основных задач, на которых базируется криптография с открытым ключом. Классическими криптографическими схемами на её основе являются схема выработки общего ключаДиффи-Хеллмана, схема электронной подписи Эль-Гамаля, криптосистема Мэсси-Омуры для передачи сообщений. Их криптостойкость основывается на предположительно высокой вычислительной сложности обращения показательной функции. Последняя вычисляется достаточно эффективно, в то время как даже самые современные алгоритмы вычисления дискретного логарифма имеют очень высокую сложность, которая сравнима со сложностью наиболее быстрых алгоритмов разложения чисел на множители.

Другая возможность эффективного решения задачи вычисления дискретного логарифма связана с квантовыми вычислениями. Теоретически доказано, что с их помощью дискретный логарифм можно вычислить за полиномиальное время[2]. В любом случае, если полиномиальный алгоритм вычисления дискретного логарифма будет реализован, это будет означать практическую непригодность криптосистем на его основе.