Доказательство. Если о в поле Zn есть примитивный элемент, который и будет искомым. Наоборот, пусть для элемента ловие (1). Если ord(a)=o m (n-1), причем условие (1) гарантирует, что m = n - мтельно, (n)= n - 1 и щема до казана. □

Замечание (Сэлфридж). Условие (1) в данной теореме можно заменить на любое из следующих двух условий:

(2) 3 а € Zn, ord(a) = n - 1;

(3)Vq(n-l), 3aGZ;, (a"-i=l (mod n)) Л (a" 1 (modn)).

Действительно, то, что (1) (1) (3), очевидно.

Докажем, что (3) (2 сть n - 1 = qks. По условию для каждого вдется ш, что ord(ai) (n - 1о ord(ai) не делит число Y. Следовательно, ord(ai). Значит, найдутся элементы 6»

ord( 6i) = qiki а = 6 6s

ord(61 6s)= qks = n - L

□

n- 1

этого можно использовать детерминированный алгоритм, основанный на переборе всех возможных значений а € Z", либо воспользоваться следующим вероятностным методом:

1) выбираем случайно числа а1, , as € Z" и проверяем для них условие (1);

2) если условие (1) выполнено хотя бы для одного из этих чисел, n

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

Fk = 22 + 1 k = 1, 2,

2m + 1

в том случае, когда m = 2k.)

Ферма высказывал предположение, что все числа такого вида- простые. При n = 0,1,2, 3, тно так. Но при n = 5, как показал Эйлер в 1732 г., справедливо разложение

F5 = 225 + 1 = 4294967297 = 641 • 6700417

F23 F23

2525223

бы строка длиной в 5 км или книга объемом в 1000 страниц.)

Теорема (Пепин, 1877). Числа Fk = 22 + « k 1 являются простыми в том и только в том случае, когда выполняется условие

3(Fk-1)/2 = -1 (mod Fk)

Доказательство. Так как единственным простым делите-Fk - 1 2

q=2 а 3

т.е. достаточно проверить условие 3(Fk-1)/2 = 1 (mod Fn). Используя формулу Эйлера для вычисления значений квадратичных вычетов и квадратичный закон взаимности Гаусса получаем, что при простом

3(Fk-1)/2

f3 \

= ( -1)(Fk-1)/2

\ 3 )

(mod Fn )

Теперь заметим, что Fk = 1 (mod му условие Fk = О (mod 3) Fk = 2 = - 1 (mod 3)

□

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

(n- 1)

n - 1

но обобщение теоремы Люка основано на рассмотрении других групп вместо мультипликативной группы Z". Фактически, доказательство n

пы Z": если каким-либо образом удается установить, что ее порядок n - 1 n

методов, как метод эллиптических кривых и метод числового поля. 12.2. Теорема Поклингтона

В 1914 г. X. Поклингтоном была доказана следующая теорема.

Теорема (Поклингтон). Пусть n = qk R +1 > 1де q - простое, не являющееся делителем твует целое а такое, что

а"-1 = 1 (mod (a(n-1)/q - 1, n) = 1 остой делитель p числа n т вид p = qk r + 1 жотором r.

pn да из условия теоремы вытекает, что an-1 = 1 (mod a(n-1)/q = =1 (mod p) m а p

m (и - 1) m (и - 1)/q

qk m m ( p - 1)

p- 1 = qkr

Применяя данную теорему для всех делителей тела и - 1, получаем следующий теорему, которая является обобщением теоремы Люка на случай Д >1.

Теорема. Пусть и = FR + 1 > 1де 0 < R < F. Если для любо-q F a

an-1 = 1 (mod и) и (a(n-1)/q - 1,и) = чиело и простое.

Доказательство. Пусть и - тавное и p - нетривиальный и

тель так, что р -\/п. Тогда из условия теоремы вытекает, что для

q F a

an-1 = 1 (mod p) и a(n-1)/q = 1 (mod p). Рассуждая аналогично замечанию к теореме Люка, получаем, что должен найтись элемент,

ма F p - 1. Следовательно, справедлива цепочка неравенств

2 (F + 1)2 > R(F + 1) RF +1 и.

Но р < л/п, противоречие. □

Данная теорема показывает, что если удалось частично факто-и - 1

условию F > /п, то п -простое.

Прежде, чем переходить к дальнейшему, приведем два классических частных случая данной теоремы.

Теорема (Прот, 1878). Пусть и = 2kR +1де R<2k. Если сущест-a

-,in-1)/2

= 1 (mod и),

то истое. □

Теорема (Прот, 1878). Пусть и = 2kR + 1де R< 2k, 3 < 2k + 1 и 3 лит Пгда и - простое в том и только в том случае, когда выполняется условие

3(n-1)/2 = -1 (mod и).

Доказательство. В силу теоремы Поклингтона достаточно

{n-1)/q

= 1 (mod и) a = 3 q = 2 по условию и = 2kR +1 = 1 (mod ловие 3(n-1)/2 = 1 (mod и)

равносильно выполнению равенства

3(п-1)/2

(-1)""/ (1) -1 (mod Fn). □ 2kR + 1 3

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

Заметим, что если в теореме Поклингтона заменить равенство (a(n-1)/q - 1,и) = табое условие a(n-1)/q = 1 (mod и), то можно получить следующий результат.

Лемма. Пусть и = qkR + 1 > 1де q - простое, не являющееся делителем твует целое ж, что an-1 = 1 (mod и)

и a(n-1)/q = 1 (mod и) достой делитель сла и вида p = qkr + 1 жотором r.

Доказательство. Пусть и = p1 ... p. Тогда из условия теоремы в силу китайской теоремы об остатках вытекает, что существует такое тоо an-1 = 1 (mod p) и a(n-1)/q = 1 (mod p). Отсюда получаем, что порядок отента тодулю p удовлет-t ( и - 1) t ( и - 1) /q qk t

В силу леммы Гаусса о цикличности мультипликативной группы кольца Zpm чаем 11p-1(pi - 1) что числа q взаимно

qk ( pi - 1)

pi - 1 = qkr □

Хотя этот результат слабее, чем теорема Поклингтона, данный подход, как показал Н. Диемитко в 1988 г., также может быть эффективно использован для доказательства простоты чисел.

Теорема (Диемитко). Пусть u=qR+1>1de стое, R чет-R < 4(q + 1) a an-1 =

= 1 (mod и) и a(n-1/q = 1 (mod и) то и - простое.

Доказательство. Пусть и - остое и и = p1 Тогда по лемме получаем, что существует такое тоо q (pi - 1).

Обозначим и = piгда и = piQ (mod ще и = 1 (mod q) и pi = 1 (mod Отсюда Q = 1 (mod мтельно, Q = qt + 1 2q + вде быть p авно шаче тое, и ли 1, так как налогично, pi = qs + 1 2q + 1. Таким образом.

и = piQ (1 + 2q)2 = q - 4(q + 11) + 1 > qR +1.

□

Заметим, что в условии теоремы числа и ш R могут быть не взаимно просты.

Эта теорема лежит в основе алгоритма генерации простых чисел в отечественном стандарте на цифровую подпись ГОСТ Р 34.10-94.

бьш заменен на новый ГОСТ Р 34.10-2001.) 12.4. Метод Маурера

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

Следующая лемма является специальным частным случаем теоремы Поклингтона.

Лемма 1. Пусть n = 2FR +1 > 1 вует целое а та-

вия an-1 = 1 (mod « (a(n-1)/q - 1,n) = 1, mo каждый простой p n p = mF + 1 m

Если, кроме того, F > Jn, или F - четное и R<F, то п - простое.

= 1 (mod p) а

(n-1)/g

= 1 (mod p)

замечанию к теореме Люка, получаем, что должен найтись элемент,

MaF (p - 1).

p<n

Тогда р\Аг. Если F>/n, то p=mF+1> /п. Если F нечетно и R<F, то p 2F + 1 и

p2 (2F + 1)2 > (2R +1)(2F +1) > 2RF +1 =

□

Следующая лемма доказана К. Коувером и Дж. Куискуотером в 1992 г.

n F R а

Определим числа жО и 0-y<F равенством 2R=xF+y. Если F/n и число у2 - 4x не равно нулю и не является полным квадратом, то

Доказательство. Согласно лемме 1 для каждого простого делителя тела n ш неравенство p F + 1. По усло-

вию n Fсли число n - составное, то оно не может иметь боле двух простых делителей. Пусть

Тогда

n = 2RF + 1 = (m1F + 1)(m2F + 1)

2R = m1m2F + m1 + m2

m1 m2

m1 m2 < F n > F3

Если m1 + m2 o F > m1m2 m1(F - m2) F - 1. Отсю-m1 = F - 1 m2 = 1 n = F3 + 1

m1 + m2 < F

Следовательно, m1m2 = x ш m1 + m2 = ме Виета m2

являются корнями квадратного уравнения m2 - ym + x = 0, которое имеет решения в целых числах в том и только в том случае, если у2 - 4 или нулем. Лемма доказана. □

Заметим, что убедиться, что заданное число не является полным квадратом, можно вычислив символ Лежандра для нескольких маленьких простых модулей. Если при некотором модуле число не будет являться квадратичным вычетом, то оно не будет и полным квадратом.

Пусть (x) -функция Эйлера.

Лемма 3. Пусть pmoe ud (p - 1) тим чсрез T число элементов x € Zp ыж делится на d. Тогда справедлива оценка

T >

(p - 1),

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

(d, (p - 1)/d) = 1

Доказательство. Используя свойства функции Эйлера получаем

d d* (p-1) k (p-1)/d

причем равенство выполнено в том и только в том случае, когда (d, (p - 1)/d) = L □