§7. Построение доказуемо простых чисел общего и специального вида.
7.1. Теорема Сэлфриджа и доказуемо простые числа общего вида на основании полного разложения (n—1).
Ранее мы изучили тесты на простоту, которые с некоторой малой вероятностью могут принять составное число за простое. Это – тесты Ферма, Соловея-Штрассена, Миллера-Рабина. Однако в некоторых случаях требуется построение доказуемо простых чисел, то есть чисел, простота которых доказана. Для этого существует класс тестов на простоту, которые могут принять простое число за составное, но не наоборот. Эти тесты основаны на теории групп.
Теорема Сэлфриджа.
Пусть n—1= . n – простое, a: 1) an—1≡1(mod n);
2) 1(mod n).
Доказательство:
Пусть n – простое число. Тогда (1) выполняется для всех a<n согласно теореме Ферма. В силу критерия Люка, найдется a: On(a)=n—1 s<n—1 выполняется as 1(mod n), а поскольку , < n—1, то выполняется (2).
Возьмем q1. Пусть a: 1) an—1≡1(mod n); 2) 1(mod n). Из (1) и (2) следует, что On(a)\(n—1) и On(a) не делит . Откуда из * следует, что \On(a). Согласно Теореме 3 (п.1), On(a)\φ(n) \ φ(n).
Рассматривая аналогичным образом q2, q3,…,qk, убеждаемся, что \φ(n), \φ(n), … , \φ(n). Тогда =(n—1)\φ(n). Но последнее возможно только в случае, когда n—1=φ(n), то есть тогда, когда n – простое число.
Теорема Сэлфриджа дает удобный критерий для доказательства простоты числа. На основании этой теоремы построены алгоритмы проверки чисел на простоту, которые требуют полной или частичной факторизации числа n—1, а потому называются n—1 – методами.
В общем случае мы можем говорить о том, что число n—1 по крайней мере четное.
В том случае, когда нам известно полное разложение проверяемого числа на множители, можно использовать следующий
тест Миллера на простоту:
Вход: n – число для проверки, n—1= - каноническое разложение, t – параметр надежности.
1. Выбрать t различных случайных чисел aj: 1<aj<n
2. Для каждого aj вычислить ajn—1 mod n. Если какой-либо из результатов не равен «1», то идти на Выход с сообщением «n – составное число».
3. Для каждого qi выполнить:
3.1. Для каждого aj вычислить mod n. Если какой-либо из результатов не равен единице, то идти на шаг 3, взять следующее qi. Если все результаты равны «1», то идти на Выход с сообщением «вероятно, n – составное число».
4. Идти на Выход с сообщением «n – простое число».
Выход.
Замечание: Если t=n—2, то слово «вероятно» на шаге 3.1. следует убрать.
Если число n было предварительно проверено на простоту вероятностным тестом Миллера-Рабина, то в тесте Миллера достаточно перебрать 4-6 значений aj.
Тест Миллера, основанный на теореме Сэлфриджа, пригоден для доказательства простоты любого нечетного числа, если известно разложение на простые сомножители числа, ему предстоящего. Однако этот тест достаточно трудоемок. Для некоторых чисел особого вида построены специальные доказательства простоты. Некоторые из таких чисел мы рассмотрим в п.3-4.
7.2. Теорема Поклингтона и доказуемо простые числа общего вида на основании частичного разложения (n—1).
Теорема Сэлфриджа дает четкий критерий для проверки простоты числа n, однако требует знания полного разложения числа (n—1) на простые сомножители. Следующая теорема позволяет ограничиться частичной факторизацией (n—1).
Теорема Поклингтона.
Пусть n=RF+1, F= - каноническое разложение.
Если a: 1) an—1≡1(mod n);
2) 1(mod n) .
p≡1(mod F) для любого простого p\n.
■
Итак, если разложить n—1 на два сомножителя n—1=RF, где F> —1, то, если для некоторого a будут выполнены условия Теоремы Поклингтона (1) и (2), то n – простое.
Таким образом, можно значительно сократить количество проверок по сравнению с тестом Миллера.
Замечание.
Если n=RF+1 – нечетное простое число, F> —1, F= , НОД(R,F)=1, то вероятность того, что случайно выбранное 1<a<n будет удовлетворять условиям (1), (2) теоремы Поклингтона, есть .
Замечание.
Если известно полное разложение n—1, то в качестве F следует брать число, составленное из наибольших делителей n—1 для того, чтобы:
1) сократить число проверок условия (2) для каждого a;
2) уменьшить степени, в которые возводится a на этапе проверки (2);
3) повысить вероятность того, что случайно выбранное a будет удовлетворять условию (2), а значит уменьшить количество перебираемых a.
Пример.
n=4021. —1<63.
n—1=4020=22·3·5·67. F=67, R=22·3·5=60.
Проверка условий:
a=2.
1) 24020 mod 4021=1.
2)260—1 mod 4021=1451.
НОД(4021,1451)=1.
n=4021 – простое число.
(Заметим, что вероятность того, что наугад выбранное a будет удовлетворять условиям теоремы Поклингтона для данного примера, есть (1—1/67)≈0,985).
7.3. Числа Ферма. Теорема Пепина.
Теорема.
Если число вида p=an+1 – простое, то 1) a – четное;
2) n=2k для некоторого k.
Доказательство:
Четность a очевидна, так как иначе p было бы четным, а значит не простым.
Предположим теперь m>2 - нечетное число : n= m·2k. Тогда
=an—m—an—2m+…+a3m—a2m+am—a0 Z.
Тогда (am+1)\(an+1), значит p – составное число. Предположение неверно, следовательно верно обратное.
Числа Fk= +1 называются числами Ферма.
F0=3, F1=5, F2=17, F3=257, F4=65739 – простые числа. Пьер Ферма выдвигал гипотезу о простоте всех чисел Ферма, но Леонардом Эйлером в 1732 г. была показана составность числа F5.
В настоящее время существует следующий критерий проверки чисел Ферма на простоту:
Теорема Пепина
Fk – простое число .
Доказательство:
Пусть Fk – простое число. Тогда по критерию Эйлера для символа Лежандра,
.
В силу простоты, Fk не делится на 3.
Поэтому возможны два случая: Fkmod 3=1 или Fk mod 3=2.
Случай Fk mod 3=1 невозможен, так как это значило бы, что mod 3 = 0, а это не так. Поэтому Fk mod 3=2, и тогда
На основании теоремы Пепина построен тест Пепина, проверяющий верность сравнения . Тест Пепина детерминированный, состоит из одной итерации и дает точный ответ о простоте или составности числа Ферма.
7.4. Числа Мерсенна.
Теорема 1
Если число вида p=an—1 – простое 1) a – четное;
2) n – простое.
Доказательство:
Четность а очевидна, так как иначе р было бы четным, а значит, составным.
Допустим, что n – не простое n=mk. Тогда
=ak(m—1)+ak(m—2)+…+ak+1 Z.
Тогда (ak—1)\(an—1), значит р – не простое число. Предположение неверно, значит верно обратное.
Простые числа вида Mp=2p—1, где р – простое число, называются числами Мерсенна.
Теорема 2
Число вида Mp=2p—1, где р>2 – простое число, является простым в последовательности, определенной равенствами u0=4, ui+1=(ui2—2) mod Mp, выполняется up—2≡0(mod Mp).
■
Из Теорем 1 и 2 следует
Тест Лукаса-Лемера для чисел Мерсенна
Вход: Число Мерсенна Mn=2n—1.
Ш.1. Пробными делениями проверить, имеет ли n делители между «2» и . Если имеет, идти на Выход с сообщением «Mn – составное число».
Ш.2. Задать u=4.
Ш.3. n—2 раза вычислить u=(u2—2) mod Mn.
Ш.4. Если u=0, то «Mn – простое число», иначе «Mn – составное число».
Выход.
В настоящее время особое внимание уделяется двойным числам Мерсенна MMp=2Mp –1, например 7=M3=MM2. Алгоритм построения таких чисел следующий: сначала строится сравнительно небольшое простое число Мерсенна Mp, а затем по нему – двойное число Мерсенна MMp, которое проверяется на простоту тестом Лукаса-Лемера минуя первый шаг.
Аналогично строятся тройные и т.д. числа Мерсенна. Например, тройным числом Мерсенна является 127=M7=MMM2.
Не для всех чисел Мерсенна существуют двойные и тройные числа. Например, MM13 не является простым.
Первыми простыми числами Мерсенна являются M2=3, M3=7, M5=31, M7=127, M13=8191, M17, M19, M31.
На данный момент (2007 г.) не доказана конечность или бесконечность количества простых чисел Мерсенна.
7.5. Теорема Диемитко и процедура генерации простых чисел заданной длины ГОСТ Р 34.10-94.
Следующая теорема позволяет строить доказуемо простые числа большего размера на основе простых чисел меньшего размера.
Теорема Диемитко.
Пусть 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. Вычисляем N= . Если N – нечетное, то N=N+1.
Ш.2. u=0.
Ш.3. Вычисляем p=(N+u)q+1 – кандидат в простые.
Ш.4. Если p>2t, возвращаемся на Ш.1.
Ш.5. Если 2n—1≡1(mod n) и 2N+u 1(mod n), то идем на Выход.
Ш.6. Вычисляем u=u+2. Возвращаемся на Ш.3.
Выход. p – простое число.
Первое слагаемое в построении числа N обеспечивает минимальный требуемый размер числа p, а второе вносит в процедуру поиска новых простых чисел необходимый элемент случайности.
Проверка на Шаге 4 необходима, чтобы число p не превышало своей верхней границы, а проверка на Шаге 5 есть проверка условия теоремы Диемитко при a=2.
Пример:
Вход: t=4, q=3=[11]2
N= =3. N=N+1=4.
u=0.
p=4·3+1=13.
13<24=16.
212 mod 13 =1, 24 mod 13 = 3.
Выход. р=13=[1011]2
Замечание
Поскольку на Шаге 5 условие теоремы Диемитко проверяется не для всех a<p, а только для 2, то некоторые простые числа, сгенерированных этим алгоритмом, не опознаются как простые. Но вероятность того, что для простого числа n наугад выбранное число a будет удовлетворять условиям теоремы Диемитко, есть (1—1/q), а q – достаточно большое число. Таким образом, проверки при a=2 вполне достаточно, чтобы не отсеивать слишком много простых чисел. Выбор a=2 обусловлен тем, что возведение числа 2 в степень в двоичном представлении является простой операцией.
|
