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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 5. Метод решета числового поля 151
многочлена x
i
(x − m). Обобщая эту идею, можно заменить, что сложение
f
1
(x) с полиномом вида g(x) · f
2
(x), где g(x)–произвольный многочлен с
целыми коэффициентами, сохраняет свойство (5.131).
Таким образом, изменение основания m и добавление (вычитание) из
f
1
(x) полиномов вида g(x) · f
2
(x) позволяет порождать многочисленные
допустимые полиномиальные пары (f
1
(x), f
2
(x)), среди которых можно
выбрать пару с наименьшим размахом коэффициентов. Проблема выбора
наилучшего полинома подробно исследуется в диссертации Б.Мерфи ([41]).
Мы обратимся к этой проблеме в разделе 5.7. В нашем примере остановим
свой выбор на m = 31 и полиноме разложения
n = m
3
+ 15m
2
+ 29m + 8.
Объясним на этом примере все последующие алгоритмы метода
числового решета.
5.2. Выбор факторных баз
Рассмотрим сначала процедуру построения рациональной факторной
базы F B
2
. Эта база будет использоваться для разложения чисел вида a−bm
в множестве Z, поэтому множество FB
2
определяется равным множеству
всех простых чисел, ограниченных сверху константой B
1
. Граница B
1
для рекордных разложений доходит до гигантских значений 10
6
− 10
7
.
В нашем примере для n = 45113 определим B
1
= 30 и F B
2
=
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29}, состоящим из 10 простых чисел.
Построение алгебраической факторной базы
Алгебраическая факторная база состоит из линейных многочленов
c −dθ, порождающих простые идеалы в кольце целых алгебраических чисел
Z
K
. Построение такой факторной базы является очень сложной задачей,
однако, следующая теорема (М. Бригс[12], теор.3.1.7) позволяет перейти от
неприводимых многочленов и порождаемых ими простых идеалов к парам
натуральных чисел (p, r):
Глава 5. Метод решета числового поля                                   151

многочлена xi (x − m). Обобщая эту идею, можно заменить, что сложение
f1 (x) с полиномом вида g(x) · f2 (x), где g(x)–произвольный многочлен с
целыми коэффициентами, сохраняет свойство (5.131).
      Таким образом, изменение основания m и добавление (вычитание) из
f1 (x) полиномов вида g(x) · f2 (x) позволяет порождать многочисленные
допустимые полиномиальные пары (f1 (x), f2 (x)), среди которых можно
выбрать пару с наименьшим размахом коэффициентов. Проблема выбора
наилучшего полинома подробно исследуется в диссертации Б.Мерфи ([41]).
Мы обратимся к этой проблеме в разделе 5.7. В нашем примере остановим
свой выбор на m = 31 и полиноме разложения

       n = m3 + 15m2 + 29m + 8.

      Объясним на этом примере все последующие алгоритмы метода
числового решета.


5.2. Выбор факторных баз
     Рассмотрим сначала процедуру построения рациональной факторной
базы F B2 . Эта база будет использоваться для разложения чисел вида a − bm
в множестве Z, поэтому множество F B2 определяется равным множеству
всех простых чисел, ограниченных сверху константой B1 . Граница B1
для рекордных разложений доходит до гигантских значений 106 − 107 .
В нашем примере для n = 45113 определим B1 = 30 и F B2 =
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29}, состоящим из 10 простых чисел.

Построение алгебраической факторной базы

      Алгебраическая факторная база состоит из линейных многочленов
c − dθ , порождающих простые идеалы в кольце целых алгебраических чисел
Z K . Построение такой факторной базы является очень сложной задачей,
однако, следующая теорема (М. Бригс[12], теор.3.1.7) позволяет перейти от
неприводимых многочленов и порождаемых ими простых идеалов к парам
натуральных чисел (p, r):

Страницы