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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 5. Метод решета числового поля 155
Область просеивания представляет собой прямоугольник вида
SP = {(a, b) | 1 ≤ b ≤ L
2
; −L
1
≤ a ≤ L
1
}. (5.136)
Линейное просеивание выполняется в виде двойного цикла, в котором
внешней переменной является переменная b, принимающая последовательно
значения 1, 2, ..., L
2
, и с каждым значением b
1
выполняется внутренний
цикл по a, изменяющемся от −L
1
до L
1
.
Джон Поллард в работе [45], опубликованной в 1993 г., предложил
вместо линейного использовать решеточное просеивание, которое
заключается в том, что выбирается несколько больших p из пар (p, r),
содержащихся в алгебраической факторной базе. Такие p называются
специальными числами. Просеивание выполняется теперь не вдоль прямых
b = i, |a| ≤ L
1
, а вдоль прямых
L
p,r
= {(a, b) ∈ SR |a − br ≡ 0 ( mod p)}.
Смысл такого просеивания в том, что на указанной прямой значения
F
1
(a, b) ≡ 0 (mod p), т.е. делятся нацело на p, и можно выполнять
просеивание по значениям F
1
(a, b)/p, которые принимают заведомо
меньшие по модулю значения, чем исходные F
1
(a, b). Решеточное
просеивание позволяет в несколько раз увеличить эффективность
процедуры просеивания, однако область просеивания должна быть не
прямоугольником, а иметь более сложную форму, что усложняет процедуру.
Следует заметить, что в рекордных проектах разложениях
присутствуют обе эти стратегии, поскольку линейное просеивание
также дает много гладких пар на некоторых специально выбранных
прямых.
В работе ([67]) автор этой монографии со своими соавторами
предлагает другую организацию просеивания, рассматривая область
прилегающую к прямой a = x
0
b, где x
0
—действительный корень полинома
f
1
(x). Идея такого просеивания состоит в том, что вдоль действительного
корня значения полинома F
1
(a, b) растут на порядок медленнее, чем в
произвольном другом направлении.
Глава 5. Метод решета числового поля                                            155

Область просеивания представляет собой прямоугольник вида

    SP = {(a, b) | 1 ≤ b ≤ L2 ; −L1 ≤ a ≤ L1 }.                              (5.136)

      Линейное просеивание выполняется в виде двойного цикла, в котором
внешней переменной является переменная b, принимающая последовательно
значения 1, 2, ..., L2 , и с каждым значением b1 выполняется внутренний
цикл по a, изменяющемся от −L1 до L1 .
      Джон Поллард в работе [45], опубликованной в 1993 г., предложил
вместо    линейного    использовать         решеточное      просеивание,    которое
заключается в том, что выбирается несколько больших p из пар (p, r),
содержащихся в алгебраической факторной базе. Такие p называются
специальными числами. Просеивание выполняется теперь не вдоль прямых
b = i, |a| ≤ L1 , а вдоль прямых

    Lp,r = {(a, b) ∈ SR | a − br ≡ 0 ( mod p)}.

      Смысл такого просеивания в том, что на указанной прямой значения
F1 (a, b) ≡ 0 (mod p), т.е. делятся нацело на p, и можно выполнять
просеивание по значениям            F1 (a, b)/p, которые принимают заведомо
меньшие по модулю значения, чем исходные                     F1 (a, b). Решеточное
просеивание     позволяет     в    несколько    раз   увеличить       эффективность
процедуры просеивания, однако область просеивания должна быть не
прямоугольником, а иметь более сложную форму, что усложняет процедуру.
      Следует     заметить,       что   в   рекордных      проектах     разложениях
присутствуют     обе   эти    стратегии,      поскольку    линейное     просеивание
также дает много гладких пар на некоторых специально выбранных
прямых.
      В работе ([67]) автор этой монографии со своими соавторами
предлагает    другую   организацию          просеивания,   рассматривая     область
прилегающую к прямой a = x0 b, где x0 —действительный корень полинома
f1 (x). Идея такого просеивания состоит в том, что вдоль действительного
корня значения полинома F1 (a, b) растут на порядок медленнее, чем в
произвольном другом направлении.

Страницы