В этом разделе мы научимся определять для заданного многочлена 
с коэффициентами из конечного поля P={0, 1, 2,... q - 1}, является ли этот многочлен неприводимым в поле P. Неприводимые многочлены используются для построения линейных сдвиговых регистров с обратной связью (см. раздел 3.1.6). Наш алгоритм основывается на следующей теореме.
Теорема. Пусть F – конечное поле, состоящее из q элементов. Тогда для любого натурального 
многочлен 
является произведением всех неприводимых над полем F многочленов степени k.
Из этой теоремы сразу следует, что для произвольного многочлена 
является произведением всех линейных сомножителей , 
является произведением всех квадратичных сомножителей и т.д. Поэтому, если 
=1 для 
, то является неприводимым многочленом. Наибольший общий делитель двух многочленов находят с помощью алгоритма Евклида, используя соотношение 
, где 
- остаток от деления 
на 
.
Упомянутый тест на неприводимость можно заменить более быстрым альтернативным тестом: многочлен 
над полем F= 
является неприводимым тогда и только тогда, когда 
, и 
для всех простых делителей k степени n.
Пример. Показать неразложимость многочлена 
над полем F2={0,1}.
В данном случае, n=3, q=2. Для вычисления 
поделим столбиком 
на и найдем остаток: 
. Остаток равен x. Простым делителям числа n=3 являются только k=1, поэтому остается только проверить, что 
. Для этого делим первый многочлен на второй и находим остаток 
. Теперь по алгоритму Евклида 
.
14. ρ-метод Полларда для дискретного логарифмирования — алгоритм дискретного логарифмирования в кольце вычетов по простому модулю, имеющий экспоненциальную сложность. Он был предложен Поллардом в 1978 году.
Постановка задачи
Для заданного простого числа p и двух целых чисел a и b требуется найти целое число x, удовлетворяющее сравнению: 
Идея алгоритма
Рассматриваются три числовые последовательности: 
определённые следующим образом: 
Замечание: везде рассматривается наименьшие неотрицательные вычеты.
Далее рассматриваются наборы 
и ищется номер i, для которого 
. Для такого i выполнено 
Если при этом 
, то 
Эвристическая оценка сложности составляет 
15. Методы факторизации целых чисел. ( ρ -1) – метод Полларда.
Факторизацией целого числа называется его разложение в
произведение простых сомножителей. Такое разложение, согласно основной
теореме арифметики, всегда существует и является единственным (с
точностью до порядка следования множителей). Задача факторизации является вычислительно сложной задачей. Однако никому пока не удалось получить высоких нижних оценок этого алгоритма.
Все методы факторизации в зависимости от их производительности можно разбить на две группы: экспоненциальные методы и субэкспоненциальные методы. Среди субэкспоненциальных алгоритмов следует выделить метод эллиптических кривых Ленстры, являющийся аналогом (ρ − 1)-метода Полларда. Последний имеет экспоненциальную оценку сходимости.
(ρ -1) – метод Полларда основан на Теореме Ферма:
Пусть n—факторизуемое число, а 1 < p < n– его простой делитель. Согласно теореме, для любого a, 1 ≤ a < p, выполняется условие ap−1 ≡ 1(mod p), если р – простое.
n = p*q, где p,q – нечётные простые числа =>
для любого а<p: ap-1 mod p = 1, aq-1 mod q = 1 =>
ap-1 = k*p, а (p-1) – чётное число.
НОД(ap-1-1,n) = p.
Предположим: p-1 = 2r^1 * 3r^2 *…*Br^t. Пусть B < B1 – грань для множества (p-1).
Вычисляем M(B1) = ∏ pir^i, pir^i < B1.
Выберем произвольное число a, например 2, и вычислим aM mod n.
Если НОД(n, aM−1) = d, 1<d<n, то задание выполнено.
Вторая стадия (ρ -1) – алгоритма Полларда.
Вторая стадия алгоритма предполагает, что существует только один
простой множитель q числа p − 1, значение которого больше границы B1.
Выбираем новую границу B2 ~ B12.
Обозначим через b число aM(B1) mod n, вычисленное на первой стадии работы алгоритма.
Выпишем последовательность q0 < q1 <... < qs всех простых чисел на интервале [B1; B2]. Если искомый множитель p−1 равен qi , то для нахождения делителя n, необходимо вычислить cо = bqо mod n, и найти d=НОД(n, со − 1). Если d = 1, то вычислим следующее ci. Каждое последующее значение ci+1 вычисляется по формуле bqi+1 mod n = bqi+δi mod n = bqi · bδi mod n = ci · bδi mod n, где δi = qi+1 − qi.
