Решето числового поля

У теорії чисел метод решета числового поля є найдієвішим серед алгоритмів факторизації чисел, що більші ніж 10¹⁰⁰. Складність факторизації цілого числа n за допомогою методу решета числового поля оцінюється евристичною формулою:

$\exp({\sqrt[{3}]{64 \over 9}}(\ln n)^{1 \over 3}(\ln \ln n)^{2 \over 3})=L_{n}\left[{1 \over 3},{\sqrt[{3}]{64 \over 9}}\right]$

Метод є узагальненням спеціального решета числового поля. На відміну від останнього, котрий факторизує тільки числа спеціального вигляду, працює на всій множині цілих чисел, окрім степенів простих чисел.

Історія

У 1988 році британський математик Джон Поллард описав новий метод факторизації цілих чисел вигляду $2^{n}\pm c$ (де c — невелике число), і продемонстрував його розкладом сьомого числа Ферма $F_{7}=2^{128}+1$. На відміну від методу квадратичного решета, в якому просіювання здійснюється в кільці простих натуральних чисел, він пропонував застосувати кільце простих чисел $Z([2^{\frac {3}{2}}])$ над числовим полем $Q(2^{\frac {3}{2}})$. Рукопис було вкладено в листа, адресованого польському математику Андрію Одлизко. Копії цього листа отримали також Річард Брент, Дж. Бріллхарт, Хедріх Ленстра, Клаус Шорр та Х. Суяма. У тому листі Поллард припустив, що можливо цей метод можна застосувати для розкладу дев'ятого числа Ферма.

У 1990 році А. Ленстра, Х. Ленстра, Марк Манассе і Поллард описали першу реалізацію нового методу з певною оптимізацією. Вони показали, що на числах спеціального виду алгоритм працює швидше, ніж усі інші раніше відомі алгоритми факторизації.

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

Того ж року А. Ленстра, Х. Ленстра, Манассе і Поллард розклали методом решета числового поля дев'яте число Ферма й опублікували працю з багатьма подробицями цього розкладу.

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

Усі крапки над «і» було поставлено в збірці статей під редакцією А. Ленстри та Х. Ленстри. Зокрема, збірка містила статтю Берштейна і А. Ленстри, яка описувала реалізацію загального решета числового поля.

Числове поле

Нехай $f$ — це многочлен $k$-го порядку на множині раціональних чисел та $r$ — це комплексний корінь $f$. Тоді $f(r)=0$, що може бути перебудовано для того, щоб виразити $r^{k}$, як лінійну комбінацію степенів $r$, що менші ніж $k$. Цю рівність можна використати, щоб відкинути всі степені $r$, що більші або рівні $k$. Для прикладу $f(x)=x^{2}+1$ та $r$ — це уявна частина $i$, тоді $i^{2}+1=0$ або $i^{2}=-1$. Це дозволяє визначити добуток комплексних чисел:

$(a+bi)(c+di)=ac+(ad+bc)i+(bd)i^{2}=(ac-bd)+(ad+bc)i$.

У цілому, це прямо стосується алгебраїчного числового поля $\mathbb {Q} [r]$, що може бути визначено як множина дійсних чисел типу:

$a_{k-1}r^{k-1}+...+a_{1}r^{1}+a_{0}r^{0},$ де $a_{0},...,a_{k-1}\in \mathbb {Q}$.

Добуток двох довільних значень може бути обчислений за допомогою обрахування добутку поліномів. Тому вищеописане відкидання всіх степенів $r$, більших або рівних $k$, видає результат у тій самій формі. Щоб впевнитися, що поле є справді $k$-го порядку й не руйнується в меншому полі, достатньо показати, що $f$ — незвідний многочлен на дійсних числах. Простіше кажучи, воно має утворювати кільце цілих чисел $\mathbb {O} _{\mathbb {Q} [r]}$ як підмножину $\mathbb {Q} [r]$, де $a_{0},...,a_{k-1}$ — також цілі числа. У деяких випадках це кільце ізоморфне кільцю $\mathbb {Z} [r]$.

Суть методу

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

Загальні принципи

• Метод факторизації Ферма для факторизації натуральних непарних чисел $n$, що полягає в пошуку таких цілих чисел $x$ та $y$, що $x^{2}-y^{2}=n$, що веде до розкладу $n=(x-y)(x+y)$.
• Знаходження підмножини множини цілих чисел, добуток яких — квадрат.
• Визначення факторної бази: набору $\{-1,p_{1},p_{2},...,p_{n}\}$, де $p_{i}$ — це прості числа, причому такі, що $p_{i}\leq B$, для деякого $B$.
• Просіювання виконується подібно до решета Ератосфена. Решетом слугують прості числа факторної бази та їхні степені. Під час просіювання число не «викреслюється», а ділиться на число з решета. Якщо в результаті число перетворилось на 1, то воно $B$-гладке.
• Загальна ідея полягає в тому, що замість перебору чисел та перевірки, чи діляться їхні квадрати по модулю $n$ на прості числа з факторної бази, перебираються прості числа із бази і одразу для всіх чисел типу $x^{2}-n$ перевіряється, чи воно ділиться на дане просте число або його степінь.

Алгоритм

Нехай $n$ — непарне складене число, яке потрібно факторизувати.

1. Виберемо степінь незвідного многочлена $d\geq 3$ (при $d=2$ цей метод не буде швидшим у порівнянні з методом квадратичного решета).
2. Оберемо таке ціле $m$, що $\lfloor n^{1/(d+1)}\rfloor <m<\lfloor n^{1/d}\rfloor$, і розкладемо $n$ за основою $m$: $n=m^{d}+a_{d-1}x^{d-1}+...+a_{0}$ (1)
3. Пов'яжемо з розкладом (1) незвідний в кільці $\mathbb {Z} [x]$ поліномів з цілими коефіцієнтами многочлен $f_{1}(x)=x^{d}+a_{d-1}x^{d-1}+...+a_{0}$
4. Визначимо поліном просіювання $F_{1}(a,b)$ як однорідний многочлен від двох змінних a та b:$F_{1}(a,b)=b^{d}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).
5. Визначимо другий поліном $f_{2}(x)=x-m$ і відповідний однорідний многочлен $F_{2}(a,b)=a-bm.$
6. Оберемо два додатні числа $L_{1}$ та $L_{2}$, що визначають область просіювання: $SR=\{1<b<L_{1}-L_{2}\leq a\leq L_{2}\}$
7. Нехай θ — корінь $f_{1}(x).$ Розглянемо кільце поліномів $\mathbb {Z} [\theta ]$. Визначимо множину, що називається алгебраїчною факторною базою $FB_{1}$, що складається з многочленів першого порядку типу $a-b\theta$ з нормою (2), що є простим числом. Ці многочлени — прості нерозкладні в кільці алгебраїчних цілих поля $K=\mathbb {Q} [\theta ]$. Обмежимо абсолютні значення поліномів із $FB_{1}$константою $B_{1}$.
8. Визначимо раціональну факторну базу $FB_{2}$, що складається з усіх простих чисел, що обмежені зверху константою $B_{2}$.
9. Визначимо множину $FB_{3}$, що називається факторною базою квадратичних характерів. Ця множина поліномів першого порядку $c-b\theta$, норма яких — просте число. Має виконуватися умова $FB_{1}\cap FB_{3}=\emptyset .$
10. Виконаємо просіювання многочленів $\{a-b\theta |(a,b)\in SR\}$ з факторною базою $FB_{1}$ і цілих чисел $\{a-bm|(a,b)\in SR\}$ по факторній базі $FB_{2}$. У результаті отримаємо множину $M$, що складається з гладких пар $(a,b)$, тобто таких пар $(a,b)$, що НСД$(a,b)=1$, поліном та число $a-b\theta$ і $a-bm$ розкладаються повністю по $FB_{1}$ та $FB_{2}$ відповідно.
11. Знайдемо таку підмножину $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}$
12. Визначимо многочлен $g(\theta )={f'_{1}}^{2}(\theta )\cdot \prod _{(a,b)\in S}(a-b\theta )$, де ${f'_{1}}(x)$ — похідна ${f_{1}}(x)$.
13. Многочлен $g(\theta )$ є повним квадратом у кільці поліномів $\mathbb {Z} [\theta ]$. Нехай тоді $a(\theta )$ є коренем із $g(\theta )$ та $B$ — корінь із $B^{2}$.
14. Будуємо відображення $\phi :0\to m$, замінюючи поліном $\alpha (\theta )$ числом $\alpha (m)$. Це відображення є кільцевим гомоморфізмом кільця алгебраїчних цілих чисел $\mathbb {Z} _{K}$ в кільце $\mathbb {Z}$, звідки отримуємо співвідношення: $A^{2}=g(m)^{2}\equiv \phi (g(\alpha ))^{2}\equiv \phi ({f'_{1}}^{2}(\theta ))\cdot \prod _{(a,b)\in S}(a-b\theta )\equiv {f'_{1}}^{2}(m)\cdot \prod (a-bm)\equiv {f'_{1}}^{2}(m)\cdot C^{2}{\pmod {n}}$
15. Нехай $B=f'(m)\cdot C$. Знайдемо пару таких чисел $(A,B)$, що $A\equiv B{\pmod {n}}$. Тоді знайдемо дільник числа $n$, обчислюючи НСД$(n,A\pm B)$, як це робиться в методі квадратичного решета.

Більш детальний опис алгоритму можна знайти тут та тут

Реалізації

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

У 2007 році Джейсон Пападопулос реалізував частину алгоритму, що займається кінцевою обробкою даних, так, щоб вона працювала швидше версії CWI. Цей код увійшов у бібліотеку msieve. 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 бітів (тобто, близько 220 десяткових знаків). Згідно з описом роботи^{[джерело?]}, обчислення здійснювалось методом решета загального числового поля. Після публікації їх праці як надійну систему шифрування можна розглядати тільки RSA-ключі довжиною не менше 1024 біти.

Див. також

• Факторизація цілих чисел.