Чебышева при некоторых константах 0 < с1 < 1 < с2 выполняются неравенства

xx Cl - < 7г(ж) < С2

ln x ln x

рого uo выполняется цепочка неравенств

N П1 (a2 (log и)6) - n(ai (log и)6) ca2(log и)6 C2al (log и)6

log(a2(log и)6) log(ai(log и)6) ca2(log и)6 C2al(log и)6

7 log log и 6 log log и (log и)6 f ca2 C2al\

log log и

{lognf log log и

где константы и ы так, что log ai > 0 log a2 < loglog и и сз > та при достаточно больших и.

Полагаем x = a2(logи)6. Тогда произведение

11 = (и - 1)(и2 - 1) - ... - (их - 1) имеет не более x?l3 log и простых делителей. С другой стороны,

х23 log п < < N,

log log и

ляющееся делителем числа П.

Это - искомое простое число, так как для него найдется простой делитель q = Р{г - 1) > г2/3 > 4\/rlogn, удовлетворяющий условию q or (и). Действительно,

r - 1 r - 1

<x

п 1 ф \ (mod г).

С другой стороны, всегда и =1 ((mod тачит, or (и) не делит и or (и) (r - Х)а доказана. □

Теорема 2. Алгоритм асимптотическую сложность 0((log и)12 х X pol(loglogи))де pol(x) - некоторый многочлен.

Доказательство. Будем для краткости использовать обозначение 0(/(и) щенки 0(/(u)pol(loglogи)).

Полиномиальность первого шага алгоритма вытекает из того, что если число ет вид a\ Ъ> 1о Ъ < [log2 uJ. Поэтому проверку можно выполнить путем последовательных попыток извлечения корня тх простых чисел p [log2 uJ . Для нахождения корня можно, например, применить алгоритм последовательного вы-

А именно, если x - ретепше уравнения xp = и и

x = xi2i

то xk = ли (2k)p < и< (2k+1) xk-1 = ли (2k + 2k-1 )p < и, и т.д. Сложность выполнения этого шага при использовании алгоритма умножения Шенхаге-Штрассена и последовательного возведения в квадрат можно оценить величиной 0((log и)4loglogи)=0((logи)4). По теореме 1 в первом цикле (while) выполняется 0((log и)6) ша-

полного перебора всех делителей потребуется не более

0{pol{\og\ogn))=0{{\ogn)3)

операций. Шаг 8 алгоритма имеет сложность 0(pol(loglogи)), по-

му сложность выполнения первого цикла оценивается величиной 0~((logn)9).

Во втором цикле (for) выполняется 2logn = 0{{logn)4) шагов. Вычисление левой части в равенстве (2) можно проводить с применением метода повторного возведения в квадрат и алгоритма быстрого

му сложность проверки равенства (2) составляет

0(r(log и)2 pol (log log и))= 0 ((log и)5),

а выполнения всего второго цикла-0((logи)12). Теорема дока-□

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

r (n, r) = 1 n

Во втором цикле (for) сравнение (2) также всегда выполнено, поэтому

Если в первом цикле (while) не будет найдено искомое простое число татся результатом r = n. В силу шага 5 алгоритма

Рассмотрим случай, когда в первом цикле будет найдено простое число г такое, что г -1 имеет простой делитель qAlogn и q\or{n). Пусть жтых делителей числа 1 i k. Поскольку в этом случае Or(n делить HOK(or (p1), , Or (pk)), то найдется простой делитель тела юторого q or (p). Так как

стое», то во втором цикле (for) для всех 1 а 2\/rlogn выполнено сравнение (2), а следовательно,и сравнение

(x - a)n = (xn - а) (mod xr - 1, mod p)

Fp = GF(p)

h(x) (xr - 1) -многочлен h(x) = x - 1. Тогда сравнение (3) можно заменить сравнением

(x - a)n = (xn - a) (mod h(x), mod p),

которое на самом деле означает равенство элементов в поле Fp(x)/(h(x)). Тем самым задача свелась к изучению свойств элементов конечного поля.

Осталось показать, что сравнение (4) для всех 1 а 2/r log п может выполняться только в случае, когда n = жотором k 1. Поскольку числа такого вида уже были отбракованы на первом шагу алгоритма, то полученное противоречие завершит доказательство теоремы.

Оставшуюся часть доказательства разобьем на несколько этапов.

1. Пусть d = or(p и k - многочлена h(x). Покажем, что k = d.

Согласно выбору многочлена h(x) все его корни должны иметь порядок торядок делит и r - тое). Еели deg h(x)=k,

то в поле Fp(x)/(h(x)) все элементы являются корнями уравнения Xp - X = 0 тачит r (pk - Отсюда pk = 1 (mod d k.

С другой стороны, так как r pd - 1, то

xp - x = О (mod h(x), mod p) и для каждого элемента g(x толя Fp(x)/(h(x)) выполнено сравнение g(x)p = xp ) = g(x) (mod h(x), mod p)

Xp -

- X = k < d.

2. Пусть I = 2\/rlogn. Покажем, что элементы (ж - a), 1 < а < порождают в поле Fp(x)/(h(x)) = GF(pd ю подгруппу G порядка G > п?.

Рассмотрим в группе тожество S, состоящее элементов, задаваемых многочленами вида

(x - a)u

У которых

Покажем, что все такие многочлены задают различные элементы поля. Если бы существовали элементы 1 а, а 1 такие, что а=а (mod pfaлo бы p< щвыбора числа r (как результата работы первого цикла алгоритма), имеем r>q4л/г logп>1, p< r n

d- 1

элементы поля Fp(x)/(h(x)).

Число элементов в разбиений числа d - на 1 + 1 слагаемых, откуда

Л + d - 1\ (1 + d - + d - 2) d /d\

>

> 2 = n

поскольку d = Or{p) q 4\/r logn = 21.

g( x) G

= (m: g(x)m = g(xm) (mod xr - 1, mod p)}

Покажем, что множество 1д(х) замкнуто относительно умножения. Пусть mi,m2 £ 1д{х)- Имеем

g(x)m1m2 = (g(x)m1 )m2 = g(xm1 )m2 (mod xr - 1, mod p).

С другой стороны,

g(xm1 )m2 = g(xm1m2) (mod xm1 r - 1, mod p),

откуда

g(xm1 )m2 = g(xm1 m2) (mod xr - 1, mod p).

4. Обозначим через от элемента g(x поле Fp(x)/(h(x)), og = G m, что если m1 ,m2 £ Ig(x и m1 = m2 (mod r), то m1 = m2 (mod og).

Пусть m2 = m1 + kr, k да в поле Fp(xx)/(h(x)) справедливы равенства

g(x)m1 g(x)kr = g(x)m2 = g(xm2 )= g(xm1+kr )= g(xm1 )= g(x)m1.

Так как g(x) = отучаем g(x)kr = теуда og kr ш m1 = m2

(mod og).

Завершим доказательство теоремы.

Пусть Е = {riY О < «,i < LvJ }• В силу п. 3 -Б С 1д(ху Так как -Е = (1+ [vJ)2 >г, то в Е найдутся два элемента прР и п22 такие, что = (i2,j2) ш и1 pj1 = и2pj2 (mod r). В силу предыдущего

пункта получаем и1 pj1 = ui2pj2 (mod og). Отсюда

-i2 = -j1 (mod og

Вместе с тем, nil pb2-ji a og>n2. Поэтому ф-2=р2-К,

что возможно только в случае, когда и = жотором k 1.

□

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

ших значений тетых чисел даст ответ r = и, что фактически будет означать проверку простоты полным перебором всех делителей. С другой стороны, известный неполиномиальный

детерминированный алгоритм, предложенный Адлеманом, Померанцем и Румли ([23]), и улучшенный Коэном и Ленстрой ([29]), имеет трудоемкость 0(logu°g°g°gn), что при всех практически значимых и

номиального алгоритма.

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

§ 12. Построение больпшх простых чисел

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

значения», данные тесты основаны на применении достаточных усло-

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

простое число построено.

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

12.1. Критерий Люка

Следующая хорошо известная теорема, впервые доказанная Люка в 1876 г., превращает малую теорему Ферма в критерий простоты и

пользовано для доказательства простоты этого числа.

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

(1) 3aGZ;, (а"-1 = 1 (mod п)) л (Vg (п- 1), а" ф1 (mod п)).