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

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

Історія У 1988 році британський математик описав новий метод факторизації цілих чисел вигляду (де c — невелике число), і продемонстрував його розкладом сьомого числа Ферма . На відміну від методу квадратичного решета, в якому просіювання здійснюється в кільці простих натуральних чисел, він пропонував застосувати кільце простих чисел над числовим полем . Рукопис було вкладено в листа, адресованого польському математику . Копії цього листа отримали також , Дж. Бріллхарт, , та Х. Суяма. У тому листі Поллард припустив, що можливо цей метод можна застосувати для розкладу дев'ятого числа Ферма.

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

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

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

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

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

Числове поле Нехай — це многочлен -го порядку на множині раціональних чисел та — це комплексний корінь . Тоді , що може бути перебудовано для того, щоб виразити , як лінійну комбінацію степенів , що менші ніж . Цю рівність можна використати, щоб відкинути всі степені , що більші або рівні . Для прикладу та — це уявна частина , тоді або . Це дозволяє визначити добуток комплексних чисел:

.

У цілому, це прямо стосується алгебраїчного числового поля , що може бути визначено як множина дійсних чисел типу:

де .

Добуток двох довільних значень може бути обчислений за допомогою обрахування добутку поліномів. Тому вищеописане відкидання всіх степенів , більших або рівних , видає результат у тій самій формі. Щоб впевнитися, що поле є справді -го порядку й не руйнується в меншому полі, достатньо показати, що — незвідний многочлен на дійсних числах. Простіше кажучи, воно має утворювати кільце цілих чисел як підмножину , де — також цілі числа. У деяких випадках це кільце ізоморфне кільцю .

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

Загальні принципи Метод факторизації Ферма для факторизації натуральних непарних чисел , що полягає в пошуку таких цілих чисел та , що , що веде до розкладу . Знаходження підмножини множини цілих чисел, добуток яких — квадрат. Визначення факторної бази: набору , де — це прості числа, причому такі, що , для деякого . Просіювання виконується подібно до решета Ератосфена. Решетом слугують прості числа факторної бази та їхні степені. Під час просіювання число не «викреслюється», а ділиться на число з решета. Якщо в результаті число перетворилось на 1, то воно -гладке. Загальна ідея полягає в тому, що замість перебору чисел та перевірки, чи діляться їхні квадрати по модулю на прості числа з факторної бази, перебираються прості числа із бази і одразу для всіх чисел типу перевіряється, чи воно ділиться на дане просте число або його степінь.

Алгоритм Нехай — непарне складене число, яке потрібно факторизувати. Виберемо степінь незвідного многочлена (при цей метод не буде швидшим у порівнянні з методом квадратичного решета). Оберемо таке ціле , що , і розкладемо за основою : (1) Пов'яжемо з розкладом (1) незвідний в кільці поліномів з цілими коефіцієнтами многочлен Визначимо поліном просіювання як однорідний многочлен від двох змінних a та b:(2). Визначимо другий поліном і відповідний однорідний многочлен Оберемо два додатні числа та , що визначають область просіювання: Нехай θ — корінь Розглянемо кільце поліномів . Визначимо множину, що називається алгебраїчною факторною базою , що складається з многочленів першого порядку типу з нормою (2), що є простим числом. Ці многочлени — прості нерозкладні в кільці алгебраїчних цілих поля . Обмежимо абсолютні значення поліномів із константою . Визначимо раціональну факторну базу , що складається з усіх простих чисел, що обмежені зверху константою . Визначимо множину , що називається факторною базою квадратичних характерів. Ця множина поліномів першого порядку , норма яких — просте число. Має виконуватися умова Виконаємо просіювання многочленів з факторною базою і цілих чисел по факторній базі . У результаті отримаємо множину , що складається з гладких пар , тобто таких пар , що НСД, поліном та число і розкладаються повністю по та відповідно. Знайдемо таку підмножину , що Визначимо многочлен , де — похідна . Многочлен є повним квадратом у кільці поліномів . Нехай тоді є коренем із та — корінь із . Будуємо відображення , замінюючи поліном числом . Це відображення є кільцевим гомоморфізмом кільця алгебраїчних цілих чисел в кільце , звідки отримуємо співвідношення: Нехай . Знайдемо пару таких чисел , що . Тоді знайдемо дільник числа , обчислюючи НСД, як це робиться в методі квадратичного решета. Більш детальний опис алгоритму можна знайти тут та тут

Реалізації До 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 біти.

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

Примітки