Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

Числовые поля [ править ]

Основная статья: Числовое поле

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

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

Произведение любых двух таких значений можно вычислить, взяв произведение как многочлены, а затем уменьшив любые степени r с показателем e ≥ k, как описано выше, и получим значение в той же форме. Чтобы это поле было действительно k -мерным и не коллапсировало до еще меньшего поля, достаточно, чтобы f был неприводимым многочленом над рациональными числами. Аналогично, можно определить кольцо целых чисел O Q [ r ] как подмножество Q [ r ], которые являются корнями монических многочленов с целыми коэффициентами. В некоторых случаях это кольцо целых чисел эквивалентно кольцу Z [ r ] . Однако есть много исключений, например, для Q [ √ d ], когда d равно 1 по модулю 4. [2]

Метод [ править ]

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

Рассмотрим кольца числовых полей Z [ r 1 ] и Z [ r 2 ], где r 1 и r 2 - корни многочленов 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 1 b и, следовательно, произведение соответствующих множителей a  -  r 1 b представляет собой квадрат в Z [ r 1 ] с «квадратным корнем», который может быть определен (как произведение известные факторы вZ [ r 1 ]) - обычно это иррациональное алгебраическое число . Точно так же произведение множителей a  -  r 2 b представляет собой квадрат в Z [ r 2 ] с «квадратным корнем», который также можно вычислить. Следует отметить, что использование исключения Гаусса не дает оптимального времени выполнения алгоритма. Вместо этого используются алгоритмы решения разреженных матриц, такие как Блок Ланцоша или Блок Видеманна .

Поскольку m является корнем как f, так и g mod n , существуют гомоморфизмы из колец Z [ r 1 ] и Z [ r 2 ] в кольцо Z / n Z (целые числа mod n ), которые отображают r 1 и r От 2 до m , и эти гомоморфизмы будут отображать каждый «квадратный корень» (обычно не представленный как рациональное число) в его целочисленный представитель. Теперь произведение факторов a  -  mb modn можно получить в виде квадрата двумя способами - по одному для каждого гомоморфизма. Таким образом, можно найти два числа х и у , с х 2  -  у 2 , делящиеся на п и снова с вероятностью по крайней мере одна половина мы получаем коэффициент п , найдя наибольший общий делитель из н и х  -  у .

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

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

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

Лучшие сообщенные результаты [4] были получены методом Торстен Kleinjung , [5] , который позволяет г ( х ) = AX  +  B , и поиски более состоят из мелких простых множителей конгруэнтны 1 по модулю 2 г и более старших коэффициентов f, которые делятся на 60.

Реализации [ править ]

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

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

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

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

См. Также [ править ]

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

Заметки [ править ]

  1. ^ Померанс, Карл (декабрь 1996). «Сказка о двух решетах» (PDF) . Уведомления AMS . 43 (12). С. 1473–1485.
  2. ^ Ribenboim Пауло (1972). Алгебраические числа . Wiley-Interscience. ISBN 978-0-471-71804-8.
  3. ^ Мерфи, B .; Брент, Р.П. (1998), "О квадратичных полиномах для сита числового поля" , Australian Computer Science Communications , 20 : 199–213
  4. ^ Franke, Jens (2006), О проектах RSA 200 и более (PDF)
  5. ^ Kleinjung, Торстен (октябрь 2006). «О выборе полинома для сита общего числового поля» (PDF) . Математика вычислений . 75 (256): 2037–2047. DOI : 10.1090 / S0025-5718-06-01870-9 . Проверено 13 декабря 2007 .
  6. ↑ Пол Лейланд (12 декабря 2003 г.). «NFSNET: первый год» . Презентация на семинаре EIDMA-CWI по факторингу больших чисел . Проверено 9 августа 2011 года .
  7. ^ «Добро пожаловать в NFSNET» . 23 апреля, 2007. Архивировано из оригинального 22 октября 2007 года . Проверено 9 августа 2011 года .
  8. ^ «О NFSNET» . Архивировано из оригинала 9 мая 2008 года . Проверено 9 августа 2011 года .

Ссылки [ править ]

  • Арьен К. Ленстра и Х.В. Ленстра младший (ред.). «Развитие сита числового поля». Конспект лекций по математике. (1993) 1554. Springer-Verlag.
  • Ричард Крэндалл и Карл Померанс . Простые числа: вычислительная перспектива (2001). 2-е издание, Springer. ISBN 0-387-25282-7 . Раздел 6.2: Сито числового поля, стр. 278–301. 
  • Мэтью Э. Бриггс: Введение в сито общего числового поля, 1998