Общее числовое поле решето

В теории чисел общее решето числового поля ( GNFS ) является наиболее эффективным классическим алгоритмом, известным для факторизации целых чисел, больших 10 $100. Эвристически$ его сложность для факторизации целого числа $n$ (состоящего из $⌊log 2 n ⌋ + 1$ бит) имеет вид

{\begin{align}&\exp \left(\left((64/9)^{1/3}+o(1)\right)\left(\log n\right)^{1/3}\left(\log \log n\right)^{2/3}\right)\\[5pt]={}&L_{n}\left[1/3,(64/9)^{1/3}\right]\end{align}}

в O- и L-нотациях . ^[1] Это обобщение специального решета числового поля : в то время как последнее может факторизовать только числа определенной специальной формы, общее решето числового поля может факторизовать любые числа, кроме степеней простых чисел (которые тривиально факторизуются извлечением корней).

Принцип решета числового поля (как специального, так и общего) можно понимать как усовершенствование более простого рационального решета или квадратичного решета . При использовании таких алгоритмов для факторизации большого числа $n$ необходимо искать гладкие числа (т. е. числа с малыми простыми множителями) порядка $n 1/2$ . Размер этих значений экспоненциален по размеру $n$ (см. ниже). Общее решето числового поля, с другой стороны, умудряется искать гладкие числа, которые субэкспоненциальны по размеру $n$ . Поскольку эти числа меньше, они с большей вероятностью будут гладкими, чем числа, проверенные в предыдущих алгоритмах. Это ключ к эффективности решета числового поля. Чтобы достичь этого ускорения, решето числового поля должно выполнять вычисления и факторизации в числовых полях . Это приводит ко многим довольно сложным аспектам алгоритма по сравнению с более простым рациональным решетом.

Размер входных данных для алгоритма равен $log 2 n$ или числу бит в двоичном представлении $n$ . Любой элемент порядка $n c$ для константы $c$ является экспоненциальным по $log n$ . Время работы решета числового поля является суперполиномиальным, но субэкспоненциальным по размеру входных данных.

Числовые поля

Предположим, что $f$ — многочлен степени $k$ над (рациональными числами), а $r$ — комплексный корень $f$ . Тогда $f$ $($ $r$ $) = 0$ , что можно переставить, чтобы выразить $r$ $k$ как линейную комбинацию степеней $r,$ меньших $k$ . Это уравнение можно использовать для сокращения любых степеней $r$ с показателем $e$ $\geq$ $k$ . Например, если $f$ $($ $x$ $) =$ $x$ $2$ $+ 1$ , а $r$ — мнимая единица $i$ , то $i$ $2$ $+ 1 = 0$ или $i$ $2$ $= -1$ . Это позволяет нам определить комплексное произведение: ${\textstyle \mathbb {Q} }$

{\begin{align}(a+bi)(c+di)&=ac+(ad+bc)i+(bd)i^{2}\\[4pt]&=(ac-bd)+(ad+bc)i.\end{align}}

В общем случае это приводит непосредственно к алгебраическому числовому полю , которое можно определить как множество комплексных чисел, заданное формулой: ${\textstyle \mathbb {Q} [р]}$

a_{k-1}r^{k-1}+\cdots +a_{1}r^{1}+a_{0}r^{0},{\text{ где }}a_{0},\ldots ,a_{k-1}\in \mathbb {Q} .

Произведение любых двух таких значений можно вычислить, взяв произведение в качестве многочленов, а затем сократив любые степени $r$ с показателем $e$ $\geq$ $k,$ как описано выше, что даст значение в той же форме. Чтобы гарантировать, что это поле на самом деле $k$ -мерное и не схлопнется в еще меньшее поле, достаточно, чтобы $f$ было неприводимым многочленом над рациональными числами. Аналогично можно определить кольцо целых чисел как подмножество , которое является корнями монических многочленов с целыми коэффициентами. В некоторых случаях это кольцо целых чисел эквивалентно кольцу . Однако существует много исключений. ^[2] ${\textstyle \mathbb {O} _ {\mathbb {Q} [r]}}$ ${\textstyle \mathbb {Q} [р]}$ ${\textstyle \mathbb {Z} [р]}$

Метод

Выбраны два многочлена f ( x ) и g ( x ) малых степеней d и e , которые имеют целые коэффициенты, неприводимые над рациональными числами , и которые при интерпретации mod n имеют общий целый корень m . Оптимальная стратегия выбора этих многочленов неизвестна; один простой метод состоит в том, чтобы выбрать степень d для многочлена, рассмотреть разложение n по основанию m (допуская цифры между − m и m ) для ряда различных m порядка n ^{1/ d} , и выбрать f ( x ) как многочлен с наименьшими коэффициентами и g ( x ) как x − m .

Рассмотрим кольца числовых полей Z [ r ₁ ] и Z [ r ₂ ], где r ₁ и r ₂ являются корнями многочленов f и g . Поскольку f имеет степень d с целыми коэффициентами, если a и b являются целыми числами, то таким же будет и b ^d · f ( a / b ), которое мы называем r . Аналогично, s = b ^e · g ( a / b ) является целым числом. Цель состоит в том, чтобы найти целые значения a и b , которые одновременно делают r и s гладкими относительно выбранного базиса простых чисел. Если a и b малы, то r и s также будут малы, примерно размером с m , и у нас больше шансов, что они будут гладкими одновременно. В настоящее время наиболее известным подходом для этого поиска является решеточное просеивание ; чтобы получить приемлемые результаты, необходимо использовать большую факторную базу.

Имея достаточно таких пар, используя исключение Гаусса , можно получить произведения определенных r и соответствующих s, которые будут квадратами одновременно. Требуется немного более сильное условие — чтобы они были нормами квадратов в наших числовых полях, но это условие может быть достигнуто и этим методом. Каждое r является нормой a − r ₁b и, следовательно, произведение соответствующих множителей a − r ₁b является квадратом в Z [ r ₁ ], с «квадратным корнем», который может быть определен (как произведение известных множителей в Z [ r ₁ ]) — оно обычно будет представлено как иррациональное алгебраическое число . Аналогично, произведение множителей a − r ₂b является квадратом в Z [ r ₂ ], с «квадратным корнем», который также может быть вычислен. Следует отметить, что использование исключения Гаусса не дает оптимального времени выполнения алгоритма. Вместо этого используются алгоритмы решения разреженных матриц, такие как блочный Ланцоша или блочный Видемана .

Так как m является корнем как f , так и g mod n , существуют гомоморфизмы из колец Z [ r ₁ ] и Z [ r ₂ ] в кольцо Z / n Z (целые числа по модулю n ), которые отображают r ₁ и r ₂ в m , и эти гомоморфизмы отображают каждый «квадратный корень» (обычно не представленный как рациональное число) в его целочисленный представитель. Теперь произведение множителей a − mb mod n можно получить как квадрат двумя способами — по одному для каждого гомоморфизма. Таким образом, можно найти два числа x и y , причем x ² − y ²делятся на n , и снова с вероятностью не менее половины мы получаем множитель n, находя наибольший общий делитель n и x − y .

Улучшение полиномиального выбора

Выбор полинома может существенно повлиять на время выполнения оставшейся части алгоритма. Метод выбора полиномов на основе разложения $n$ по основанию $m,$ показанный выше, является субоптимальным во многих практических ситуациях, что приводит к разработке лучших методов.

Один из таких методов был предложен Мерфи и Брентом; ^[3] они вводят двухкомпонентную оценку для многочленов, основанную на наличии корней по модулю малых простых чисел и на среднем значении, которое многочлен принимает по области просеивания.

Наилучшие результаты ^[4] были достигнуты методом Торстена Кляйнджунга ^[5] , который допускает $g (x) = ax + b$ и выполняет поиск по $a,$ составленному из малых простых множителей, сравнимых с 1 по модулю 2 $d$ , и по старшим коэффициентам $f$ , которые делятся на 60.

Реализации

Некоторые реализации фокусируются на определенном меньшем классе чисел. Они известны как специальные методы решета числового поля , такие как используемые в проекте Каннингема . Проект под названием NFSNET действовал с 2002 ^[6] по крайней мере до 2007 года. Он использовал добровольные распределенные вычисления в Интернете . ^[7] В нем участвовали Пол Лейланд из Великобритании и Ричард Вакербарт из Техаса. ^[8]

До 2007 года золотым стандартом реализации был набор программного обеспечения, разработанный и распространенный CWI в Нидерландах, который был доступен только по относительно ограничительной лицензии. ^{[ необходима цитата ]} В 2007 году Джейсон Пападопулос разработал более быструю реализацию окончательной обработки как часть msieve, которая находится в открытом доступе. Обе реализации обладают возможностью распределения между несколькими узлами в кластере с достаточно быстрым соединением.

Полиномиальный отбор обычно выполняется с помощью программного обеспечения GPL, написанного Кляйнджунгом, или с помощью msieve, а решеточное просеивание — с помощью программного обеспечения GPL, написанного Франке и Кляйнджунгом; они распространяются в GGNFS.

NFS@Home
ГГНФС
фактор по gnfs
CADO-NFS
msieve (содержит код окончательной обработки, полиномиальный выбор, оптимизированный для меньших чисел, и реализацию линейного решета)
кмГНФС

Смотрите также

Специальное числовое поле сито

Примечания

^ Померанс, Карл (декабрь 1996 г.). «Сказка о двух решетах» (PDF) . Извещения AMS . Том 43, № 12. С. 1473–1485.
^ Рибенбойм, Пауло (1972). Алгебраические числа . Wiley-Interscience. ISBN 978-0-471-71804-8.
^ Мерфи, Б.; Брент, РП (1998), «О квадратичных многочленах для решета числового поля», Australian Computer Science Communications , 20 : 199–213
^ Франке, Йенс (2006), О RSA 200 и более крупных проектах (PDF)
^ Kleinjung, Thorsten (октябрь 2006 г.). "On polynomial selection for the general number field sieve" (PDF) . Mathematics of Computation . 75 (256): 2037–2047. Bibcode :2006MaCom..75.2037K. doi : 10.1090/S0025-5718-06-01870-9 . Получено 13.12.2007 .
^ Пол Лейланд (12 декабря 2003 г.). "NFSNET: первый год". Презентация на семинаре EIDMA-CWI по факторизации больших чисел . Получено 9 августа 2011 г.
^ "Добро пожаловать в NFSNET". 23 апреля 2007 г. Архивировано из оригинала 22 октября 2007 г. Получено 9 августа 2011 г.
^ "О NFSNET". Архивировано из оригинала 9 мая 2008 г. Получено 9 августа 2011 г.

Ссылки

Арьен К. Ленстра и Х. В. Ленстра, младший (ред.). «Развитие решета числового поля». Lecture Notes in Math. (1993) 1554. Springer-Verlag.
Ричард Крэндалл и Карл Померанс . Простые числа: вычислительная перспектива (2001). 2-е издание, Springer. ISBN 0-387-25282-7 . Раздел 6.2: Решето числового поля, стр. 278–301.

Мэтью Э. Бриггс: Введение в общее числовое решето поля, 1998