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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 5. Метод решета числового поля 150
Определив B = f
0
(m) · C , найдем пару целых чисел (A, B),
удовлетворяющих условию
A
2
≡ B
2
( mod n).
Теперь можно найти делитель числа n так же, как в методе
квадратичного решета, вычисляя Н.О.Д.(n, A ± B).
В следующей части мы дадим более подробное описание основных
шагов метода решета числового поля, выполнив все необходимые расчеты
для числа n = 45113. Пример взят из книги М.Бриггса [12].
Пример
Найти разложения числа n = 45 113. Вычислим n
1/3
= 35, 4..., и
определим m = 35. Раскладывая n в m–й системе исчисления, получим
n = m
3
+ m
2
+ 28m + 33.
Получившийся кубический многочлен имеет большие коэффициенты,
близкие к максимальному значению m − 1 = 34. Вычтем m из последнего
коэффициента, одновременно добавляя 1 к коэффициенту при m в 1-й
степени. Получим:
n = m
3
+ m
2
+ 29m − 2.
Вычтем m из предпоследнего коэффициента, одновременно добавляя
1 к коэффициенту при m в квадрате. Получим:
n = m
3
+ 2m
2
− 6m − 2.
Такой многочлен выглядит намного лучше с точки зрения меньшего
роста значений F
1
(a, b) в области просеивания, что позволит найти больше
гладких чисел при неизменном размере области просеивания. Меняя также
основание m от значений m
1/(d+1)
до m
1/d
, можно также менять значения
коэффициентов.
Операция уменьшения коэффициента a
i
на величину m с
последующим добавлением 1 к a
i+1
, эквивалентна добавления к f
1
(x)
Глава 5. Метод решета числового поля                                     150

      Определив B      = f 0 (m) · C , найдем пару целых чисел (A, B),
удовлетворяющих условию

          A2 ≡ B 2 ( mod n).

      Теперь можно найти делитель числа n так же, как в методе
квадратичного решета, вычисляя Н.О.Д.(n, A ± B).
      В следующей части мы дадим более подробное описание основных
шагов метода решета числового поля, выполнив все необходимые расчеты
для числа n = 45113. Пример взят из книги М.Бриггса [12].

     Пример

      Найти разложения числа n = 45 113. Вычислим n1/3 = 35, 4..., и
определим m = 35. Раскладывая n в m–й системе исчисления, получим

       n = m3 + m2 + 28m + 33.

      Получившийся кубический многочлен имеет большие коэффициенты,
близкие к максимальному значению m − 1 = 34. Вычтем m из последнего
коэффициента, одновременно добавляя 1 к коэффициенту при m в 1-й
степени. Получим:

       n = m3 + m2 + 29m − 2.

      Вычтем m из предпоследнего коэффициента, одновременно добавляя
1 к коэффициенту при m в квадрате. Получим:

       n = m3 + 2m2 − 6m − 2.

      Такой многочлен выглядит намного лучше с точки зрения меньшего
роста значений F1 (a, b) в области просеивания, что позволит найти больше
гладких чисел при неизменном размере области просеивания. Меняя также
основание m от значений m1/(d+1) до m1/d , можно также менять значения
коэффициентов.
      Операция      уменьшения   коэффициента   ai   на   величину   m     с
последующим добавлением 1 к ai+1 , эквивалентна добавления к f1 (x)

Страницы