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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 5. Метод решета числового поля 174
простым модулям:
α
i
=
X
small p
1 − r(F
i
, p)
p
p + 1
log p
p − 1
для i ∈ {1, 2}, (5.158)
Второй сомножитель в интеграле (5.157) мало зависит от выбора параметров
полинома f
1
, поэтому им можно пренебречь. Дальнейшее упрощение состоит
в рассмотрении выражения
α
1
+
1
2
log
Z
A
F
2
1
(x, y)dxdy
, (5.159)
которое надо минимизировать в отличие от предыдущих мер.
Таким образом, в алгоритме Кляйнъюнга перебираются всевозможные
полиномы f
1
(x), удовлетворяющие условию n = p
d
· f
1
(m/p) и ищутся тот,
который доставляет минимум выражению (5.159). Приведем выражение для
наилучшего полинома для числа RSA-512, найденное по этому алгоритму:
f
1
(x) = 498520x
5
+ 15578368316860x
4
− 513748876280490487x
3
−
−1021157413079535703297344x
2
− 3989311146723167867825129900x+
+14658919460374074323550710377995600,
f
2
(x) = 8794555574829559x − 293947565389650342960556270613.
В качестве критики этого подхода отметим, что указанная мера
зависит от области просеивания, вид которой существенно влияет на
количество генерируемых гладких пар. Например, вдоль прямой x
0
= b/a,
где x
0
— действительный корень полинома число гладких пар значительно
возрастает. В статье Ш.Т.Ишмухаметова, Д.Б.Зиятдинова и Р.Г.Рубцовой [68]
предлагается другой подход к оценке полиномов.
Изменения в базовом алгоритме GNFS
Обсудим изменения, которые следует внести в базовый алгоритм GNFS,
описанный на стр.146, при изменении параметров c
d
и m
2
= p:
1. Эти изменения касаются, в первую очередь, однородных
многочленов F
1
(a, b) и F
2
(a, b), которые в новом варианте получают
вид :
F
1
(a, b) = c
d
a
d
+c
d−1
a
d−1
b+ ... + c
0
b
d
F
2
(a, b) = am
2
−bm
1
. (5.160)
Глава 5. Метод решета числового поля                                            174

простым модулям:
       X                   p
                              
                                log p
  αi =       1 − r(Fi , p)            для i ∈ {1, 2},                        (5.158)
                           p+1 p−1
         small p

Второй сомножитель в интеграле (5.157) мало зависит от выбора параметров
полинома f1 , поэтому им можно пренебречь. Дальнейшее упрощение состоит
в рассмотрении выражения
                        Z                 
                   1
               α1 + log      F12 (x, y)dxdy ,                                (5.159)
                   2      A
которое надо минимизировать в отличие от предыдущих мер.
        Таким образом, в алгоритме Кляйнъюнга перебираются всевозможные
полиномы f1 (x), удовлетворяющие условию n = pd · f1 (m/p) и ищутся тот,
который доставляет минимум выражению (5.159). Приведем выражение для
наилучшего полинома для числа RSA-512, найденное по этому алгоритму:
 f1 (x) = 498520x5 + 15578368316860x4 − 513748876280490487x3 −
        −1021157413079535703297344x2 − 3989311146723167867825129900x+
        +14658919460374074323550710377995600,
 f2 (x) = 8794555574829559x − 293947565389650342960556270613.
        В качестве критики этого подхода отметим, что указанная мера
зависит от области просеивания, вид которой существенно влияет на
количество генерируемых гладких пар. Например, вдоль прямой x0 = b/a,
где x0 — действительный корень полинома число гладких пар значительно
возрастает. В статье Ш.Т.Ишмухаметова, Д.Б.Зиятдинова и Р.Г.Рубцовой [68]
предлагается другой подход к оценке полиномов.

Изменения в базовом алгоритме GNFS

Обсудим изменения, которые следует внести в базовый алгоритм GNFS,
описанный на стр.146, при изменении параметров cd и m2 = p:
        1.   Эти    изменения      касаются,    в   первую    очередь,   однородных
многочленов F1 (a, b) и F2 (a, b), которые в новом варианте получают
вид :

 F1 (a, b) = cd ad +cd−1 ad−1 b+ ... + c0 bd   F2 (a, b) = am2 −bm1 .        (5.160)

Страницы