Факторизация. Логарифмирование в конечных полях.

Факторизация числа означает нахождение его простых множителей.
Пример 1. 
10 = 2  5,
60 = 2  2  3  5,
252601 = 41  61  101,
- 1 = 3391  23279  65933  1868569  1066818131868207.
Проблема факторизации – одна из старейших в теории чисел. Сложность самого быстрого алгоритма факторизации [Schn96]:

Пусть (n) – число простых чисел  n.
Теорема. (Чебышева о числе простых чисел [Massey 94]).
.
Все современные тесты на простоту основаны на обобщениях теоремы Ферма.
Если  имеет порядок N ((modp)) в мультипликативной группе поля GF(p), что предполагает, что  - различны, и . Тогда i называется дискретным логарифмом от  по основанию   и обозначается .

при этом:
(1)	вычислять экспоненту легко: требуется не более  операций в алгоритме быстрого возведения в степень;
(2)	вычисление дискретного логарифма в GF(p) является очень сложной задачей, когда р-1 имеет большой простой множитель.
Для вычисления  в GF(p), когда  имеет мультипликативный порядок N ((modp)), используют алгоритм Shank [Massey 94]. Выбирается некоторое целое d , где . 
Тогда  x = Qd + r,  0   r   и 
.
Далее все вычисления ведутся в GF(p).
1.	Для  = 0, 1, … , d-1 вычисляем  а = aa и запоминаем  - это все логарифмы    такие, что 
2.	Составляем таблицу (,) для 0   d – таблицу малых логарифмов.
3.	Вычисляем  с помощью алгоритма быстрого возведения в степень.
Заметим, что

и, следовательно,
.
4.	Для q = 0, 1, 2, … вычисляем  до тех пор, пока  не станет равным некоторому  в таблице. 
5.	Тогда .
Сложность алгоритма имеет порядок  операций умножения и память .
Пример 2.  Найдем  здесь 5- примитивный элемент GF(23), и  N = 22 (522 = 1(mod23)) .
(0)	d = 5
(1)	
      
(2) 
		
1
2
4
5
10	0
2
4
1
3	
(3) 
       
 (4) y = 13 не принадлежит входу в таблице (q = 0).

Следовательно,
      .
 = 14
и для его нахождения требуется 5 операций умножения.
Проблема дискретного логарифмирования упрощается, если основание логарифма  имеет порядок N и  и сводится к дискретному логарифмированию по основанию, имеющему порядок , и  дискретному логарифмированию по основанию, имеющему порядок  .
Алгоритм [Massey 94] нахождения дискретного логарифма, когда основание логарифма  имеет порядок N и  приведен ниже. Пусть
.
(0)	Вычисляем  с помощью алгоритма быстрого возведения в степень.
(1)	Вычисляем  с помощью алгоритма быстрого возведения в степень.
(2)	Находим . 
(3)	Вычисляем  с помощью алгоритма быстрого возведения в степень.
(4)	Вычисляем .
(5)	Вычисляем  с помощью алгоритма быстрого возведения в степень.
(6)	Находим .
(7)	Получаем  x = xN + x.