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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

Історія[ред. | ред. код]

У 1988 році британський математик Джон Поллард[en] описав новий метод факторизації цілих чисел спеціального вигляду , продемонструвавши його розкладом сьомого числа Ферма . На відміну від методу квадратичного решета, в якому просіювання відбувається в кільці всіх простих чисел, він пропонував використовувати кільце простих чисел Над числовим полем . Рукопис був вкладений у лист, адресований польському математику Андрію Одлизко[en]. Копії цього листа також отримали: Річард Брент[en], Дж. Бріллхарт, Хедріх Ленстра[en], Клаус Шорр[en] та Х. Суяма. У тому листі Поллард припустив, що можливо цей метод може бути застосований для розкладу дев'ятого числа Ферма.

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

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

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

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

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

Числове поле[ред. | ред. код]

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

.

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

де .

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

Суть методу[ред. | ред. код]

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

Загальні принципи[ред. | ред. код]

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

Алгоритм[ред. | ред. код]

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

  1. Виберемо степінь незвідного многочлена (при цей метод не буде швидшим у порівнянні з методом квадратичного решета).
  2. Оберемо таке ціле , що , і розкладемо за основою : (1)
  3. Пов'яжемо з розкладом (1) незвідний в кільці поліномів з цілими коефіцієнтами многочлен
  4. Визначимо поліном просіювання як однорідний многочлен від двох змінних a та b:(2).
  5. Визначимо другий поліном і відповідний однорідний многочлен
  6. Оберемо два додатні числа та , що визначають область просіювання:
  7. Нехай θ — корінь Розглянемо кільце поліномів . Визначимо множину, що називається алгебраїчною факторною базою , що складається з многочленів першого порядку типу з нормою (2), що є простим числом. Ці многочлени — прості нерозкладні в кільці алгебраїчних цілих поля . Обмежимо абсолютні значення поліномів із константою .
  8. Визначимо раціональну факторну базу , що складається з усіх простих чисел, що обмежені зверху константою .
  9. Визначимо множину , що називається факторною базою квадратичних типів. Ця множина поліномів першого порядку , норма яких — просте число. Повинна виконуватися умова
  10. Виконаємо просіювання многочленів з факторною базою і цілих чисел по факторній базі . В результаті отримаємо множину , що складається з гладких пар , тобто таких пар , що НСД, поліном та число і розкладаються повністю по та відповідно.
  11. Знайдемо таку підмножину , що
  12. Визначимо многочлен , де — похідна .
  13. Многочлен є повним квадратом в кільці поліномів . Нехай тоді є коренем із та — корінь із .
  14. Будуємо відображення , замінюючи поліном числом . Це відображення є кільцевим гомоморфізмом кільця алгебраїчних цілих чисел в кільце , звідки отримуємо співвідношення:
  15. Нехай . Знайдемо пару таки чисел , що . Тоді знайдемо дільник числа , обчислюючи НСД, як це робиться в методі квадратичного решета.

Більш детальний опис алгоритму можна знайти тут[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.

Примітки[ред. | ред. код]

  1. Pomerance, Carl (1996). A Tale of Two Sieves. 
  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. 
  4. J.P. Buhler, H.W. Lenstra, Carl Pomerance (1993). Factoring integers with the number field sieve. 
  5. Couveignes, Jean-Marc (1993). Computing A Square Root For The Number Field Sieve. 
  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. 
  8. Ribenboim, Paulo (1972). Algebraic Numbers. Wiley-Interscience. ISBN 0471718041. 
  9. И. В. Агафонова. Факторизация больших целых чисел и криптография. 
  10. Ишмухаметов, Ш. Т. (2011). Методы факторизации натуральных чисел. [недоступне посилання з квітня 2019]
  11. Briggs M. (1998). An Introduction to the General Number. Архів оригіналу за 8 серпня 2017. Процитовано 28 листопада 2016.