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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 5. Метод решета числового поля 173
Практическая реализация алгоритма Кляйнъюнга
В практической реализации алгоритма выбирается сначала параметр p как
произведение нескольких средних простых чисел p
i
, сравнимых с 1 по модулю
d. Потом следует выбрать пару (c
d
, m) в ходе итерационной процедуры
изменения параметра c
d
с некоторым шагом.
В рекордном разложении 512-битового числа RSA [15] степень
полинома была выбрана равной d = 5, параметр p равным произведению 7
простых чисел и вспомогательного множителя p
0
, а шаг перебора c
d
равным
60.
Для каждого значения c
d
решается сравнение (5.154). Если оно
разрешимо, то находится d решений x и рассматривается d соответствующих
значений для m таких, что разность n − a
d
m
d
имеет наименьшие значения
по абсолютной величине. Вычисляется коэффициент c
d−1
= (n − a
d
m
d
)/p,
и оставляются только те решения, для которых значение |c
d−1
| меньше
некоторой наперед выбранной границы.
Выбрав c
d−1
, можно вычислить c
d−2
с помощью реккурентных
формул (5.155). Здесь также есть небольшой выбор при выборе δ
i
. Если
старшие коэффициенты оказались большими по абсолютной величине, то нет
смысла их рассматривать, поэтому такие полиномы сразу отбрасываются, и
выполняется приращение очередной коэффициента c
d
.
Лучшим считается полином, у которого все коэффициенты принимают
небольшие по модулю значения, и кроме того, полином имеет много корней
по модулю небольших простых чисел. Последний фактор учесть достаточно
сложно, поскольку он достаточно случаен. В статье Кляйнъюнга [29]
приводится интегральная мера для числа гладких пар, попадающих в область
просеивания A:
6
π
2
Z
A
ρ
log F
1
(x, y) + α
1
log B
1
ρ
log F
2
(x, y) + α
2
log B
2
dxdy (5.157)
Здесь ρ обозначает функцию Дикмана-де Брюина (см.стр.129), коэффициент
6/π
2
оценивает долю пар (a, b) со взаимно-простыми аргументами, а
параметры α
i
введены для учета корней полиномов F
1
, F
2
по небольшим
Глава 5. Метод решета числового поля                                  173

Практическая реализация алгоритма Кляйнъюнга

В практической реализации алгоритма выбирается сначала параметр p как
произведение нескольких средних простых чисел pi , сравнимых с 1 по модулю
d. Потом следует выбрать пару (cd , m) в ходе итерационной процедуры
изменения параметра cd с некоторым шагом.
      В рекордном разложении 512-битового числа RSA [15] степень
полинома была выбрана равной d = 5, параметр p равным произведению 7
простых чисел и вспомогательного множителя p0 , а шаг перебора cd равным
60.
      Для каждого значения cd решается сравнение (5.154). Если оно
разрешимо, то находится d решений x и рассматривается d соответствующих
значений для m таких, что разность n − ad md имеет наименьшие значения
по абсолютной величине. Вычисляется коэффициент cd−1 = (n − ad md )/p,
и оставляются только те решения, для которых значение |cd−1 | меньше
некоторой наперед выбранной границы.
      Выбрав cd−1 , можно вычислить cd−2 с помощью реккурентных
формул (5.155). Здесь также есть небольшой выбор при выборе δi . Если
старшие коэффициенты оказались большими по абсолютной величине, то нет
смысла их рассматривать, поэтому такие полиномы сразу отбрасываются, и
выполняется приращение очередной коэффициента cd .
      Лучшим считается полином, у которого все коэффициенты принимают
небольшие по модулю значения, и кроме того, полином имеет много корней
по модулю небольших простых чисел. Последний фактор учесть достаточно
сложно, поскольку он достаточно случаен. В статье Кляйнъюнга [29]
приводится интегральная мера для числа гладких пар, попадающих в область
просеивания A:
    Z                                             
  6        log F1 (x, y) + α1     log F2 (x, y) + α2
       ρ                       ρ                       dxdy        (5.157)
 π2 A           log B1                 log B2

Здесь ρ обозначает функцию Дикмана-де Брюина (см.стр.129), коэффициент
6/π 2 оценивает долю пар (a, b) со взаимно-простыми аргументами, а
параметры αi введены для учета корней полиномов F1 , F2 по небольшим

Страницы