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

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

34
где µ(n)–функция Мебиуса.
В 1901 г. Хельге фон Кох показал, что гипотеза Римана эквивалентна
следующему утверждению о распределении простых чисел:
π(x) =
Z
x
2
dt
ln t
+ O(
√
x ln x) при x → ∞
1.14. Извлечение квадратного корня в конечных полях
В реализациях методов квадратичного решета и решета числового
поля, описываемых в 4-й и 5-й главах, будет использован алгоритм
извлечения квадратного корня в конечных полях, разработанный Шенксом
и Тоннелли. Опишем данный алгоритм в этом параграфе.
Рассмотрим конечное поле GF
p
, p > 2, и элемент a, являющийся
квадратичным вычетом по модулю p. Требуется найти x такое, что a ≡
x
2
( mod p).
Представим число p −1 в виде p −1 = 2
r
·s, где s–нечетно. Заметим,
что поскольку p − 1–четно, r ≥ 1. Пусть z –квадратичный невычет по
модулю p. Вычислим y = z
s
mod p. Поскольку порядок любого элемента
является делителем числа 2
r
· s, то порядок y является делителем 2
r
,
откуда y
2
r
≡ 1 ( modp). Можно также показать, что y
2
r
−1
≡ −1 ( mod p),
т.е. порядок элемента y равен в точности 2
r
. Вычислим далее элементы
λ
0
= a
s
( mod p), w
0
= a
(s+1)/2
( mod p). (1.11)
Заметим, что
w
2
0
≡ a · λ
0
( mod p) и x
2
≡ a( mod p) → x
2s
≡ a
s
= λ
0
( mod p). (1.12)
Поскольку порядок элемента x
s
является делителем 2
r
, то порядок
λ
0
является делителем 2
r−1
. Идея метода Шенкса–Тоннелли состоит
в построении последовательности пар чисел (λ
i
, w
i
), удовлетворяющих
условию
w
2
i
≡ a · λ
i
( mod p), i = 0, 1, 2, ... , (1.13)
                                                                             34

где µ(n)–функция Мебиуса.
      В 1901 г. Хельге фон Кох показал, что гипотеза Римана эквивалентна
следующему утверждению о распределении простых чисел:
             Z x
                 dt      √
      π(x) =         + O( x ln x) при x → ∞
              2 ln t


1.14. Извлечение квадратного корня в конечных полях
      В реализациях методов квадратичного решета и решета числового
поля, описываемых в 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. Вычислим y = z s mod p. Поскольку порядок любого элемента
является делителем числа 2r · s, то порядок y является делителем 2r ,
          r                                              r
                                                             −1
откуда y 2 ≡ 1 ( mod p). Можно также показать, что y 2            ≡ −1 ( mod p),
т.е. порядок элемента y равен в точности 2r . Вычислим далее элементы

      λ0 = as ( mod p), w0 = a(s+1)/2 ( mod p).                           (1.11)

      Заметим, что

 w02 ≡ a · λ0 ( mod p) и x2 ≡ a( mod p) → x2s ≡ as = λ0 ( mod p).         (1.12)

      Поскольку порядок элемента xs является делителем 2r , то порядок
λ0 является делителем 2r−1 . Идея метода Шенкса–Тоннелли состоит
в построении последовательности пар чисел (λi , wi ), удовлетворяющих
условию

    wi2 ≡ a · λi ( mod p), i = 0, 1, 2, ... ,                             (1.13)

Страницы