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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

До 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.