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

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

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

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

Пізніше Леонард Макс Адлеман запропонував застосувати квадратичний характер для пошуку квадратів у числовому полі. Це надало альтернативне розв'язання проблеми, піднятою Бухлером і Померансом^[en], і покращило очікуваний час роботи методу решета числового поля для чисел, які не мають спеціального виду[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}$, що полягає в пошуку таких цілих чисел ${\displaystyle x}$ та ${\displaystyle y}$, що ${\displaystyle x^{2}-y^{2}=n}$, що веде до розкладу ${\displaystyle n=(x-y)(x+y)}$.
• Знаходження підмножини множини цілих чисел, добуток яких — квадрат.[9]
• Визначення факторної бази: набору ${\displaystyle \{-1,p_{1},p_{2},...,p_{n}\}}$, де ${\displaystyle p_{i}}$ — це прості числа, причому такі, що ${\displaystyle p_{i}\leq B}$, для деякого ${\displaystyle B}$.
• Просіювання виконується подібно до решета Ератосфена. Решетом слугують прості числа факторної бази та їхні степені. Під час просіювання число не «викреслюється», а ділиться на число з решета. Якщо в результаті число перетворилось на 1, то воно ${\displaystyle B}$-гладке.
• Загальна ідея полягає в тому, що замість перебору чисел та перевірки, чи діляться їхні квадрати по модулю ${\displaystyle n}$ на прості числа з факторної бази, перебираються прості числа із бази і одразу для всіх чисел типу ${\displaystyle x^{2}-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[12]. 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 біти.

Див. також

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

Примітки

1. Pomerance, Carl (1996). A Tale of Two Sieves (PDF). Архів оригіналу (PDF) за 11 листопада 2020. Процитовано 23 листопада 2016.
2. Adleman, Leonard M. (1991). Factoring numbers using singular integers. ISBN 0-89791-397-3.
3. A.K. Lenstra, H.W. Lenstra, Jr., M.S. Manasse, J.M. Pollard (1993). The Factorization of the Ninth Fermat Number. Архів оригіналу за 24 листопада 2016. Процитовано 23 листопада 2016.
4. J.P. Buhler, H.W. Lenstra, Carl Pomerance (1993). Factoring integers with the number field sieve. Архів оригіналу за 24 листопада 2016. Процитовано 23 листопада 2016.
5. Couveignes, Jean-Marc (1993). Computing A Square Root For The Number Field Sieve. Архів оригіналу за 24 листопада 2016. Процитовано 23 листопада 2016.
6. A. K. Lenstra, H. W. Lenstra (1993). The Development of the Number Field Sieve, Springer. ISBN 9783540570134.
7. Couveignes, Jean-Marc (1993). A general number field sieve implementation. Архів оригіналу за 24 листопада 2016. Процитовано 23 листопада 2016.
8. Ribenboim, Paulo (1972). Algebraic Numbers. Wiley-Interscience. ISBN 0471718041.
9. И. В. Агафонова. Факторизация больших целых чисел и криптография (PDF). Архів оригіналу (PDF) за 26 лютого 2015. Процитовано 28 листопада 2016.
10. Ишмухаметов, Ш. Т. (2011). Методы факторизации натуральных чисел (PDF).^[недоступне посилання з квітня 2019]
11. Briggs M. (1998). An Introduction to the General Number (PDF). Архів оригіналу (PDF) за 8 серпня 2017. Процитовано 28 листопада 2016.
12. Msieve announcements. mersenneforum.org. Процитовано 13 жовтня 2023.