Алгоритм нахождения простых чисел. Алгоритмы, используемые при реализации асимметричных криптосхем

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

Требования к алгоритму и его реализации

Требования к алгоритмам генерации случайных простых чисел сводятся к следующим двум:

• Распределение получаемых простых чисел должно быть близко к равномерному на множестве всех k -битных простых чисел. Существует несколько способов обеспечить выполнимость этого требования.
• Процесс генерации конкретного случайного простого числа нельзя воспроизвести, даже зная детали алгоритма и его реализации. Обычно выполнение этого требования обеспечивается использованием криптостойкого ГПСЧ , проинициализированного некоторым ключом , получаемым извне (т. е. не являющимся частью алгоритма или его реализации). В качестве ключа может выступать, например, значение криптографической хеш-функции от секретной фразы, запрашиваемой у пользователя.

Типовые алгоритмы генерации случайных простых чисел

Везде далее предполагается использование криптографически стойкого ГПСЧ , проинициализированного с помощью секретного ключа (детали зависят от используемого ГПСЧ и способа получения и представления ключа).

Тестирование простоты

Проверить (вероятную) простоту числа p , содержащего k битов, можно так:

1. Убедиться, что p не делится на небольшие простые числа 3, 5, 7, 11, и т.д. до некоторого небольшого предела (например, 256). Такая проверка позволяет эффективно отсечь множество заведомо составных чисел, прежде чем проверять их посредством более трудоёмких алгоритмов. Так, проверка делимости p на простые числа 2, 3, 5 и 7 отсеивает все четные числа и 54% нечетных чисел, проверка делимости p на все простые числа до 100 отсеивает 76% нечетных чисел, а проверка делимости p на все простые числа до 256 отсеивает 80% нечетных чисел.
2. Выполнить тест Миллера - Рабина с количеством раундов не меньше k .

Если число p не проходит хотя бы одной проверки - оно не является простым. В противном случае с большой вероятностью (зависящей от количества раундов) число p является простым.

Прямое построение

Второй шаг можно ускорить, если рассматривать только нечетные числа или числа сравнимые с 1 и 5 по модулю 6 и т.п.

(n -1)-методы

(n -1)-методы построения простых чисел используют знание о простых делителях числа n -1 для тестирования простоты n с помощью

Тест Миллера-Рабина:

Вход: n=2sr+1 – нечетное число, проверяемое на простоту, s≥0, r – нечетное. t - количество итераций, параметр надежности.

1. Повторить t раз следующие шаги:

1.1. Случайным образом выбрать a {2,…, n-2};

1.2. Построить последовательность b0, b1,…,bs, по правилу:

b0=ar mod n, bj=(bj-1)2 mod n, j=1,2,…,s.

1.3. Если в построенной последовательности не встретилась

«1», то идти на Выход с сообщением «n - составное».

1.4. Если перед первой единицей в последовательности стоит не

«-1», то идти на Выход с сообщением «n - составное».

2. Идти на Выход с сообщением «n – простое с вероятностью εt ».

Обратим внимание на то, что в последовательности b 0,b 1,…,bs каждый последующий член является квадратом предыдущего по модулю n , а последний член есть ни что иное как an -1 mod n .

Вероятность ошибки теста на одной итерации составляет ε≤φ(n )/4n , то есть верхняя граница ошибки на одной итерации для теста Миллера-Рабина в 2 раза меньше аналогичной для теста Соловея-Штрассена и в 4 раза – для теста Ферма.

Пример использования теста Миллера-Рабина:

n =65=64+1=26+1. r =1, s =6. t =5.

1. 1-я итерация:

1.1. a =8.

1.2. Составляем последовательность: b0=8, b1=64=-1, b2=1,

b3=1, b4=1, b5=1, b6=1.

1.3. В последовательности встретилась «1».

1.4. Перед первой единицей стоит «-1».

1. 2-я итерация:

1.1. a =11.

1.2. Составляем последовательность: b0=11, b1=56, b2=16,

b3=61, b4=16, b5=61, b6=16.

1.3. В последовательности не встретилась «1».

Выход: « n - составное число».

Задания к разделу 2

1) Реализовать процедуру генерации простых чисел методом случайного поиска среди 128-битных чисел, старший бит которых равен 1 и проверки

а) тестом Ферма

б) тестом Соловея-Штрассена

в) тестом Миллера-Рабина.

Количество итераций вероятностного теста должно быть таково, чтобы вероятность ошибки не превышала 0,1. Вероятность ошибки определяется исходя из оценки ε для теста. Количество итераций для теста Ферма задать равным 50.

2) Получить с помощью этой процедуры 10 простых чисел. Для каждого эксперимента найти количество перебранных чисел до получения простого. Результаты оформить в виде таблицы.

Здесь №-номер эксперимента, p – найденное простое число, n – количество перебранных чисел до получения простого.

Данные для самопроверки к разделу 2

Данными следует пользоваться следующим образом:

· Задать значение параметра надежности теста t =1.

· Подставить в качестве входного параметра n число из колонки «Числа для проверки».

· Несколько (10-20) раз «прогнать» программу с заданными входными параметрами.

· Выводы о корректности реализованного теста следует делать на основании сравнения результата теста с данными из таблицы (колонка «Результат теста»).

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

Подход к получению доказуемо простых чисел отличается от подхода, рассмотренного ранее. Для построения таких чисел не используется случайный поиск. С использованием таблицы простых чисел небольшого размера, построенной заранее, строится число m (равное произведению нескольких простых чисел либо произведению простых чисел и случайного числа), затем число n =2m +1 проверяется на простоту одним из нижеприведенных тестов. Достоинством такого подхода является не только получение гарантированно простого числа n , но также получение порождающего элемента группы Z n *. Поэтому доказуемо простые числа, как правило, используются в качестве модулей криптосистем, основанных на проблеме дискретного логарифмирования, таких как шифр Шамира, криптосистема Эль-Гамаля и связанные с ней стандарты цифровой подписи ГОСТ Р 34.11-94, ГОСТ Р 34.11-2001, DSA и EСDSA.

3.1. Тест Миллера на простоту

Тест Миллера основан на теореме Сэлфриджа.

Алгоритм построения простого числа с помощью теста Миллера следующий:

q i

2. Строится число m =(где qi-различные случайные простые числа из таблицы, αi – случайные целые числа), размер которого на 1 бит меньше требуемого размера для простого числа;

3. Вычисляется значение n =2m +1;

4. Построенное число n испытывается тестом Миллера с заданным параметром надежности. Если результат проверки отрицательный, то следует вернуться на шаг 2 и построить новое число m .

Тест Миллера:

Вход: n – число для проверки, n -1=https://pandia.ru/text/78/045/images/image051_14.gif" width="44" height="43">mod n . Если какой-либо из результатов не равен единице, то идти на шаг 3, взять следующее qi . Если все результаты равны «1», то идти на Выход с сообщением «вероятно, n – составное число».

4. Идти на Выход с сообщением «n – простое число».

Если число n было предварительно проверено на простоту вероятностным тестом Миллера-Рабина, то в тесте Миллера достаточно перебрать 4-6 значений aj .

Если n – нечетное простое число, то вероятность того, что n по случайно выбранному основанию 1< a < n пройдет проверку на шаге 3.1, есть j(n-1)/(n-1).

3.2. Тест Поклингтона

Тест Поклингтона основан на теореме Поклингтона и позволяет проверять простоту числа n , если каноническое разложение числа (n -1) известно лишь частично.

Алгоритм построения простого числа с помощью теста Поклингтона следующий:

1. Строится таблица малых простых чисел q i (или используется готовая таблица);

2..gif" width="104" height="32"> - каноническое разложение; t – параметр надежности.

1. Выбрать t различных целых случайных чисел aj : 1< aj < n .

2. Для каждого aj вычислить (ajn -1 mod n . Если какой-либо из результатов не равен «1», то идти на Выход с сообщением «n – составное число».

3. Для каждого ai выполнить:

3.1. Для каждого qj вычислить () mod n . Если какой-либо из результатов равен единице, то идти на шаг 3, взять следующее ai . Если все результаты не равны «1», то идти на Выход с сообщением «n – простое число».

4. Идти на Выход с сообщением «вероятно, n – составное число».

Если n = RF+1 – нечетное простое число, F>https://pandia.ru/text/78/045/images/image055_12.gif" width="99" height="29">, НОД(R, F)=1, то вероятность того, что случайно выбранное 1< a < n будет удовлетворять условиям теоремы Поклингтона, есть https://pandia.ru/text/78/045/images/image057_10.gif" width="28" height="27 src=">-1<63.

n - 1=4020=22·3·5·67. F=67, R=22·3·5=60.

Проверка условий:

a = 2.

1) 24020 mod 4021=1.

2)24020/67 mod 4021 =260 mod 4021=1452.

Выход: n = 4021 – простое число.

(Заметим, что вероятность того, что наугад выбранное a будет удовлетворять условиям теоремы Поклингтона для данного примера, есть (1-1/67)≈0,985).

3.3. Процедура генерации простых чисел ГОСТ Р 34.10-94

В отечественном стандарте на цифровую подпись ГОСТ Р34.10-94 рекомендована процедура генерации доказуемо простых чисел заданного размера. ГОСТ Р 34.10-2001 также предписывает использование этой процедуры. Данная процедура основана на теореме Диемитко.

Теорема Диемитко

Пусть n = qR + 1, где q – простое число, R – четное, R <4(q +1).

Если найдется a < n : 1) an -1≡1(mod n ); 2) 1(mod n ), то n – простое число.

Итак, если имеем простое число q , то, перебирая четные числа R , строим числа n = qR + 1 и испытываем их на простоту согласно теореме Диемитко, пока не получим простое число. По полученному числу можно построить еще одно простое число и т. д., пока не будет достигнут требуемый размер числа.

Приведем алгоритм перехода от меньшего простого числа q : |q |= к большему p : |p |=t , использующийся в ГОСТе. Фигурирующая в процедуре ξ есть равномерно распределенная на (0,1) случайная величина, получаемая с помощью линейного конгруэнтного генератора. Каждый раз на шаге 1 получают новое значение ξ.

Алгоритм перехода от меньшего простого числа к большему:

Вход: t – требуемая размерность простого числа, q – простое число: |q |=.

1..gif" width="15 height=20" height="20">1(mod p ), то идем на Выход.

6. Вычисляем u = u +2. Возвращаемся на шаг 3.

Выход: p – простое число.

Первое слагаемое в построении числа N на шаге 1 обеспечивает минимальный требуемый размер числа p , а второе вносит в процедуру поиска новых простых чисел необходимый элемент случайности.

Проверка на шаге 4 необходима, чтобы число p не превышало своей верхней границы, а проверка на Шаге 5 есть проверка условия теоремы Диемитко при a =2.

Пример

Вход: t= 4, q= 3=2

1. N=0 " style="margin-left:-101.3pt;border-collapse:collapse;border:none">

Результат проверки вероятностным тестом

Здесь № - номер эксперимента, p – построенное простое число, в третьей строке результат проверки построенного числа вероятностным тестом (+ или -), k – количество отвергнутых чисел, определенных вероятностным тестом как простые.

Количество итераций вероятностного теста должно быть таково, чтобы вероятность ошибки не превышала 0,1.

Данные для самопроверки к разделу 3

Для тестов Миллера и Поклингтона

1) реализованный тест следует проверить таблицей составных чисел. В качестве входных параметров реализованного теста следует подставить числа из колонки «Числа для проверки» если в результате тест выдаст сообщение о том, что данное число отвергается, то следует перейти к следующему этапу проверки. Если хотя бы одно из этих чисел опознается тестом как простое, то тест реализован с ошибками.

2) Затем следует воспользоваться таблицами согласно реализованному тесту. Для проверки этими таблицами следует подставить в качестве входных параметров данные из таблиц (для теста Миллера проверяемое простое число p и каноническое разложение числа (p -1), для теста Поклингтона – проверяемое простое число p , число R и каноническое разложение числа F). Установить количество итераций теста t =1. Проверить число p этим тестом несколько раз (30-100). Затем рассчитать частоту события, когда проверяемое простое число будет принято за составное, и сравнить это значение с данными из колонки «Вероятность ошибки». Если эти данные приблизительно равны рассчитанному значению частоты, то тест реализован верно.

Для процедуры генерации чисел ГОСТ 31.10-94

Для проверки лабораторной работы следует выставить параметр ξ = 0 (то есть избавиться от случайности). Затем следует подставить в качестве входных параметров данные из таблицы (q и t ). Результат должен совпадать со значением из колонки «Построенное число».

Таблица составных чисел

Другим примером является выработка простых чисел p и q для получения модуля n =pq в RSA. В этом случае простые числа должны быть больших размеров и случайными в том смысле, что вероятность выбора любого конкретного простого числа должна быть достаточно малой для того, чтобы не дать злоумышленнику возможность использовать эту вероятность для оптимизации стратегии поиска . Иногда к простым числам могут предъявляться дополнительные требования для того, чтобы они были устойчивы к каким-либо специализированным атакам. Третий пример – выработка неприводимого многочлена f(x) степени m над конечным полем для построения конечного поля . В этом случае также необходима выработка элемента высокого порядка в .

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

Подходы к генерации больших простых чисел

Самым естественным методом является генерация случайного числа n необходимого размера и проверка его на простоту. Это можно сделать, проверяя, является ли какое-нибудь число от 2 до делителем n . На практике требуются более эффективные методы, но общая идея выглядит следующим образом.

1. Генерация случайного числа n необходимого размера, называемого кандидат.

2. Проверка числа n на простоту.

3. Если n – составное, вернуться на первый шаг.

Небольшой модификацией является выбор кандидатов из некоторой последовательности, начинающейся с n . Такой последовательностью является, например, n, n+2, n+4, n+6, … Использование специальных последовательностей позволяет увеличить вероятность того, что кандидат будет простым числом, а также находить простые числа, удовлетворяющие специальным требованиям.

На втором шаге может быть использован тест, однозначно определяющий, если кандидат – простое число (детерминированные тесты) или тест, устанавливающий более слабое утверждение, а именно то, что n – вероятно простое (вероятностные тесты). В последнем случае нужно очень аккуратно относиться к определению. Большинство вероятностных тестов на простоту однозначно определяет, если n – составное, но не обеспечивает математического доказательства простоты числа n , когда оно определяется вероятно простым. Тесты на простоту, которые позволяют однозначно определить, является ли n простым, используются крайне редко, поскольку обычно они требуют гораздо больших вычислительных ресурсов.

Последним различием между различными техниками генерации больших простых чисел является использование «случайности». Обычно кандидаты генерируются как функции от случайных входных данных. Техника для определения простоты числа может использовать или не использовать случайные числа. В некоторых случаях необходимо, чтобы простое число имело дополнительные свойства. К примеру, чтобы сделать извлечение дискретного логарифма стойким к алгоритму Полига-Хеллмана требуется , чтобы p-1 имело большой простой делитель. Поэтому техники для генерации параметров открытых ключей, таких как простые числа специальной формы, должны это учитывать .

Вероятностные тесты на простоту

Далее будут рассмотрены два вероятностных теста на простоту : Соловея-Штрассена (Solovay-Strassen) и Миллера-Рабина (Miller-Rabin). По историческим причинам также представлен тест Ферма (Fermat), однако его нельзя назвать вероятностным тестом на простоту, поскольку он не различает простые числа и особые составные числа, именуемые числами Кармайкла (Carmichael numbers) .

Тест Ферма (Fermat test)

Теорема Ферма утверждает, что если n – простое число и a – любое целое число, тогда . Потому если n – целое число, чья простота под вопросом, нахождение такого a в этом интервале, что это равенство не выполняется, докажет, что n – составное.

И наоборот, если найти целое число a , такое что , утверждается, что n – простое, в том смысле, что оно удовлетворяет теореме Ферма для основания a . Отсюда вытекает следующее определение. Составное n такое, что называется псевдопростым по основанию a . Примером такого числа является число 341 (11 х 31) – оно псевдопростое по основанию 2, поскольку .

Тест Ферма

Выход : Ответ на вопрос является n простым или составным (n – составное или n –простое).

1. В цикле i от 1 до t выполнить: 1.1 Выбрать случайное a : . 1.2 Вычислить . 1.3 Если , тогда вернуть («n – составное»). 2. Вернуть («n – простое»).

Если алгоритм утверждает, что n – составное, то оно однозначно составное. С другой стороны, если алгоритм утверждает, что n – простое, нет никаких гарантий того, что n – действительно простое. Однако, поскольку для заданного основания a псевдопростых чисел не так много, тест Ферма выдает правильный результат на большинстве входных значений, но не на всех .

Составные числа n , удовлетворяющие этому сравнению называются псевдопростыми Эйлера-Якоби (Euler–Jacobi pseudoprime) по основанию a .

Алгоритм Соловея - Штрассена параметризуется количеством раундов k . В каждом раунде случайным образом выбирается число a < n . Если НОД(a,n) > 1 , то выносится решение, что n составное. Иначе проверяется справедливость сравнения . Если оно не выполняется, то выносится решение, что n - составное. Если это сравнение выполняется, то a является свидетелем простоты числа n . Далее выбирается другое случайное a , и процедура повторяется. После нахождения k свидетелей простоты в k раундах выносится заключение, что n является простым числом с вероятностью .

Тест Соловея-Штрассена

Вход: n > 2, тестируемое нечётное натуральное число;

k - параметр, определяющий точность теста.

Выход : составное, означает, что n точно составное;

n вероятно является простым.

1.В цикле i от 1 до k выполнить: 1.1. Выбрать a - случайное целое от 2 до n-1 , включительно; 1.2. Если НОД(a, n) > 1, тогда вернуть (составное); 1.3.Если , тогда вернуть (составное). 2.Вернуть (простое с вероятностью ).

Тест Миллера-Рабина (Miller-Rabin test)

Тест Миллера - Рабина - вероятностный полиномиальный тест простоты. Тест Миллера - Рабина позволяет эффективно определять, является ли данное число составным. Однако, с его помощью нельзя строго доказать простоту числа. Тем не менее, тест Миллера - Рабина часто используется в криптографии для получения больших случайных простых чисел.

Алгоритм был разработан Гари Миллером (Gary Miller) в 1976 году и модифицирован Майклом Рабином (Michael Rabin) в 1980 году.

Пусть n - нечётное число большее 1. Число n-1 однозначно представляется в виде , где t нечётно. Целое число a , 1 < a < n , называется свидетелем простоты числа n , если выполняется одно из условий:

Существует целое число k , такое, что .

Теорема Рабина утверждает, что составное нечётное число n имеет не более различных свидетелей простоты, где - функция Эйлера (Euler"s phi function) .

Тест Миллера-Рабина

Алгоритм Миллера - Рабина параметризуется количеством раундов r . Рекомендуется брать r порядка величины , где n - проверяемое число.

Для данного n находятся такие целое число s и целое нечётное число t , что . Выбирается случайное число a , 1 < a < n . Если a не является свидетелем простоты числа n , то выдается ответ «m - составное», и алгоритм завершается. Иначе, выбирается новое случайное число a , и процедура проверки повторяется. После нахождения r свидетелей простоты выдается ответ «n - вероятно простое», и алгоритм завершается.

Вход : n > 2, нечётное натуральное число, которое необходимо проверить на простоту;

r - количество раундов.

Выход : составное, означает, что n является составным числом;

вероятно простое, означает, что n с высокой вероятностью является простым числом.

1. Представить n − 1 в виде , где t нечётно, можно сделать последовательным делением n - 1 на 2. 2. В цикле по i от 1 до r выполнить: 2.1. Выбрать случайное целое число a в отрезке . 2.2. , вычисляется с помощью алгоритма возведения в степень по модулю. 2.3. Если x = 1 или x = m − 1 , то перейти на следующую итерацию цикла 2. 2.4. В цикле по j от 1 до s − 1 выполнить: 2.4.1. . 2.4.2. Если x = 1, то вернуть (составное). 2.4.3. Если x = m − 1 , то перейти на следующую итерацию цикла 2. 2.5. Вернуть (составное). 3. Вернуть (вероятно простое).

Из теоремы Рабина следует, что если r случайно выбранных чисел оказались свидетелями простоты числа n , то вероятность того, что n составное, не превосходит .

Детерминированные тесты на простоту

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

Проверка чисел Мерсенна (Mersenne primes)

Существуют эффективные алгоритмы для проверки простоты некоторых особых классов чисел, таких как числа Мерсенна и числа Ферма . Особенно важными считаются именно числа Мерсенна , поскольку для них сложение в поле может быть произведено очень эффективно.

Этот факт приводит нас к детерминированному алгоритму проверки простоты числа Мерсенна за полиномиальное время.

Тест Люка-Лемера (Lucas–Lehmer primality test)

Выход : простое или составное.

1. Проверить наличие делителей у s в промежутке от 2 до ; 2. Если найден хоть один, то вернуть (составное); 3. Установить u = 4 ; 4. В цикле по k от 1 до s-2 выполнить ; 5.Если u = 0 вернуть (простое), в противном случае вернуть (составное).

На сентябрь 2013 года самым большим известным простым числом является число Мерсенна , найденное 25 января 2013 года Кертисом Купером (Curtis Cooper) в рамках проекта распределённых вычислений GIMPS . Десятичная запись числа n содержит 17 425 170 цифр.

Всего известно 48 простых чисел Мерсенна, причём порядковые номера с уверенностью установлены только у первых 42-х. Интересно отметить, что 46-е найденное простое число Мерсенна было найдено на две недели позднее 45-го найденного простого числа Мерсенна и оказалось меньше его.

Также существуют тесты на простоту, использующие факторизацию числа n-1 , эллиптические кривые , и другие, однако они довольно громоздки и потому не будут рассматриваться здесь.

Генерация простых чисел

В этом подразделе будут рассмотрены алгоритмы генерации простых чисел для криптографических целей.

Случайный поиск вероятно простых чисел

Как уже отмечалось выше, простейшим способом является случайный выбор числа необходимого размера и проверка его вероятностным тестом на простоту, например, тестом Миллера-Рабина. Однако, если кандидат n делится на малое простое число, проверка делимости на небольшие простые числа позволит отбросить не прошедшего кандидата n быстрее, чем по алгоритму Миллера-Рабина. Поскольку вероятность того, что случайное целое число имеет небольшой простой делитель, достаточно высока, до применения теста Миллера-Рабина стоит проверить n на простые делители до некоторой границы B . Это можно сделать последовательным делением n на все простые числа, меньше B или вычислением НОД n и произведения нескольких простых чисел, меньших B .

Случайный поиск простого числа с использованием теста Миллера-Рабина.

Вход : целое число k , параметр безопасности t .

Выход : случайное вероятно простое целое число длиной k бит.

1. Сгенерировать случайное число n длиной k бит; 2. Использовать деление n на простые числа, меньше B для проверки существования простого делителя; 3. Если хотя бы один найден – вернуться на шаг 1; 4. Проверить простоту n тестом Миллера-Рабина; 5. Если n – вероятно простое, то вернуть (n ), в противном случае вернуться на шаг 1.

Генерация сильно простых чисел

Вход : целое число l в интервале от 0 до 8.

Выход : 160-битное простое число q , L -битное простое число p , где L=512+64l и q|(p-1)

1. Вычислить L = 512+64l . Найти n , b : L-1 = 160n+b , где b в интервале от 0 до 159; 2. В цикле выполнить следующее: 2.1. Выбрать случайное число s (не обязательно хранить его в секрете) длины g больше или равной 160; 2.2. Вычислить ; 2.3. Сформировать q , установив самый старший и самый младший биты U в 1; 2.4. Проверить q на простоту тестом Миллера-Рабина с параметром t > 17; 2.5. Если q – составное, то вернуться на шаг 2; 3. Установить i =0, j =2; 4. В цикле пока i < 4096 выполнить: 4.1. В цикле для k от 0 до n выполнить: Установить ; 4.2. Для целого числа , определить ; 4.3. Вычислить и установить p = X – (c-1); 4.4. Если тогда выполнить: 4.4.1. Проверить p на простоту тестом Миллер-Рабина для параметра t > 4; 4.4.2. Если p – вероятно простое, вернуть (q,p ); 4.5. Установить i=i+1 , j=j+n+1 ; 5. Вернуться на шаг 2.

Конструктивные техники для простых чисел

Алгоритм Морера (Maurer’s algorithm) генерирует случайные однозначно простые числа, которые почти равномерно распределены над множеством всех простых чисел необходимого размера. Ожидаемое время генерации немногим больше, чем генерация вероятно простого числа алгоритмом случайного поиска простого числа с параметром t =1 .

Пусть n > 2 – целое число и предположим, что n=1+2Rq , где q – простое и q > R .

1. Если существует целое число a : и , то n – простое.

2. Если n – простое, вероятность, что случайно выбранное число a удовлетворяет условиям и , равна .

Алгоритм Морера рекурсивно генерирует простое число q и затем выбирает целые числа R < q , пока не будет доказано по первому пункту вышеописанной теоремы, что n=1+2Rq – простое по некоторому основанию a .

Алгоритм Морера

Вход : положительное целое число k .

Выход : простое число n длины k бит.

1. Если k < 21 тогда в цикле выполнить: 1.1. Выбрать случайное целое число n длины k бит; 1.2. Последовательно поделить n на все простые числа от 2 до ; 1.3. Если нашелся хоть один делитель, вернуться на шаг 1, в противном случае вернуть (n ); 2. Установить c = 0.1, m = 20; 3. Установить ; 4. Если k > 2m тогда в цикле выполнить: выбрать случайное число s в интервале , установить до тех пор пока (k - rk) > m . В противном случае установить r = 0.5; 5. Вычислить q , как результат алгоритма Морера с параметром (); 6. Установить ; 7. Установить success=0; 8. Пока success=0 выполнить в цикле: 8.1. Выбрать случайное целое число R в интервале [I+1, 2I ] и установить n = 2Rq + 1 ; 8.2. Использовать деление n на простые числа < B для нахождения простых делителей: 8.3. Если простые делители не найдены выполнить: 8.3.1. Выбрать случайное целое a в интервале ; 8.3.2. Вычислить ; 8.3.3. Если b = 1 выполнить: 8.3.1.1. Вычислить ; 8.3.1.2. Если d =1 установить success = 1; 9.Вернуть (n ).

Неприводимые многочлены

2. Пусть f(x) - полином степени m в . Тогда f(x) неприводим над тогда и только тогда, когда .

Проверка многочлена на неприводимость

Вход : Простое число p и нормированный многочлен f(x) степени m в .

Выход : Ответ на вопрос, приводим ли многочлен f(x) над .

1. Установить u(x)=x ; 2. В цикле по i от 1 до выполнить: 2.1. Вычислить ; 2.2. Вычислить d(x) = НОД (f(x), u(x)-x) ; 2.3. Если вернуть (приводимый); 3. Вернуть (неприводимый).

Отсюда следует метод для нахождения неприводимого многочлена степени m в – сгенерировать случайный нормированный многочлен степени m в , проверить его на неприводимость и повторять до тех пор, пока неприводимый многочлен не будет найден. Число многочленов, которые необходимо перебрать для того, чтобы найти неприводимый многочлен в среднем равно m .

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

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

Теорема 4. Пусть нечетные натуральные числа, причем для каждого простого делителя числа 5 существует целое число а такое, что

Тогда каждый простой делитель числа N удовлетворяет сравнению

Доказательство. Пусть простой делитель числа некоторый делитель 5. Из условий (10) следует, что в поле вычетов справедливы соотношения

Обозначим буквой порядок элемента а в мультипликативной группе поля Первые два из соотношений (11) означают, что входит в разложение на простые множители числа в степени такой же, как и в разложение последнее - что делится на Таким образом, каждый простой делитель числа 5 входит в разложение в степени не меньшей, чем в так что делится на 5. Кроме того, четно. Теорема 2 доказана.

Следствие. Если выполнены условия теоремы то простое число.

Действительно, пусть N равняется произведению не менее двух простых чисел. Каждое из них, согласно утверждению теоремы 2, не меньше, чем Но тогда Противоречие и доказывает следствие.

Покажем теперь, как с помощью последнего утверждения, имея большое простое число 5, можно построить существенно большее простое число Выберем для этого случайным образом четное число на промежутке положим Затем проверим число N на отсутствие малых простых делителей, разделив его на малые простые числа; испытаем N некоторое количество раз с помощью алгоритма 5. Если при этом выяснится, что составное число, следует выбрать новое значение и опять повторить вычисления. Так следует делать до тех пор, пока не будет найдено число выдержавшее испытания алгоритмом достаточно много раз. В этом случае появляется надежда на то, что простое число, и следует попытаться доказать простоту с помощью тестов теоремы 2.

Для этого можно случайным образом выбирать число и проверять для него выполнимость соотношений

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

Предположим, что построенное число N действительно является простым. Зададимся вопросом, сколь долго придется перебирать числа а, пока не будет найдено такое, для которого будут выполнены условия (12). Заметим, что для простого числа N первое условие (12), согласно малой теореме Ферма, будет выполняться всегда. Те же числа а, для которых нарушается второе условие (12), удовлетворяют сравнению Как известно, уравнение в поле вычетов имеет не более решений. Одно из них Поэтому на промежутке имеется не более чисел, для которых не выполняются условия (12). Это означает, что, выбирая случайным образом числа а на промежутке при простом N можно с вероятностью большей, чем найти число а, для которого будут выполнены условия теоремы 2, и тем доказать, что N действительно является простым числом.

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

новым S все указанные выше действия, можно построить еще большее простое число. Начав с какого-нибудь простого числа, скажем, записанного 10 десятичными цифрами (простоту его можно проверить, например, делением на маленькие табличные простые числа), и повторив указанную процедуру достаточное число раз, можно построить простые числа нужной величины.

Обсудим теперь некоторые теоретические вопросы, возникающие в связи с нахождением простых чисел вида где числа удовлетворяют неравенствам Прежде всего, согласно теореме Дирихле, доказанной еще в 1839 г., прогрессия содержит бесконечное количество простых чисел. Нас интересуют простые числа, лежащие недалеко от начала прогрессии. Оценка наименьшего простого числа в арифметической прогрессии была получена в 1944 г. Ю.В. Линником. Соответствующая теорема утверждает, что наименьшее простое число в арифметической прогрессии не превосходит где С - некоторая достаточно большая абсолютная постоянная. В предположении справедливости расширенной гипотезы Римана можно доказать, , что наименьшее такое простое число не превосходит при любом положительном

Таким образом, в настоящее время никаких теоретических гарантий для существования простого числа существует. Тем не менее, опыт вычислений на ЭВМ показывает, что простые числа в арифметической прогрессии встречаются достаточно близко к ее началу. Упомянем в этой связи гипотезу о существовании бесконечного количества простых чисел с условием, что число также простое, т. е. простым является уже первый член прогрессии.

Очень важен в связи с описываемым методом построения простых чисел также вопрос о расстоянии между соседними простыми числами в арифметической прогрессии. Ведь убедившись, что при некотором число составное, можно следующее значение взять равным и действовать так далее, пока не будет найдено простое число И если расстояние между соседними простыми числами в прогрессии велико, нет надежды быстро построить нужное число Перебор чисел до того момента, как мы наткнемся на простое число N окажется слишком долгим. В более простом вопросе о расстоянии между соседними простыми числами в натуральном ряде доказано лишь, что что, конечно, не очень хорошо для наших целей. Вместе с тем существует так называемая гипотеза Крамера (1936 г.), что дающая вполне приемлемую оценку. Примерно такой же результат следует и из расширенной гипотезы Римана. Вычисления на ЭВМ показывают, что простые

числа в арифметических прогрессиях расположены достаточно плотно.

В качестве итога обсуждения в этом разделе подчеркнем следующее: если принять на веру, что наименьшее простое число, а также расстояние между соседними простыми числами в прогрессии при оцениваются величиной то описанная схема построения больших простых чисел имеет полиномиальную оценку сложности. Кроме того, несмотря на отсутствие теоретических оценок времени работы алгоритмов, отыскивающих простые числа в арифметических прогрессиях со сравнительно большой разностью, на практике эти алгоритмы работают вполне удовлетворительно. На обычном персональном компьютере без особых затрат времени строятся таким способом простые числа порядка

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

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

Дело было давно, в университете, когда мы начали изучать язык программирования Pascal и домашним заданием стало создание алгоритма нахождения простых чисел.

Алгоритм был придуман и тутже реализован на изучаемом языке. Программа запрашивала у пользователя число N и искала все простые числа до N включительно. После первого успешного теста сразу же возникло непреодолимое желание ввести N = «много». Программа работала, но не так быстро как хотелось бы. Естественно, дело было в многочисленных проверках (порядка N*N/2), поэтому пришлось избавиться от лишних. В итоге получилось 5 похожих алгоритмов каждый из которых работал быстре предыдущего. Недавно захотелось их вспомнить и реализовать, но на этот раз на Python.

Итак, поехали. Первый алгоритм, ударивший в студенческую голову, продемонстрирован в Листинге 1.
# Листинг 1 # вводим N n = input("n=") # создаем пустой список для хранения простых чисел lst = # в k будем хранить количество делителей k = 0 # пробегаем все числа от 2 до N for i in xrange(2, n+1): # пробегаем все числа от 2 до текущего for j in xrange(2, i): # ищем количество делителей if i % j == 0: k = k + 1 # если делителей нет, добавляем число в список if k == 0: lst.append(i) else: k = 0 # выводим на экран список print lst
Очень быстро понимаешь, что в подсчете делителей каждого числа нет никакой надобности и поэтому переменную k можно освободить от своих обязанностей. Действительно, если хотябы один делитель имеется, то число уже не простое. Смотрим Листинг 2.
# Листинг 2 n = input("n=") lst = for i in xrange(2, n+1): for j in xrange(2, i): if i % j == 0: # если делитель найден, число не простое. break else: lst.append(i) print lst
Конструкция break позволяет нам завершить выполнение внутреннего цикла и перейти к следующей итерации внешнего.
Далее возникает вопрос: «а зачем делить на 4, если на 2 число не делится?». Приходим к выводу, что искать делители нужно только среди простых чисел не превышающих делимое. Наш алгоритм превращается в… см. Листинг 3.
# Листинг 3 n = input("n=") lst= for i in xrange(2, n+1): # пробегаем по списку (lst) простых чисел for j in lst: if i % j == 0: break else: lst.append(i) print lst
А потом вспоминаем теорию чисел и понимаем, что переберать надо только числа, не превосходящие корня из искомого. К примеру, если число M имеет делитель pi, то имеется делитель qi, такой, что pi * qi = M. То есть, чтобы найти пару, достаточно найти меньшее. Среди всех пар, предполагаемая пара с максимальным наименьшим - это пара с равными pi и qi, то есть pi * pi = M => pi = sqrt(M). Смотрим Листинг 4.
# Листинг 4 from math import sqrt n = input("n=") lst= for i in xrange(2, n+1): for j in lst: if j >
Код из Листинга 4 при N=10000 выполняется примерно в 1000 раз быстрее, чем самый первый вариант. Есть еще один «ускоритель», проверять только те числа, которые заканчиваются на 1, 3, 7 или 9 (так как остальные очевидно делятся на 2 или 5). Наблюдаем Листинг 5.
# Листинг 5 from math import sqrt n = input("n=") lst= for i in xrange(2, n+1): if (i > 10): if (i%2==0) or (i%10==5): continue for j in lst: if j > int((sqrt(i)) + 1): lst.append(i) break if (i % j == 0): break else: lst.append(i) print lst
В следствии незначительного изменения Листинга 5 получаем небольшую прибавку в скорости:
# Листинг 6 from math import sqrt n = input("n=") lst= for i in xrange(3, n+1, 2): if (i > 10) and (i%10==5): continue for j in lst: if j > int((sqrt(i)) + 1): lst.append(i) break if (i % j == 0): break else: lst.append(i) print lst
Итого: Программа из последнего листинга выполняется, примерно, в 1300 раз быстрее первоначального варианта.
Я не ставил перед собой задачи написать программу максимально быстро решающую данную задачу, это скорее демонстрация начинающим программистам того, что правильно составленный алгоритм играет далеко не последнюю роль в оптимизации Ваших программ.

P.S.
Благодаря замечаниям получаем Листинг 7:
# Листинг 7 n = input("n=") lst= for i in xrange(3, n+1, 2): if (i > 10) and (i%10==5): continue for j in lst: if j*j-1 > i: lst.append(i) break if (i % j == 0): break else: lst.append(i) print lst

При N=10000, поучаем время:
time 1 = 26.24
time 2 = 3.113
time 3 = 0.413
time 4 = 0.096
time 5 = 0.087
time 6 = 0.083
time 7 = 0.053

Решето Эратосфена:
# Листинг 8 n = input("n=") a = range(n+1) a = 0 lst = i = 2 while i <= n: if a[i] != 0: lst.append(a[i]) for j in xrange(i, n+1, i): a[j] = 0 i += 1 print lst

Результаты при n = 1 000 000:
time 7 = 7.088
time 8 = 1.143