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

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

$\exp ((\sqrt[3]{\frac{64}{9}}+o(1))(\log n{)}^{\frac{1}{3}}(\log \log n{)}^{\frac{2}{3}})=L_n[\frac{1}{3},\sqrt[3]{\frac{64}{9}}]$

Метод является обобщением специального метода решета числового поля: тогда как последний позволяет факторизовать числа только некоторого специального вида, общий метод работает на множестве целых чисел, за исключением степеней простых чисел (которые факторизуются тривиально извлечением корней).

История

В 1988 году английский математик Шаблон:Нп1 описал новый метод факторизации целых чисел специальной формы ($2^n\pm C$), проиллюстрировав его разложением седьмого числа Ферма $F_7=2^{128}+1$. В отличие от метода квадратичного решета, в котором просеивание выполняется в кольце всех целых чисел, в методе предлагалось использовать кольцо целых чисел $Z([2^{3/2}])$ над числовым полем $Q(2^{3/2})$. Рукопись была приложена к письму, адресованному Шаблон:Iw, также копии получили Ричард Брент, Шаблон:Iw, Хендрик Ленстра, Шаблон:Iw и Х. Суяма. В этом письме Поллард предположил, что возможно этот метод может быть использован для разложения девятого числа Ферма.

В 1990 году А. Ленстра, Х. Ленстра, Марк Манассе и Поллард описали первую крупномасштабную реализацию нового метода с некоторыми усовершенствованиями. Они показали, что на числах специального вида алгоритм работает быстрее, чем все остальные известные методы факторизации. Также в работе обсуждается идея Джо Бухлера и Карла Померанса об усовершенствовании метода для разложения любых целых чисел и приводятся наброски решения этой задачи.

Позднее Леонард Макс Адлеман предложил использовать квадратичный характер для нахождения квадратов в числовом поле. Это предоставило альтернативное решение проблемы, поднятой Бухлером и Померансом, и улучшило предположительное время работы решета числового поля в применении к числам не специального вида.

В том же году А. Ленстра, Х. Ленстра, Манассе и Поллард представили разложение девятого числа Ферма с помощью метода числового поля. В соответствующей работе обсуждаются многие детали этого разложения.

Наконец, в работе «Факторизация целых чисел с помощью решета числового поля» Бухлер, Х. Ленстра и Померанс описали метод решета числового поля в применении к числам, которые не обязательно имеют специальный вид. Эта реализация алгоритма содержала шаг, предполагающий вычисления с использованием чрезвычайно больших чисел. Джин-Марк Кувейгнес в своей работе описал способ обойти это.

Итоги раннего развития метода подвёл сборник статей под редакций А. Ленстры и Х. Ленстры. В том числе сборник включал статью Бернштейна и А. Ленстры, описывающую очередную улучшенную реализацию алгоритма. Статья вошла в сборник под заголовком «Общий метод решета числового поля».

Суть метода

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

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

• Метод факторизации Ферма для факторизации натуральных нечетных чисел n, состоящий в поиске таких целых чисел x и y, что $x^2-y^2=n$, что ведет к разложению $n=(x-y)\cdot (x+y)$.
• Нахождение подмножества множества целых чисел, произведение которых — квадрат
• Составление факторной базы: набора $\{-1,p_1,p_2,\dots ,p_n\}$, где p_i — простые числа, такие, что $p_i⩽B$ для некоторого B.
• Просеивание выполняется подобно решету Эратосфена (откуда метод и получил своё название). Решетом служат простые числа факторной базы и их степени. При просеивании число не «вычёркивается», а делится на число из решета. Если в результате число оказалось единицей, то оно B-гладкое.
• Основная идея состоит в том, чтобы вместо перебора чисел и проверки, делятся ли их квадраты по модулю n на простые числа из факторной базы, перебираются простые числа из базы и сразу для всех чисел вида $x^2-n$ проверяется, делятся ли они на это простое число или его степень.

Алгоритм

Пусть $n$ — нечетное составное число, которое требуется факторизовать.

Выберем степень неприводимого многочлена $d\ge 3$ (при $d=2$ не будет выигрыша в сравнении с методом квадратичного решета).

Выберем целое $m$ такое, что $\lfloor n^{1/(d+1)}\rfloor <m<\lfloor n^{1/d}\rfloor$, и разложим n по основанию $m$:

$n=m^d+a_{d-1}{m}^{d-1}+\dots +a_0$ (1)

Свяжем с разложением (1) неприводимый в кольце $\mathbb{Z}[x]$ полиномов с целыми коэффициентами многочлен

$f_1(x)=x^d+a_{d-1}{x}^{d-1}+\dots +a_0$

Определим полином просеивания $F_1(a,b)$ как однородный многочлен от двух переменных $a$ и $b$:

$F_1(a,b)=b^d\cdot f_1(a/b)=a^d+a_{d-1}{a}^{d-1}b+a_{d-2}{a}^{d-2}{b}^2+...+a_0{b}^d$ (2)

Определим второй полином $f_2(x)=x-m$ и соответствующий однородный многочлен $F_2(a,b)=a-bm$.

Выберем два положительных числа $L_1$ и $L_2$, определяющих область просеивания (англ. sieve region):

$SR=\{1\le b\le L_1,-L_2\le a\le L_2\}$

Пусть $\theta$ — корень $f_1(x)$. Рассмотрим кольцо полиномов $\mathbb{Z}[\theta ]$. Определим множество, называемое алгебраической факторной базой $F{B}_1$, состоящее из многочленов первого порядка вида $a-b\theta$ с нормой (2), являющейся простым числом. Эти многочлены — простые неразложимиые в кольце алгебраических целых поля $K=\mathbb{Q}[\theta ]$. Ограничим абсолютные значения норм полиномов из $F{B}_1$ константой $B_1$.

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

Определим множество $F{B}_3$, называемое факторной базой квадратичных характеров. Это множество полиномов первого порядка $c-d\theta$, норма которых - простое число. Должно выполняться условие $F{B}_1\cap F{B}_3=\mathrm{\varnothing }$.

Выполним просеивание многочленов $\{a-b\theta \mid (a,b)\in SR\}$ по факторной базе $F{B}_1$ и целых чисел $\{a-bm\mid (a,b)\in SR\}$ по факторной базе $F{B}_2$. В результате получим множество $M$, состоящее из гладких пар $(a,b)$, то есть таких пар $(a,b)$, что НОД(a,b) = 1, полином и число $a-b\theta$ и $a-bm$ раскладываются полностью по $F{B}_1$ и $F{B}_2$ соответственно.

Найдём такое подмножество $S\subseteq M$, что

$\prod _{(a,b)\in S}Nr(a-b\theta )=H^2,H\in \mathbb{Z};\prod _{(a,b)\in S}(a-bm)=B^2,B\in \mathbb{Z}$

Определим многочлен

$g(\theta )={{f_1}^{\prime }}^2(\theta )\cdot \prod _{(a,b)\in S}(a-b\theta )$

где ${f_1}^{\prime }(x)$ — производная $f_1(x)$

Многочлен $g(\theta )$ является полным квадратом в кольце полиномов $\mathbb{Z}(\theta )$. Пусть тогда $\alpha (\theta )$ есть корень из $g(\theta )$ и $B$ — корень из $B^2$.

Строим отображение $\varphi :\theta \to m$, заменяя полином $\alpha (\theta )$ числом $\alpha (m)$. Это отображение является кольцевым гомоморфизмом кольца алгебраических целых чисел ${\mathbb{Z}}_K$ в кольцо $\mathbb{Z}$, откуда получаем соотношение:

$A^2={g(m)}^2\equiv {\varphi (g(\alpha ))}^2\equiv \varphi ({{f_1}^{\prime }}^2(\theta )\cdot \prod _{(a,b)\in S}(a-b\theta ))\equiv {{f_1}^{\prime }}^2(m)\cdot \prod _{(a,b)\in S}(a-bm)\equiv {{f_1}^{\prime }}^2(m)\cdot C^2(\mathrm{mod}n)$

Пусть $B=f^{\prime }(m)\cdot C$. Найдём пару чисел $(A,B)$ таких, что $A\equiv B(\mathrm{mod}n)$. Тогда найдём делитель числа $n$, вычисляя НОД(n, A ± B), как это делается, например, в методе квадратичного решета.

Подробное описание алгоритма можно найти, например, в и .

Реализации

До 2007 года наиболее успешной реализацией считалось программное обеспечение, разработанное и распространяемое Центром математики и информатики (CWI) в Нидерландах, распространявшееся под закрытой лицензией.

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

Некоторые другие реализации общего метода решета числового поля:

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

Достижения

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

В 2009 году группе учёных из Швейцарии, Японии, Франции, Нидерландов, Германии и США удалось успешно вычислить данные, зашифрованные при помощи криптографического ключа стандарта RSA длиной 768 битов. Как следует из описания работы, вычисление значений ключа осуществлялось общим методом решета числового поля. По словам исследователей, после их работы в качестве надежной системы шифрования можно рассматривать только RSA-ключи длиной 1024 бита и более.

См. также

• Специальный метод решета числового поля
• Факторизация целых чисел