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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Простые алгоритмы факторизации 60
Н.О.Д.(n, с
i
−1), где c
i
= b
q
i
. Монтгомери предложил объединять несколько
соседних элементов c
i
в блоки G
j
и вычислять сначала произведение h =
Q
(c
i
−1) mod n для всех c
i
∈ G
j
, а потом Н.О.Д.(n, h). Если Н.О.Д.(n, с
i
−
1) > 1, то таковым будет и Н.О.Д.(n, h). Эти и другие улучшения, найденные
Монтгомери, позволяют в несколько раз сократить общее время работы
алгоритма.
На сайте www.loria.fr/∼zimmerma/records/Pminus1.html можно найти
таблицу рекордов разложения натуральных чисел, установленных с помощью
(p − 1)–метода Полларда.
Упражнение.
Сформируйте множество E
n
всех составных чисел n одинаковой
длины, являющихся произведением двух простых чисел. Найдите для
каждого числа n математическое ожидание M[k] наименьшего показателя
k для множества элементов a < p, где p– наименьший делитель n.
Распределите все числа из множества E
n
в классы в зависимости от значения
M[k]. Сделайте вывод о доле составных чисел, которые могут быть быстро
разложены в произведение простых сомножителей с помощью (p−1)–метода
Полларда.
В главе 2 мы увидим, что идея (p − 1)-метода Полларда была
использована Х.Ленстрой для построения нового более быстрого метода
факторизации с использованием эллиптических кривых.
2.3. (p + 1)–метод Вильямса
Определение. Последовательностью Люка (Lucas) назовем
реккурентную последовательность u
n
, определяемую соотношениями:
u
0
= 0, u
1
= u, u
n+1
= P · u
n
− Q · u
n−1
, (2.26)
где P , Q – фиксированные целые числа.
(p+1)–метод Вильямса (Williams) похож на (p−1)–метод Полларда и
основан на предположении гладкости числа p+1. Пусть p–простой делитель
Глава 2. Простые алгоритмы факторизации                                  60

Н.О.Д.(n, сi − 1), где ci = bqi . Монтгомери предложил объединять несколько
соседних элементов ci в блоки Gj и вычислять сначала произведение h =
Q
  (ci −1) mod n для всех ci ∈ Gj , а потом Н.О.Д.(n, h). Если Н.О.Д.(n, сi −
1) > 1, то таковым будет и Н.О.Д.(n, h). Эти и другие улучшения, найденные
Монтгомери, позволяют в несколько раз сократить общее время работы
алгоритма.
      На сайте www.loria.fr/∼zimmerma/records/Pminus1.html можно найти
таблицу рекордов разложения натуральных чисел, установленных с помощью
(p − 1)–метода Полларда.

Упражнение.

      Сформируйте множество En всех составных чисел n одинаковой
длины, являющихся произведением двух простых чисел. Найдите для
каждого числа n математическое ожидание M [k] наименьшего показателя
k для множества элементов a < p, где p– наименьший делитель n.
Распределите все числа из множества En в классы в зависимости от значения
M [k]. Сделайте вывод о доле составных чисел, которые могут быть быстро
разложены в произведение простых сомножителей с помощью (p−1)–метода
Полларда.

      В главе 2 мы увидим, что идея (p − 1)-метода Полларда была
использована Х.Ленстрой для построения нового более быстрого метода
факторизации с использованием эллиптических кривых.


2.3. (p + 1)–метод Вильямса
        Определение.    Последовательностью       Люка    (Lucas)   назовем
реккурентную последовательность un , определяемую соотношениями:

     u0 = 0, u1 = u, un+1 = P · un − Q · un−1 ,                       (2.26)

где P , Q – фиксированные целые числа.
      (p + 1)–метод Вильямса (Williams) похож на (p − 1)–метод Полларда и
основан на предположении гладкости числа p + 1. Пусть p–простой делитель

Страницы