Математические основы защиты информации. Ишмухаметов Ш.Т - 40 стр.

                                                                           41

      Замечание. Несмотря на то, что тест AKS явился решением крупной
и долгостоявшей научной проблемы, он является не слишком удобным с
практической точки зрения. Проверка условий пункта 3 является настолько
громоздкой, что общая оценка времени работы алгоритма достигает
O(log18 n) (см. Д. Вентури. Лекции по алгоритмической теории чисел [35]).
Поэтому этот тест следует применять лишь в тех случаях, когда надо
получить гарантированное доказательство того, что число n является
простым.
      В следующем главе мы выясним, как распределяются простые числа
и дадим формулировку знаменитой проблемы Римана.


2.16. Извлечение квадратного корня в конечных полях
      В реализациях методов квадратичного решета и решета числового
поля, описываемых в 4-й и 5-й главах, будет использован алгоритм
извлечения квадратного корня в конечных полях, разработанный Шенксом
и Тоннелли. Опишем данный алгоритм в этом параграфе.
      Рассмотрим конечное поле GFp , p > 2, и элемент a, являющийся
квадратичным вычетом по модулю p. Требуется найти x такое, что a ≡
x2 ( mod p).
      Представим число p−1 в виде p−1 = 2r ·s, где s–нечетно. Заметим, что
поскольку p − 1–четно, r ≥ 1. Пусть z –некоторый квадратичный невычет по
модулю p (его можно найти просто перебором по элементам Fp , пока символ
Лежандра (z/p) не окажется равным −1).
      Рассмотрим 2 случая:
1. p ≡ 3 (mod 4). В этом случае можно сразу найти решение
                                   p+1
                             x=a    4    (mod p)

2. p ≡ 1 (mod 4).
      Вычислим y = z s mod p. Поскольку порядок любого элемента
является делителем числа 2r · s, то порядок y является делителем 2r ,
           r                                           r
                                                           −1
откуда y 2 ≡ 1 ( mod p). Можно также показать, что y 2          ≡ −1 ( mod p),