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

У теорії чисел метод решета числового поля є найбільш ефективним серед алгоритмів факторизації чисел, що більші ніж 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)$, продемонструвавши його розкладом сьомого числа Ферма $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 бітів. Згідно з описом роботи, обчислення значень ключа здійснювалось методом решета загального числового поля. Після публікації їх праці як надійну систему шифрування можна розглядати тільки RSA-ключі довжиною не менше ніж 1024 біти.

Див. також

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

Посилання

• А. Ленстра та Х. Ленстра "Розвиток решета числового поля", Замітки з лекцій з Математики (1993).
• Р. Крандаль та К. Померанц Прості числа: Перспективи обчислень, (2001), 2 видання ISBN 0-387-25282-7.