Теорема. Пусть и = 2FR + 1 жтое и F = qk1 .. .qk% F > R (2R, F) = 1 q , . . . , q ятность того, что случайно выбранное основание a £ Zn в лемме 1 будет доказывать простоту числа щвна (F)/F.

и an- =

= 1 (mod тся при всех a £ При (2R,F) = 1 условие a(n-1)/qj = 1 (mod и) всех j равносильно тому, что порядок элемента ется на лемму 3 при d = F получаем □

q1 , . . .

...,q личину

Так как F = qkk1 ... , то искомая оценка вытекает из неравенства

F = q s = 1 □

у. Маурер предложил следующий рекурсивный алгоритм построения больших простых чисел (впервые идея метода изложена им в 1991 г.). В нем на каждом шаге алгоритма берутся уже построенные на предыдущем этапе простые числа qi,qs и для случайного набора показателей ki,..., жтся число F = qkk1 ... qkks. Затем случайно подбираются числа x У R=R(x, y) < тобы (2F, R) = 1 и число и = 2FR + жотором a удовлетворяло условию лемм 1 или 2. По времени данный алгоритм оказывается очень эффек-и

ее следствия число жтро. Если же число и со-

an- = 1 (mod и)

нескольких баз сти только и не является числом Кармайкла, т.е. является числом очень специального вида. При этом, полученные в результате работы алгоритма простые числа будут иметь практически равномерное распределение. У. Маурер был фактически первым, кто предложил и обосновал использование случайного поиска вместе с достаточными условиями простоты, что позволило строить доказуемо простые числа.

12.5. Метод Михалеску

В 1994 г. П. Михалеску предложил еще более быстрый алгоритм генерации доказуемо простых чисел. По мнению Михалеску в методе Маурера потеря в эффективности происходит из-за усложненного механизма для построения простых чисел с «почти» равномерным распределением. Он предложил алгоритм поиска чисел в арифметиче-

и - 1

сивную процедуру. Кроме того, он оптимизировал процедуру отбраковки составных чисел, используя решето Эратофена и тест простоты Рабина-Миллера.

рядных чисел состоит в следующем. Пусть B > 0 - целое число и s,c> 0 - действительные константы. m < B m

пробных делений).

ла 2m < F < 2cm, факторизация которого полностью известна, где положить 1/2 1/3 в зависимости от применяемого достаточного условия простоты, см. леммы 1 или 2 в методе Маурера.

Шаг 3. Выбираем случайное число t £ (2m-2/F, 2m-1/F - sm).

Шаг 4. Ищем простое число в арифметической прогрессии

P = {и = no + ia: no = ta +1, a = 2F, 0 < i < s}.

Тест простоты, применяемый на шаге 4, выполняется в три этапа.

Этап 1. Пробные деления на простые числа, не превосходящие Л, где Л -заданная верхняя граница.

Этап 2. Проверка простоты с помощью теста Рабина-Миллера.

Этап 3. Доказательство простоты с помощью лемм 1 или 2 (см. метод Маурера).

B s c

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

12.6. (n + 1)-методы

Рассмотренные выше методы относятся к так называемым (n- 1)

(n - 1)

(n + 1)

(n + 1)

p q p2 - 4q

ным вычетом по модулю п. Тогда квадратное уравнение -рх + д = 0 имеет различные корни, один из которых равен г = (р + /р" - 4q)/2. Индукцией легко показать, что степени этого числа имеют специальный вид.

Лемма 1. Степени числаг имеют видr = {Vk+Ukp - 4q)/2, где последовательности {Uk } {V;;} определяются рекуррентными соотношениями

Uo =0, U1 = 1, Uk+2 = pUk+1 - qUk,

Vo =2, V1 = p, Vk+2 = pVk+1 - qVk, k 0

Данные последовательности называются последовательностями

позволяющих вычислять их аналогично методу повторного возведения в квадрат при возведении в степень, например,

U2k = Uk Vk, V2k = V2 - 2qk, k 0

(При p = 1 q = - мтельность {Uk} совпадает с последовательностью Фибоначчи.) Следующая лемма играет роль, аналогичную малой теореме Ферма.

Лемма 2. Пусть числа р, q и г определены выше и 2г = а + + Ьл/р2 - 4q (mod п) для некоторых чисел а и Ь одинаковой четности. Если п простое, то 2г" = а - Ьл/р2 - 4q (mod п). □

{ Uk }

Лемма 3. Еслг1 тое, то Un+1 = О (mod □ n>1

делителя r сла n +1 жие простые числа p и q, что

p2 - 4q n

Un+1 = О (mod n), U(n+1)/r = О (mod n), то ncmoe. □

Данная теорема играет роль, в точности аналогичную роли теоре-(n - 1)

{ Vk } ( n - 1)

n2 + 1 n2 ± n- 1

12.Т. Числа Мерсенна

Наиболее известным частным случаем этого подхода является следующий критерий простоты для чисел Мерсенна. Числами Мерсенна называются числа вида Mn = 2n - вде n - простое. Легко видеть, что число тетым только если n - простое.

тельность {Lm} определена рекуррентным образом

Lo =4, Lm+1 = Lm - 2, О < m<n

Число только то гда, когда Ln-2 = О (mod □ Критерий был первоначально открыт Люка в конце 1890-х гг., а данную краткую форму приобрел около 1930 г. в работах Лемера.

(n + 1) q = 2 k = 2m

Lm = V2k/2k

В таблице 1 приведен список всех известных в настоящее время p Mp

очередь число Pp = Mp(Mp - 1) является совершенным). Вопросительные знаки в таблице означают, что пока проверены не все числа, и поэтому неизвестно, являются ли они подряд идущими простыми числами Мерсенна.

Последние пять простых чисел были найдены в рамках программы широкомасштабного поиска, организованного с 1995 г. в сети Интернет - GIMPS (the Great Internet Mersenne Prime Search) Г. "Уолма-hom, написавшим быструю программу для персонального компьютера и разместившим ее на своем web-сервере. Он организовал также распределенную базу данных, в которой отражался ход поиска. В 1997 г. компание Entropia, Inc., основанной С.Куровски, была организована система поддержки распределенных вычислений PrimeNet, которая в настоящее время координирует работу нескольких сотен тысяч компьютеров. (В последнем столбце таблицы 1 в скобках указано число компьютеров, принимавших участие в поиске.)

§ 13. Алгоритмы факторизации целых чисел

разложения его в произведение простых сомножителей. Тривиальный алгоритм, часто называемый алгоритмом «пробных делений».

Таблица 1. Известные числа Мерсенна

простые числа, не превосходящие -\/п. При выполнении данного алгоритма возникает две трудности. С одной стороны, для больших чисел и

оказаться настолько большим, что его просто невозможно выполнить. С другой стороны, необходимо заранее строить список всех простых чисел, не превосходящих -\/п, что уже само по себе является трудной задачей. Второй трудности можно легко избежать, если осуществлять деления числа на все целые числа k, не превосхо-

дящие -\/п. Это избавит от необходимости строить исходный список простых чисел, причем сложность такого алгоритма увеличится не более, чем в 0(log и) раз.

для данного алгоритма оценивается величиной

0(7г(у) log2 п) =0(vlogn)

для деления на простые числа, и

©(vlogn)

для деления на подряд идущие целые числа.

Заметим, что при анализе алгоритмов факторизации часто ограничиваются рассмотрением только первого шага-нахождения первого нетривиального делителя. Легко видеть, что для нахождения полной и

log2 и

Хотя применение алгоритма «пробных делений» в полном объеме и

рокое применение в своем «сокращенном» варианте, когда пробные деления осуществляются только на все простые числа, не превосходящие некоторой константы С