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

Глава 2. Криптостойкость RSA. Алгоритмы факторизации                                55

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

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


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

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

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

                                           ∏
                                           k
                                p+1=             qiai .
                                           i=1

Обозначим через B        =   max{qiai |1   ≤       i      ≤   k}. По-прежнему будем
называть натуральное число r B –степенно-гладким, если наибольшая
степень сомножителя pai i в разложении r на простые множители, не
превышает B . Таким образом, определенное выше число B является
наименьшим числом, для которого p + 1 является B –степенно-гладким.
Отметим, что поскольку p не известно, то и B так же не известно.
      Алгоритм Вильямса заключается в следующем:

  1. Выбираем некоторое число B , являющее верхней границей для
     рассматриваемых простых чисел и их степеней.