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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 5. Метод решета числового поля 145
5. Метод решета числового поля
В этой главе мы дадим описание самого быстрого на сегодняшний день
алгоритма факторизации натуральных чисел – метода решета числового
поля. Идея этого метода принадлежит Джону Полларду, который в 1988
г. распространил среди коллег письмо (см. [44]), в котором предложил
выполнять просеивание не в кольце целых чисел Z , как в методе
квадратичного решета, а в алгебраическом числовом поле. Первоначально
этот метод можно было использовать только для разложения чисел
специального вида 2
n
± c, поэтому метод получит название «специального
решета числового поля» (the Special Number Field Sieve SFNS).
Практическая реализация идеи Полларда была выполнена
А. Ленстрой, Х. Ленстрой, М. Манассе и Д. Поллардом (см.[32]) в
1990 г., когда с помощью этого метода было факторизовано 9–е число
Ферма 2
2
9
. Также были факторизованы некоторые числа вида b
c
± 1 из
проекта Каннингама (см.[11]).
Вскоре было замечено, идею Полларда можно использовать и для
разложения произвольных чисел. Этот метод получил название обобщенного
решета числового поля (the General Number Field Sieve GFNS). Была
найдена эвристическая оценка нового метода, которая равнялась L
n
(1/3, c)
в терминах функции L
n
(α, c) (4.114), т.е. множитель α был уменьшен со
значения α = 1/2 в методе квадратичного решета до α = 1/3 в решете
числового поля. Это обеспечило новому методу значительный выигрыш по
отношению ко всем другим ранее известным методам.
Сборник статей под редакцией А. Ленстры и Х. Ленстры [33],
опубликованный издательством Springer в 1993 г., подвел итоги раннего
развития этого метода. Перечислим основные источники литературы, в
которых можно найти описание метода решета числового поля: [12], [13],
[21], [23], [32], [46], [47], [64].
Опишем в следующем разделе основные идеи GNFS. Мы будем
придерживаться, в основном, книги Бригса [12].
Глава 5. Метод решета числового поля                                     145

5. Метод решета числового поля


В этой главе мы дадим описание самого быстрого на сегодняшний день
алгоритма факторизации натуральных чисел – метода решета числового
поля. Идея этого метода принадлежит Джону Полларду, который в 1988
г. распространил среди коллег письмо (см. [44]), в котором предложил
выполнять просеивание не в кольце целых чисел Z , как в методе
квадратичного решета, а в алгебраическом числовом поле. Первоначально
этот метод можно было использовать только для разложения чисел
специального вида 2n ± c, поэтому метод получит название «специального
решета числового поля» (the Special Number Field Sieve SFNS).
        Практическая         реализация   идеи   Полларда   была   выполнена
А. Ленстрой, Х. Ленстрой, М. Манассе и Д. Поллардом (см.[32]) в
1990 г., когда с помощью этого метода было факторизовано 9–е число
            9
Ферма 22 . Также были факторизованы некоторые числа вида b c ± 1 из
проекта Каннингама (см.[11]).
        Вскоре было замечено, идею Полларда можно использовать и для
разложения произвольных чисел. Этот метод получил название обобщенного
решета числового поля (the General Number Field Sieve GFNS). Была
найдена эвристическая оценка нового метода, которая равнялась Ln (1/3, c)
в терминах функции Ln (α, c) (4.114), т.е. множитель α был уменьшен со
значения α = 1/2 в методе квадратичного решета до α = 1/3 в решете
числового поля. Это обеспечило новому методу значительный выигрыш по
отношению ко всем другим ранее известным методам.
        Сборник статей под редакцией А. Ленстры и Х. Ленстры [33],
опубликованный издательством Springer в 1993 г., подвел итоги раннего
развития этого метода. Перечислим основные источники литературы, в
которых можно найти описание метода решета числового поля: [12], [13],
[21], [23], [32], [46], [47], [64].
        Опишем в следующем разделе основные идеи GNFS. Мы будем
придерживаться, в основном, книги Бригса [12].

Страницы