Лемма. Чтобы вычислить степень mn , где m – элемент некоторого кольца, а n – натуральное число, достаточно выполнить не более умножений.

требуется выполнить не более чем умножений. И не более чем r - 1 умножений потребуется для вычисления всех членов ряда (1.4). Поэтому общее число операций для решения уравнения (1.2) не превосходит

Теорема 3. Пусть G = < G; •, 1 > - конечная группа; а и b -элементы группы G; t = ord b; b^'= a. И пусть, кроме того, число t составное:

Тогда дискретный логарифм элемента а по основанию b можно вычислить, выполнив не более чем за операций.

Доказательство. Нетрудно заметить, что любое целое число l с условием однозначно представимо в виде:

Равенство b^l = а можно записать в виде

(1.6)

Возводя обе части равенства (1.6) в степень r₁ и замечая, что t =r₁ r₂ , получим

А это удобно записать в виде

(1.7)

где .Легко проверить, что ord b₁ = r₂. По теореме 2 дискретный логарифм a₁ по основанию b₁, т.е. m₁, можно вычислить при помощи не более чем операций. Из равенства (1.6) сразу получим

(1.8)

где

Аналогично, l₁ можно вычислить при помощи не более чем заопераций. Далее,можно вычислить соответственно не более чем за

операций. Отсюда и следует наше утверждение.

Замечание. Здесь и дальше при подсчете числа операций, необходимых для вычисления индекса элемента конечного поля, учитываем только число умножений в конечном поле и не принимаем во внимание любые логические операции и операции в поле рациональных чисел, если такие потребуется выполнять.

Теорема 4. Пусть сохраняются условия теоремы 3. Если r₁ ,r_2, r₃ - натуральные (>1) числа, ord b = t и t = r₁ .r₂. r₃ , то для вычисления индекса элемента а при основании b достаточно выполнить не более

операций.

Доказательство. Пусть, как в теореме 3 b^l = а , и пусть l₁, m₁ - целые, тогда

Полагаем

Имеем

Обозначим

Получим

Оценим количество операций, достаточное для выполнения всех промежуточных шагов. При этом воспользуемся теоремами 2,3 и леммой:

Итак, общее число операций равно

Теорема 5. Если - есть произведение натуральных чисел, то решение уравнения (1. 1) можно найти, выполнив не более чем операций. При этом величины

определяются условиями:

Доказательство. Чтобы оценить верхнюю границу числа операций, достаточную для отыскания индекса а при основании b, как и ранее, представим число l в виде:

где m₁ и l₁ -целые с условиями

Тогда получим

Так как Введем обозначения:

Поэтому имеем

Далее находим

Полагаем теперь Тогда получим

Оценив количество операций, достаточное для выполнения всех промежуточных шагов, и применив индуктивное предположение, получим объявленный результат. [2]

Вопрос 9 Дискретный корень

Пусть G — некоторая конечная группа. Для а N, x  G положим f_a(x)=x^a. Рассмотрим обратную функцию f_a^-1(x)=x^1/a — дискретный корень.

Вычисление дискретных корней в Z_p*, где р — простое, не представляет трудностей. В самом деле, x^p-1=1 по Малой теореме Ферма, следовательно, x^1/a=x^c, где aс 1 (mod p-1). Таким образом, в качестве односторонней функции имеет смысл использовать возведение в степень только по составному модулю.[1]