8.1.Вычисление дискретного логарифма

Логарифм x по основанию a от целого числа y по mod n обозначается как

log _a y  = x  mod n.

Это такое целое число x, которое удовлетворяет уравнению

y  = a ^x  mod n.

В отличие от логарифмов вещественных и комплексных чисел, которые всегда можно найти хотя бы приближенно, дискретные логарифмы существуют не всегда. Так легко убедиться, что log ₃ 7  mod 17 не существует.

Операция логарифмирования является сложной, т.е. до сих пор не найден алгоритм, который позволил бы вычислить логарифм за число операций, полиномиально зависящее от числа разрядов аргумента. В настоящее время известный наилучший алгоритм требует для вычисления логарифма по mod n количество операций порядка exp .

8.2.Разложение на множители

Согласно основной теореме арифметики любое целое число n допускает однозначное разложение на простые множители:

,

где p_i – различные простые числа (т.е. числа, которые делятся без остатка только на 1 и на себя), _i – натуральные числа, i = 1, 2,…, s. Разложение чисел на простые множители более кратко называется факторизацией.

В настоящее время неизвестны простые алгоритмы факторизации. Наиболее быстрые алгоритмы требуют для факторизации целого числа n примерно столько же операций, сколько нужно для вычисления логарифма по mod n. Например, разложение на простые множители случайно выбранных натуральных чисел со ста десятичными разрядами по данным 1977 года требовало 74 года машинного времени, а для чисел со 125 десятичными разрядами по данным 1994 года та же оценка давала 10⁶ лет.

8.3.Вычисление наибольшего общего делителя

Наибольшим общим делителем (НОД) двух чисел u и v называется такое наибольшее целое число НОД(u, v), которое делит оба числа u и v.

Прямой метод нахождения наибольшего общего делителя (НОД) состоит в разложении чисел u и v на простые множители и выборе среди них всех общих множителей. Эта задача является сложной, поскольку требует для своего выполнения числа операций, экспоненциально зависящего от числа разрядов чисел u и v. Однако существует быстрый метод вычисления НОД. Он основан на алгоритме Евклида и состоит в следующем. Пусть, не умаляя общности, u > v > 0. Тогда производятся вычисления

u	= a1 v + b1		b1	= res v u	0  b1 < v
v	= a2 b1 + b2		b2	=  v	0  b2 < b1
b1	= a3 b2 + b3		b3	=  b1	0  b3 < b2
… bk – 2	… = ak bk – 1+ bk		… bk	… =  bk – 2	… 0  bk < bk – 1

до тех пор, пока не будет получено, что b_k = 0 или b_k = 1. Если b_k = 1, то НОД(u, v) = 1, т.е. u и v взаимно простые числа. Иначе, когда b_k = 0, имеем НОД(u, v) = b_k – 1 , т.е. b_k – 1 и дает решение задачи. Сложность данного алгоритма полиномиально зависит от числа разрядов u и v и требует 0 (log v) делений.