|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ilia Kantor 2:5020/1815.6 20 Oct 2001 22:32:38
To : Victor Anikeev
Subject : Огpомные числа
--------------------------------------------------------------------------------
VA> Тогда я вопpос по-дpyгомy поставлю. Как вообще pаботают пpогpаммы,
VA> котоpые отыскивают пpостые числа? Дело в том, что я хочy сделать
VA> пpогpаммy-бpелок, типа подаpка - пyсть сидит в тpее и все вpемя
VA> отыскивает пpостые числа и записывает их в текстовый файл
аиболее эффективным средством построения простых чисел является несколько
модифицированная малая теорема Ферма.
Пусть N, S --- нечётные натуральные числа, N-1 = S*R, причем для каждого
простого делителя q числа S существует целое число a такое, что
aN-1=1(mod N), ОД( a(N-1)/q-1, N ) = 1
Тогда каждый простой делитель p числа N удовлетворяет сравнению p = 1(mod 2S)
Следствие.
Если выполнены условия теоремы Ферма и R <= 4S+2, то N --- простое число.
Покажем теперь, как с помощью последнего утверждения, имея большое простое число
S, можно построить существенно большее простое число N. Выберем для этого
случайным образом чётное число R на промежутке R <= 4S+2 и положим N=SR+1. Затем
проверим число N на отсутствие малых простых делителей, разделив его на малые
простые числа; испытаем N некоторое количество раз с помощью алгоритма Рабина.
Если при этом выяснится, что N --- составное число, следует выбрать новое
значение R и опять повторить вычисления. Так следует делать до тех пор, пока не
будет найдено число N, выдержавшее испытания алгоритмом Рабина достаточно много
раз. В этом случае появляется надежда на то, что N --- простое число, и следует
попытаться доказать простоту с помощью тестов теоремы 2.
Для этого можно случайным образом выбирать число a, 1 < a < N, и проверять для
него выполнимость соотношений aN-1=1(mod N), ОД(aR-1, N)=1.
Если при выбранном a эти соотношения выполняются, то, согласно следствию из
теоремы Ферма, можно утверждать, что число N простое. Если же эти условия
нарушаются, нужно выбрать другое значение a и повторять эти операции до тех пор,
пока такое число не будет обнаружено.
Предположим, что построенное число N действительно является простым. Зададимся
вопросом, сколь долго придётся перебирать числа a, пока не будет найдено такое,
для которого будут выполнены условия (12). Заметим, что для простого числа N
первое условие (12), согласно малой теореме Ферма, будет выполняться всегда. Те
же числа a, для которых нарушается второе условие (12), удовлетворяют сравнению
aR=1(mod N). Как известно, уравнение xR=1 в поле вычетов Fn имеет не более R
решений. Одно из них x=1. Поэтому на промежутке 1 < a < N имеется не более R-1
чисел, для которых не выполняются условия (12).
Это означает, что, выбирая случайным образом числа a на промежутке 1 < a < N,
при простом N можно с вероятностью большей, чем 1-O(S-1), найти число a, для
которого будут выполнены условия теоремы Ферма, и тем доказать, что N
действительно является простым числом.
Заметим, что построенное таким способом простое число N будет удовлетворять
неравенству N>S2, т.е. будет записываться вдвое большим количеством цифр, чем
исходное простое число S. Заменив теперь число S на найденное простое число N и
повторив с этим новым S все указанные выше действия, можно построить ещё большее
простое число. ачав с какого-нибудь простого числа, скажем, записанного 10
десятичными цифрами (простоту его можно проверить, например, делением на
маленькие табличные простые числа), и повторив указанную процедуру достаточное
число раз, можно построить простые числа нужной величины.
Обсудим теперь некоторые теоретические вопросы, возникающие в связи с
нахождением числа R, удовлетворяющего неравенствам S <= R <= 4S+2, и такого, что
N=SR+1 -- простое число. Прежде всего, согласно теореме Дирихле, доказанной ещё
в 1839г., прогрессия 2Sn+1, n=1,2,3,... содержит бесконечное количество простых
чисел. ас интересуют простые числа, лежащие недалеко от начала прогрессии.
Оценка наименьшего простого числа в арифметической прогрессии была получена в
1944г. Ю.В.Линником. Соответствующая теорема утверждает, что наименьшее простое
число в арифметической прогрессии 2Sn+1 не превосходит SC, где C -- некоторая
достаточно большая абсолютная постоянная. В предположении справедливости
расширенной гипотезы Римана можно доказать, что наименьшее такое простое число
не превосходит c(e)*S2+e при любом положительном e.
Таким образом, в настоящее время никаких теоретических гарантий для
существования простого числа N=SR+1, S < R < 4S+2 не существует. Тем не менее
опыт вычислений на ЭВМ показывает, что простые числа в арифметической прогрессии
встречаются достаточно близко к её началу. Упомянем в этой связи гипотезу о
существовании бесконечного количества простых чисел q с условием, что число 2q+1
также простое, т.е. простым является уже первый член прогрессии.
Очень важен в связи с описываемым методом построения простых чисел также вопрос
о расстоянии между соседними простыми числами в арифметической прогрессии. Ведь
убедившись, что при некотором R число N=SR+1 составное, можно следующее значение
R взять равным R+2 и действовать так далее, пока не будет найдено простое число
N.
И если расстояние между соседними простыми числами в прогрессии велико, нет
надежды быстро построить нужное число N. Перебор чисел R до того момента, как мы
наткнемся на простое число N окажется слишком долгим. В более простом вопросе о
расстоянии между соседними простыми числами pn и pn+1 в натуральном ряде
доказано лишь, что pn+1-pn=O(pn38/61+e), что, конечно, не очень хорошо для наших
целей. Вместе с тем существует так называемая гипотеза Крамера (1936г.), что
pn+1-pn=O(ln2pn), дающая вполне приемлемую оценку. Примерно такой же результат
следует и из расширенной гипотезы Римана. Вычисления на ЭВМ показывают, что
простые числа в арифметических прогрессиях расположены достаточно плотно.
В качестве итога обсуждения в этом пункте подчеркнём следующее: если принять на
веру, что наименьшее простое число, а также расстояние между соседними простыми
числами в прогрессии 2Sn+1 при S <= n <= 4S+2 оцениваются величиной O(ln2S), то
описанная схема построения больших простых чисел имеет полиномиальную оценку
сложности. Кроме того, несмотря на отсутствие теоретических оценок времени
работы алгоритмов, отыскивающих простые числа в арифметических прогрессиях со
сравнительно большой разностью, на практике эти алгоритмы работают вполне
удовлетворительно. а обычном персональном компьютере без особых затрат времени
строятся таким способом простые числа порядка 10300.
Конечно, способ конструирования простых чисел для использования в схеме RSA
должен быть массовым, а сами простые числа должны быть в каком-то смысле хорошо
распределёнными. Это вносит ряд дополнительных осложнений в работу алгоритмов.
Впрочем, описанная схема допускает массу вариаций.
аконец, отметим, что существуют методы построения больших простых чисел,
использующие не только простые делители N-1, но и делители чисел N+1, N2+1, N2
+- N+1 $. В основе их лежит использование последовательностей целых чисел,
удовлетворяющих линейным рекуррентным уравнениям различных порядков. Отметим,
что последовательность an, члены которой присутствуют в формулировке малой
теоремы Ферма, составляет решение рекуррентного уравнения первого порядка
un+1=aun, u0=1.
-----------------------------
Закрой за мной дверь, я ухожу.. [Team Кино]
--- GoldEd 3.00.Alpha4+
* Origin: http://algolist.da.ru - Мир Алгоритмов (2:5020/1815.6)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
