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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 4. Метод квадратичного решета 143
где
c
2
= (a
2
2
− a
1
)b
2
2
− 2a
2
b
1
b
2
+ b
2
1
+ 2b
0
b
2
c
1
= (a
1
a
2
− a
0
)b
2
2
− 2a
1
b
1
b
2
+ b
2
1
+ 2b
0
b
1
c
0
= a
0
a
2
b
2
2
− 2a
0
b
1
b
2
+ b
2
0
.
Подберем параметры b
0
, b
1
, b
2
так, чтобы коэффициент c
2
был равен нулю.
Для этого положим
b
2
= 2, b
1
= 2t, b
0
= a
1
− a
2
2
+ 2a
2
t − t
2
, (4.127)
где t принимает произвольное целые значения. Подставляя значения (4.127)
в формулы (4.125), получим эквивалентность
x(t)
2
≡ y(t) ( mod n)
где
x(t) = 2m
2
+ 2mt + a
1
− a
2
2
+ 2a
2
t − t
2
y(t) = (4a
1
a
2
− 4a
0
− (4a
1
+ 4a
2
2
) t + 8a
2
t
2
− 4t
3
) m+
+4a
0
a
2
− 8a
0
t + (a
1
− a
2
2
+ 2a
2
t − t
2
)
2
).
В этом случае можно, меняя значения t на некотором интервале
просеивания, искать пары чисел (x, y) так же, как в обычном методе
квадратичного решета.
Метод Занга существенно зависит от значений коэффициентов в
формуле (4.123), поэтому имеет ограниченную область применения. Его
можно использовать для разложения чисел специального вида.
Рассмотрим, например, число n = 2
601
− 1. Используя метод
разложения, зависящий от младшего сомножителя, например, метод
эллиптических кривых, найдем два младших делителя n:
n = 3607 · 64 863 527 · n
0
,
где n
0
–составное 170-разрядное десятичное число. Рассмотрим число
4n = 2
603
− 4 = (2
201
)
3
− 4 = m
3
− 4,
где m = 2
201
. Тогда формулы для x(t), y(t) приобретают вид:
x(t) = 2m
2
+ 2mt − t
2
, y(t) = (16 − 4t
3
)m + 32t + t
4
).
Глава 4. Метод квадратичного решета                                         143

где

      c2 = (a22 − a1 )b22 − 2a2 b1 b2 + b21 + 2b0 b2
      c1 = (a1 a2 − a0 )b22 − 2a1 b1 b2 + b21 + 2b0 b1
      c0 = a0 a2 b22 − 2a0 b1 b2 + b20 .
Подберем параметры b0 , b1 , b2 так, чтобы коэффициент c2 был равен нулю.
Для этого положим

  b2 = 2,     b1 = 2t,     b0 = a1 − a22 + 2a2 t − t2 ,                  (4.127)

где t принимает произвольное целые значения. Подставляя значения (4.127)
в формулы (4.125), получим эквивалентность

             x(t)2 ≡ y(t) ( mod n)

где
            x(t) = 2m2 + 2mt + a1 − a22 + 2a2 t − t2
            y(t) = (4a1 a2 − 4a0 − (4a1 + 4a22 ) t + 8a2 t2 − 4t3 ) m+
            +4a0 a2 − 8a0 t + (a1 − a22 + 2a2 t − t2 )2 ).
        В этом случае можно, меняя значения t на некотором интервале
просеивания, искать пары чисел (x, y) так же, как в обычном методе
квадратичного решета.
        Метод Занга существенно зависит от значений коэффициентов в
формуле (4.123), поэтому имеет ограниченную область применения. Его
можно использовать для разложения чисел специального вида.
        Рассмотрим, например, число n = 2601 − 1. Используя метод
разложения, зависящий от младшего сомножителя, например, метод
эллиптических кривых, найдем два младших делителя n:

       n = 3607 · 64 863 527 · n0 ,

где n0 –составное 170-разрядное десятичное число. Рассмотрим число

      4n = 2603 − 4 = (2201 )3 − 4 = m3 − 4,

где m = 2201 . Тогда формулы для x(t), y(t) приобретают вид:

 x(t) = 2m2 + 2mt − t2 ,          y(t) = (16 − 4t3 )m + 32t + t4 ).

Страницы