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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 4. Метод квадратичного решета 138
y
i
= g(x
i
), −L ≤ x
i
≤ L, с одинаковым значением множителя P
x
. Тогда,
можно добавить k − 1 новых чисел вида
g
1
= y
1
· y
2
, g
2
= y
1
· y
3
, ..., g
k−1
= y
1
· y
k
,
к множеству гладких чисел, поскольку каждое g
j
= P
2
x
· C
1
· C
j+1
, и,
значит, может использоваться на следующем этапе для построения системы
линейных уравнений.
Отметим, что дополнительное время, необходимое для сортировки
полугладких элементов, является ничтожно малым на фоне полного времени
просеивания, а выигрыш является значительным, поскольку не меняя
размерности факторной базы мы можем получать большее число гладких
чисел. Таким образом, используя вариацию больших множителей, можно
увеличить выход гладких чисел на единицу простого числа факторной базы,
что позволяет уменьшить границу гладкости B для факторной базы и
уменьшить все основные затраты по поиску решения.
Граница B
2
, предложенная для поиска полугладких чисел, является
слишком большой, и вероятность того, что найдутся два полугладких числа с
одинаковым множителем P
x
, значительно уменьшается с ростом P
x
, поэтому
многие практические реализации квадратичного решета ограничивали поиск
полугладких чисел на значительно меньшем интервале, например, на
интервале [B; kB], где множитель k находится в пределах от 10 до 100.
При разложении тестового 129-разрядного числа, предложенного
создателями RSA, Х. Ленстра и М. Манассе в 1994 г. использовали
дальнейшее развитие идеи LPV с двумя большими множителями вместо
одного. Хотя такая реализация требует намного больше дополнительной
работы, но обеспечивает больше возможностей для выбора полугладких
чисел. В этом варианте граница полугладкости может быть доведена
(хотя бы теоретически) до B
3
, и рассматриваются числа, имеющие либо
простой множитель в интервале [B; B
2
], либо составной множитель в
интервале [B
2
; B
3
]. Для проверки того, что число с множителем в интервале
[B
2
; B
3
] является составным, используется самая простая проверка вида
2
y−1
6≡ y метода Ферма. Если число y не проходит эту проверку, то
Глава 4. Метод квадратичного решета                                      138

yi = g(xi ), −L ≤ xi ≤ L, с одинаковым значением множителя Px . Тогда,
можно добавить k − 1 новых чисел вида

g1 = y1 · y2 , g2 = y1 · y3 , ..., gk−1 = y1 · yk ,

к множеству гладких чисел, поскольку каждое gj = Px2 · C1 · Cj+1 , и,
значит, может использоваться на следующем этапе для построения системы
линейных уравнений.
        Отметим, что дополнительное время, необходимое для сортировки
полугладких элементов, является ничтожно малым на фоне полного времени
просеивания, а выигрыш является значительным, поскольку не меняя
размерности факторной базы мы можем получать большее число гладких
чисел. Таким образом, используя вариацию больших множителей, можно
увеличить выход гладких чисел на единицу простого числа факторной базы,
что позволяет уменьшить границу гладкости B для факторной базы и
уменьшить все основные затраты по поиску решения.
        Граница B 2 , предложенная для поиска полугладких чисел, является
слишком большой, и вероятность того, что найдутся два полугладких числа с
одинаковым множителем Px , значительно уменьшается с ростом Px , поэтому
многие практические реализации квадратичного решета ограничивали поиск
полугладких чисел на значительно меньшем интервале, например, на
интервале [B; kB], где множитель k находится в пределах от 10 до 100.
        При разложении тестового 129-разрядного числа, предложенного
создателями RSA, Х. Ленстра и М. Манассе в 1994 г. использовали
дальнейшее развитие идеи LPV с двумя большими множителями вместо
одного. Хотя такая реализация требует намного больше дополнительной
работы, но обеспечивает больше возможностей для выбора полугладких
чисел. В этом варианте граница полугладкости может быть доведена
(хотя бы теоретически) до B 3 , и рассматриваются числа, имеющие либо
простой множитель в интервале [B; B 2 ], либо составной множитель в
интервале [B 2 ; B 3 ]. Для проверки того, что число с множителем в интервале
[B 2 ; B 3 ] является составным, используется самая простая проверка вида
2y−1 6≡ y метода Ферма. Если число y не проходит эту проверку, то

Страницы