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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 5. Метод решета числового поля 148
которое, очевидно выполняется в нашем случае, т.к. первый многочлен
в т. m равен n, а второй – нулю.
6. Выберем два положительных числа L
1
и L
2
, которые определяют
некоторую прямоугольную область SR = {1 ≤ b ≤ L
1
, −L
2
≤ a ≤ L
2
},
называемую областью просеивания (sieve region).
7. Пусть θ–корень многочлена f
1
(x). Рассмотрим кольцо многочленов
Z[θ] (практически корень θ не вычисляется, а используется только
для формального описания алгоритма). Определим алгебраическую
факторную базу F B1, состоящую из многочленов первого порядка
вида a − bθ с нормой (5.130), являющейся простым числом. Такие
многочлены являются простыми неразложимыми элементами в кольце
алгебраических целых поля K = Q[θ]. Абсолютные величины норм
многочленов из факторной базы F B
1
ограничим сверху некоторой
константой B
1
.
8. Одновременно определим рациональную факторную базу F B
2
,
состоящую из всех простых чисел, ограниченных сверху второй
константой B
2
.
9. Напомним, что произвольный элемент a кольца K называется
квадратичным вычетом, если найдется элемент x ∈ K такой, что
x
2
= a. Чтобы иметь возможность проверять на заключительной
стадии алгоритма, является ли найденный в ходе просеивания
многочлен полным квадратом, определим сравнительно небольшое
множество многочленов 1 порядка c − dθ, норма которых также
является простым числом. Обозначим это множество как F B
3
.
Оно должно удовлетворять условию F B
1
∩ FB
3
= ∅ и называется
факторной базой квадратичных характеров (the Quadratic Character
Base).
10. Далее выполняется одновременное просеивание многочленов
{a − bθ | (a, b) ∈ SR} по факторной базе F B
1
и целых чисел
{a − bm | (a, b) ∈ SR} по факторной базе F B
2
c целью получения
Глава 5. Метод решета числового поля                                 148

     которое, очевидно выполняется в нашем случае, т.к. первый многочлен
     в т. m равен n, а второй – нулю.

  6. Выберем два положительных числа L1 и L2 , которые определяют
     некоторую прямоугольную область SR = {1 ≤ b ≤ L1 , −L2 ≤ a ≤ L2 },
     называемую областью просеивания (sieve region).

  7. Пусть θ –корень многочлена f1 (x). Рассмотрим кольцо многочленов
     Z[θ] (практически корень θ не вычисляется, а используется только
     для формального описания алгоритма). Определим алгебраическую
     факторную базу F B1, состоящую из многочленов первого порядка
     вида a − bθ с нормой (5.130), являющейся простым числом. Такие
     многочлены являются простыми неразложимыми элементами в кольце
     алгебраических целых поля K = Q[θ]. Абсолютные величины норм
     многочленов из факторной базы F B1 ограничим сверху некоторой
     константой B1 .

  8. Одновременно определим рациональную факторную базу            F B2 ,
     состоящую из всех простых чисел, ограниченных сверху второй
     константой B2 .

  9. Напомним, что произвольный элемент a кольца K называется
     квадратичным вычетом, если найдется элемент x ∈ K такой, что
     x2 = a. Чтобы иметь возможность проверять на заключительной
     стадии алгоритма, является ли найденный в ходе просеивания
     многочлен полным квадратом, определим сравнительно небольшое
     множество многочленов 1 порядка c − dθ , норма которых также
     является простым числом. Обозначим это множество как F B3 .
     Оно должно удовлетворять условию F B1 ∩ F B3 = ∅ и называется
     факторной базой квадратичных характеров (the Quadratic Character
     Base).

 10. Далее    выполняется    одновременное    просеивание   многочленов
     {a − bθ | (a, b) ∈ SR} по факторной базе F B1 и целых чисел
     {a − bm | (a, b) ∈ SR} по факторной базе F B2 c целью получения

Страницы