Processing math: 97%

Общий метод решета числового поля

Общий метод решета числового поля (, GNFS) — методфакторизации целых чисел. Является наиболее эффективным алгоритмомфакторизации чисел длиной более 110 десятичных знаков. Сложностьалгоритма оценивается эвристической формулой

exp((3649+o(1))(logn)13(loglogn)23)=Ln[13,3649]
 Метод является обобщением специального метода решета числового поля:тогда как последний позволяет факторизовать числа только некоторогоспециального вида, общий метод работает на множестве целых чисел, заисключением степеней простых чисел (которые факторизуются тривиальноизвлечением корней).

История


 В 1988 году английский математик описал новый метод факторизации целыхчисел специальной формы (2n±C), проиллюстрировав его разложениемседьмого числа Ферма F7=2128+1. В отличие от методаквадратичного решета, в котором просеивание выполняется в кольце всехцелых чисел, в методе предлагалось использовать кольцо целых чиселZ([23/2]) над числовым полем Q(23/2). Рукопись была приложенак письму, адресованному , также копии получили Ричард Брент, Дж.Бриллхарт, , и Х. Суяма. В этом письме Поллард предположил, что возможноэтот метод может быть использован для разложения девятого числа Ферма.
 В 1990 году А. Ленстра, Х. Ленстра, Марк Манассе и Поллард описалипервую крупномасштабную реализацию нового метода с некоторымиусовершенствованиями. Они показали, что на числах специального видаалгоритм работает быстрее, чем все остальные известные методыфакторизации. Также в работе обсуждается идея Джо Бухлера и КарлаПомеранса об усовершенствовании метода для разложения любых целых чисели приводятся наброски решения этой задачи.
 Позднее Леонард Макс Адлеман предложил использовать квадратичныйхарактер для нахождения квадратов в числовом поле. Это предоставилоальтернативное решение проблемы, поднятой Бухлером и Померансом, иулучшило предположительное время работы решета числового поля вприменении к числам не специального вида.
 В том же году А. Ленстра, Х. Ленстра, Манассе и Поллард представилиразложение девятого числа Ферма с помощью метода числового поля. Всоответствующей работе обсуждаются многие детали этого разложения.
 Наконец, в работе «Факторизация целых чисел с помощью решета числовогополя» Бухлер, Х. Ленстра и Померанс описали метод решета числового поляв применении к числам, которые не обязательно имеют специальный вид. Этареализация алгоритма содержала шаг, предполагающий вычисления сиспользованием чрезвычайно больших чисел. Джин-Марк Кувейгнес в своейработе описал способ обойти это.
 Итоги раннего развития метода подвёл сборник статей под редакций А.Ленстры и Х. Ленстры. В том числе сборник включал статью Бернштейна и А.Ленстры, описывающую очередную улучшенную реализацию алгоритма. Статьявошла в сборник под заголовком «Общий метод решета числового поля».

Сутьметода


 Метод решета числового поля (как специальный, так и общий) можнопредставить как усовершенствование более простого метода — методарационального решета, либо метода квадратичного решета. Подобные ималгоритмы требуют нахождение гладких чисел порядка n. Размерэтих чисел экспоненциально растёт с ростом n. Метод решета числовогополя, в свою очередь, требует нахождения гладких чиселсубэкспоненциального относительно n размера. Благодаря тому, что этичисла меньше, вероятность того, что число такого размера окажетсягладким выше, что и является причиной эффективности метода решетачислового поля. Для достижения ускорения вычислений в рамках методапроводятся в числовых полях, что усложняет алгоритм, по сравнению сболее простым рациональным решетом.

Основныепринципы



  • Метод факторизации Ферма для факторизации натуральных нечетных чисел n, состоящий в поиске таких целых чисел x и y, что x2y2=n, что ведет к разложению n=(xy)(x+y).
  • Нахождение подмножества множества целых чисел, произведение которых — квадрат
  • Составление факторной базы: набора {1,p1,p2,,pn}, где pi — простые числа такие, что piB для некоторого B.
  • Просеивание выполняется подобно решету Эратосфена (откуда метод и получил своё название). Решетом служат простые числа факторной базы и их степени. При просеивании число не «вычёркивается», а делится на число из решета. Если в результате число оказалось единицей, то оно B-гладкое.
  • Основная идея состоит в том, чтобы вместо перебора чисел и проверки, делятся ли их квадраты по модулю n на простые числа из факторной базы, перебираются простые числа из базы и сразу для всех чисел вида x2n проверяется, делятся ли они на это простое число или его степень.

Алгоритм


 Пусть n — нечетное составное число, которое требуется факторизовать.
 Выберем степень неприводимого многочлена d3 (при d=2 не будетвыигрыша в сравнении с методом квадратичного решета).
 Выберем целое m такое, чтоn1/(d+1)<m<n1/d, и разложимn по основанию m:

n=md+ad1md1++a0 (1)
 Свяжем с разложением (1) неприводимый в кольце Z[x] полиномовс целыми коэффициентами многочлен

f1(x)=xd+ad1xd1++a0
 Определим полином просеивания F1(a,b) как однородный многочлен отдвух переменных a и b:

F1(a,b)=bdf1(a/b)=ad+ad1ad1b+ad2ad1b2+...+a0bd(2)
 Определим второй полином f2(x)=xm и соответствующий однородныймногочлен F2(a,b)=abm.
 Выберем два положительных числа L1 и L2, определяющих областьпросеивания (англ. sieve region):

SR={1bL1,L2aL2}
 Пусть θ — корень f1(x). Рассмотрим кольцо полиномовZ[θ]. Определим множество, называемоеалгебраической факторной базой FB1, состоящее из многочленовпервого порядка вида abθ с нормой (2), являющейся простымчислом. Эти многочлены — простые неразложимиые в кольце алгебраическихцелых поля K=Q[θ]. Ограничим абсолютные значения нормполиномов из FB1 константой B1.
 Определим рациональную факторную базу FB2, состоящую из всехпростых чисел, ограниченных сверху константой B2.
 Определим множество FB3, называемое факторной базойквадратичных характеров. Это множество полиномов первого порядкаcdθ, норма которых - простое число. Должно выполнятьсяусловие FB1FB3=\empty.
 Выполним просеивание многочленов {abθ(a,b)SR} пофакторной базе FB1 и целых чисел {abm(a,b)SR} пофакторной базе FB2. В результате получим множество M, состоящее изгладких пар (a,b), то есть таких пар (a,b), что НОД(a,b) =1, полином и число abθ и abm раскладываются полностьюпо FB1 и FB2 соответственно.
 Найдём такое подмножество SM, что

(a,b)SNr(abθ)=H2,HZ;(a,b)S(abm)=B2,BZ
 Определим многочлен

g(θ)=f12(θ)(a,b)S(abθ)
 где f1(x) — производная f1(x)
 Многочлен g(θ) является полным квадратом в кольце полиномовZ(θ). Пусть тогда α(θ) есть корень изg(θ) и B — корень из B2.
 Строим отображение ϕ:θm, заменяя полиномα(θ) числом α(m). Это отображение является кольцевымгомоморфизмом кольца алгебраических целых чисел ZK в кольцоZ, откуда получаем соотношение:

A2=g(m)2ϕ(g(α))2ϕ(f12(θ)(a,b)S(abθ))f12(m)(a,b)S(abm)f12(m)C2(modn)
 Пусть B=f(m)C. Найдём пару чисел (A,B) таких, чтоA \equiv B \pmod n. Тогда найдём делитель числа n, вычисляя НОД(n, A± B), как это делается, например, в методе квадратичного решета.
 Подробное описание алгоритма можно найти, например, в и .

Реализации


 До 2007 года наиболее успешной реализацией считалось программноеобеспечение разработанное и распространяемое Центром математики иинформатики (CWI) в Нидерландах, распространявшееся под закрытойлицензией.
 В 2007 году реализовал часть алгоритма, занимающуюся окончательнойобработкой данных, так, что она работала быстрее версии CWI. Этот кодвходит в библиотеку msieve. Msieve написана Пападопулосом и другимиучастниками проекта на C и включает в себя реализации общего методарешета числового поля и квадратичного решета. Распространяется на правахобщественного достояния. Поддерживает распределенные вычисления.Последняя версия msieve может быть найдена насайте автора.
 Некоторые другие реализации общего метода решета числового поля:

  • NFS@Home - исследовательский проект, направленный на факторизацию больших чисел с помощью общего метода решета числового поля, использующий сеть из подключившихся к проекту компьютеров для просеивания.
  • GGNFS, распространяется под GPL.
  • pGNFS
  • factor by gnfs
  • CADO-NFS
  • kmGNFS

Достижения


 В 1996 году с помощью алгоритма было получено разложение числа RSA-130.Позднее с помощью метода были факторизованы, например, числа RSA-140, иRSA-155. На разложение последнего потребовалось более 8000 mips лет. 9мая 2005 года Ф. Бар, М. Бом, Йенс Франке и Т. Клейнжунг объявили, чтоони разложили число RSA-200, используя общий метод решета числовогополя.
 В 2009 году группе учёных из Швейцарии, Японии, Франции, Нидерландов,Германии и США удалось успешно вычислить данные, зашифрованные припомощи криптографического ключа стандарта RSA длиной 768 битов. Какследует из описания работы, вычисление значений ключа осуществлялосьобщим методом решета числового поля. По словам исследователей, после ихработы в качестве надежной системы шифрования можно рассматривать толькоRSA-ключи длиной 1024 бита и более.