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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 4. Метод квадратичного решета 142
что позволяет быстро вычислить все требуемые значения b по найденным
значениям B
i
.
Идея самоинициализирующегося метода решета была предложена
Померансом, Смитом и Тулером в 1988 ([48]). Вильям Харт (William Hart)
разработал пакет программ SIMPQS для реализации этого метода (доступен
код на сайте http://www.friedspace.com/QS), использующий библиотеку
работы с длинными числами GMP).
4.10. Метод Занга (Zhang’ Special QS)
Метод Занга (Zhang’ Special Quadratic Sieve) был разработан в 1998
г. ([55]). Идея этого метода состояла в использовании многочленов более
высокой степени, чем квадратные, также являющихся полными квадратными
по модулю n. Пусть n–факторизуемое число, а m–натуральное число, равное
примерно n
1/3
. Разложим число n в m-й системе координат:
n = m
3
+ a
2
m
2
+ a
1
+ a
0
. (4.123)
Разложение считается более хорошим, если коэффициенты a
i
принимают меньшие значения по абсолютной величине. Выбор m позволяет
изменять значения коэффициентов. Пусть b
2
, b
1
, b
0
– изменяемые параметры
по множеству Z, и рассмотрим
x = b
2
m
2
+ b
1
m + b
0
. (4.124)
Имеем следующие соотношения:
m
3
≡ −a
2
m
2
− a
1
m − a
0
( mod n)
m
4
≡ (a
2
2
− a
1
)m
2
+ (a
1
a
2
− a
0
)m + a
0
a
2
( mod n),
(4.125)
откуда получим,
x
2
≡ c
2
m
2
+ c
1
m + c
0
, ( mod n), (4.126)
Глава 4. Метод квадратичного решета                                   142

что позволяет быстро вычислить все требуемые значения b по найденным
значениям Bi .
      Идея самоинициализирующегося метода решета была предложена
Померансом, Смитом и Тулером в 1988 ([48]). Вильям Харт (William Hart)
разработал пакет программ SIMPQS для реализации этого метода (доступен
код на сайте http://www.friedspace.com/QS), использующий библиотеку
работы с длинными числами GMP).


4.10. Метод Занга (Zhang’ Special QS)
      Метод Занга (Zhang’ Special Quadratic Sieve) был разработан в 1998
г. ([55]). Идея этого метода состояла в использовании многочленов более
высокой степени, чем квадратные, также являющихся полными квадратными
по модулю n. Пусть n–факторизуемое число, а m–натуральное число, равное
примерно n1/3 . Разложим число n в m-й системе координат:

   n = m3 + a2 m2 + a1 + a0 .                                      (4.123)

      Разложение считается более хорошим, если коэффициенты             ai
принимают меньшие значения по абсолютной величине. Выбор m позволяет
изменять значения коэффициентов. Пусть b2 , b1 , b0 – изменяемые параметры
по множеству Z, и рассмотрим

   x = b2 m2 + b1 m + b0 .                                         (4.124)

      Имеем следующие соотношения:

    m3 ≡ −a2 m2 − a1 m − a0 ( mod n)
    m4 ≡ (a22 − a1 )m2 + (a1 a2 − a0 )m + a0 a2 ( mod n),
                                                                   (4.125)
откуда получим,

  x2 ≡ c2 m2 + c1 m + c0 , ( mod n),                               (4.126)

Страницы