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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

29
Если после r проверок окажется r свидетелей простоты, то
заканчиваем тест с сообщением «n–вероятно простое».
Пример. Пусть n = 1729–число Кармайкла (см. стр. 50). Разложим
n − 1 = 2
6
· 3
3
. Выполним тест Миллера–Рабина для a = 2:
x
0
= 2
27
mod 1729 = 645 6= 1, 6= n − 1,
x
1
= x
2
0
mod 1729 = 645
2
mod 1729 = 1065.
x
2
= x
2
1
mod 1729 = 1065
2
mod 1729 = 1.
Последующие элементы {x
i
} для i = 3, 4, 5 равны 1, и
последовательность {x
1
, x
2
, ..., x
s−1
}, не содержит n − 1. Значит, 2
является свидетелем непростоты n, и n = 1729 – составное число.
Оценка эффективности теста Миллера–Рабина
Следующая лемма была доказана Рабином в предположении
справедливости обобщенной гипотезы Римана о распределении простых
чисел (с. 33):
Лемма 1.1. Пусть число n–нечетное число, и n−1 = 2
s
·d, где d–нечетно.
Если для всех x, 0 < x < 2 · ( log
2
n)
2
выполняется x
d
≡ 1 (mod n), или
x
2
k
·d
≡ −1 (modn) для некоторого 0 ≤ k < s. Тогда число n является
простым.
Оценка, приведенная в этой лемме, является полиномиальной, однако,
с теоретической точки зрения она не может быть использована, пока
не доказана обобщенная гипотеза Римана, которая на сегодняшний день
является самой известной из нерешенных «проблем тысячелетия». Кроме
того, для практических расчетов эта оценка является сильно завышенной.
Вместо нее обычно используется граница порядка O(log
2
n) (см. [50]
˙
).
1.11. Вероятностный тест простоты Соловея–Штрассена
Тест Соловея — Штрассена опирается на малую теорему Ферма (разд.
1.2) и свойства символа Якоби (разд. 1.9):
                                                                                29

           Если после r проверок окажется r свидетелей простоты, то
заканчиваем тест с сообщением «n–вероятно простое».
           Пример. Пусть n = 1729–число Кармайкла (см. стр. 50). Разложим
n − 1 = 26 · 33 . Выполним тест Миллера–Рабина для a = 2:
            x0 = 227 mod 1729 = 645 6= 1, 6= n − 1,
            x1 = x20 mod 1729 = 6452 mod 1729 = 1065.
            x2 = x21 mod 1729 = 10652 mod 1729 = 1.
           Последующие элементы        {xi }   для    i   =   3, 4, 5   равны 1, и
последовательность {x1 , x2 , ..., xs−1 }, не содержит n − 1. Значит, 2
является свидетелем непростоты n, и n = 1729 – составное число.

Оценка эффективности теста Миллера–Рабина

            Следующая лемма была доказана Рабином в предположении
справедливости обобщенной гипотезы Римана о распределении простых
чисел (с. 33):

Лемма 1.1. Пусть число n–нечетное число, и n−1 = 2s ·d, где d–нечетно.
Если для всех x, 0 < x < 2 · ( log2 n)2 выполняется xd ≡ 1 (mod n), или
  k
      ·d
x2         ≡ −1 (mod n) для некоторого 0 ≤ k < s. Тогда число n является
простым.

Оценка, приведенная в этой лемме, является полиномиальной, однако,
с теоретической точки зрения она не может быть использована, пока
не доказана обобщенная гипотеза Римана, которая на сегодняшний день
является самой известной из нерешенных «проблем тысячелетия». Кроме
того, для практических расчетов эта оценка является сильно завышенной.
                                                                  ˙
Вместо нее обычно используется граница порядка O(log2 n) (см. [50]).


1.11. Вероятностный тест простоты Соловея–Штрассена
           Тест Соловея — Штрассена опирается на малую теорему Ферма (разд.
1.2) и свойства символа Якоби (разд. 1.9):

Страницы