Сито общего числового поля
В теории чисел сито общего числового поля ( GNFS ) является наиболее эффективным классическим алгоритмом, известным для факторизации целых чисел больше 10. 100 . Эвристически его сложность для факторизации целого числа n (состоящего из ⌊log 2 n ⌋ + 1 бит) имеет вид
![{\displaystyle {\begin{aligned}&\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{выровнено}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/65ab1aa7e793022d23ae984155302c620ebe2ff3)
в O и L-нотациях . [1] Это обобщение сита специального числового поля : хотя последнее может факторизовать только числа определенной специальной формы, общее сито числового поля может факторизовать любое число, кроме простых степеней (которые тривиально факторизовать путем извлечения корня).
Принцип решета числового поля (как специального, так и общего) можно понимать как улучшение более простого рационального решета или квадратичного решета . При использовании таких алгоритмов для факторизации большого числа n необходимо искать гладкие числа (т.е. числа с малыми простыми множителями) порядка n. 1/2 . Размер этих значений экспоненциально зависит от размера n (см. ниже). С другой стороны, сито общего числового поля позволяет искать гладкие числа, субэкспоненциальные по размеру n . Поскольку эти числа меньше, они с большей вероятностью будут гладкими, чем числа, проверенные в предыдущих алгоритмах. Это ключ к эффективности сита числового поля. Чтобы добиться такого ускорения, сито числовых полей должно выполнять вычисления и факторизацию в числовых полях . Это приводит ко многим довольно сложным аспектам алгоритма по сравнению с более простым рациональным решетом.
Размер входных данных алгоритма равен log 2 n или количеству битов в двоичном представлении n . Любой элемент порядка n с для константы c экспоненциально по log n . Время работы сита числового поля является суперполиномиальным, но субэкспоненциальным по размеру входных данных.
Числовые поля
[ редактировать ]Предположим, f — полином k -степени над (рациональные числа), а r — комплексный корень из f . Тогда f ( r ) = 0 , которое можно переставить, чтобы выразить r к как линейная комбинация степеней r меньше k . Это уравнение можно использовать для уменьшения любых степеней r с показателем e ≥ k . Например, если f ( x ) = x 2 + 1 и r — мнимая единица i , то i 2 + 1 = 0 или я 2 = −1 . Это позволяет нам определить сложный продукт:
![{\displaystyle {\begin{aligned}(a+bi)(c+di)&=ac+(ad+bc)i+(bd)i^{2}\\[4pt]&=(ac-bd)+( ad+bc)i.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0fab9e3303ab8d79f42e38f45ec006724c9fe956)
В общем, это ведет непосредственно к полю алгебраических чисел , который можно определить как набор комплексных чисел, заданный формулой:
![{\textstyle \mathbb {Q} [r]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4cbf7feccf064d48e74452b3eedcbe2592779cf5)
Произведение любых двух таких значений можно вычислить, взяв произведение в виде полинома, а затем уменьшив любые степени r с показателем e ≥ k, как описано выше, получив значение в той же форме. Чтобы гарантировать, что это поле действительно k -мерно и не схлопывается в еще меньшее поле, достаточно, чтобы f был неприводимым многочленом над рациональными числами. Аналогично можно определить кольцо целых чисел как подмножество которые являются корнями монических многочленов с целыми коэффициентами. В некоторых случаях это кольцо целых чисел эквивалентно кольцу . Однако есть много исключений. [2]
![{\textstyle \mathbb {O} _ {\mathbb {Q} [r]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/971f7420524eeb1aca810e20c18243d7bdd3d0d0)
![{\textstyle \mathbb {Z} [r]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1596c675c7c604078aa2d578c0da1df3668b5d31)
Метод
[ редактировать ] | Этот раздел может сбивать с толку или быть неясным для читателей . В частности, здесь нет примеров или псевдокода. ( Май 2021 г. ) |
два многочлена f ( x ) и g ( x ) малых степеней d и e Выбираются , которые имеют целые коэффициенты, неприводимые к рациональным числам и которые при интерпретации по модулю n имеют общий целочисленный корень m . Оптимальная стратегия выбора этих полиномов неизвестна; Один простой метод — выбрать степень d для многочлена, рассмотреть разложение n по основанию m (допуская цифры от − m до m ) для ряда различных m порядка n. 1/ д и выберите f ( x ) как полином с наименьшими коэффициентами и g ( x ) как x − m .
числовых полей Z [ r1 ] и Z [ r2 — ], где и корни r2 f Рассмотрим кольца многочленов g и r1 . Поскольку f имеет степень d с целыми коэффициентами, если a и b будет целыми числами. являются целыми числами, то и b д · f ( a / b ), который мы называем r . Аналогично, s = b и · 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 ] с «квадратным корнем», который также можно вычислить. Следует отметить, что использование метода исключения Гаусса не дает оптимального времени работы алгоритма. алгоритмы решения разреженных матриц, такие как Block Lanczos или Block Wiedemann Вместо этого используются .
Поскольку m является корнем как f , так и g по модулю n , существуют гомоморфизмы колец Z [ r1 ] и Z [ r2 ] кольцо Z / n Z (целые числа по модулю n ), которые отображают r1 и r в 2 в m , и эти гомоморфизмы отобразят каждый «квадратный корень» (обычно не представленный как рациональное число) в его целочисленный представитель. Теперь произведение множителей a − mb mod n можно получить в виде квадрата двумя способами — по одному для каждого гомоморфизма. Таким образом, можно найти два числа x и y , причем x 2 − и 2 делится на n, снова с вероятностью не менее половины мы получаем коэффициент n, находя наибольший общий делитель n и и x − y .
Улучшение полиномиального выбора
[ редактировать ]Выбор полинома может существенно повлиять на время завершения оставшейся части алгоритма. Показанный выше метод выбора полиномов на основе разложения n по основанию m неоптимален во многих практических ситуациях, что приводит к разработке более совершенных методов.
Один из таких методов был предложен Мерфи и Брентом; [3] они вводят оценку, состоящую из двух частей, для полиномов, основанную на наличии корней по модулю малых простых чисел и на среднем значении, которое полином принимает по площади просеивания.
Наилучшие заявленные результаты [4] были достигнуты методом Торстена Кляйнъюнга , [5] который допускает g ( x ) = ax + b и выполняет поиск по совокупности маленьких простых множителей, конгруэнтных 1 по модулю 2 d , и по старшим коэффициентам f , которые делятся на 60.
Реализации
[ редактировать ]Некоторые реализации фокусируются на определенном меньшем классе чисел. Они известны как методы сита специального числового поля , например, используемые в проекте Каннингема .Проект под названием NFSNET работал с 2002 года. [6] по крайней мере до 2007 года. Он использовал добровольные распределенные вычисления в Интернете . [7] Пол Лейланд из Великобритании и Ричард Вакербарт из Техаса. В этом участвовали [8]
До 2007 года реализацией золотого стандарта был набор программного обеспечения, разработанный и распространяемый CWI в Нидерландах, который был доступен только по относительно ограничительной лицензии. [ нужна ссылка ] В 2007 году Джейсон Пападопулос разработал более быструю реализацию окончательной обработки в рамках msieve, которая находится в открытом доступе. Обе реализации имеют возможность распределения между несколькими узлами кластера с достаточно быстрым межсоединением.
Полиномиальный выбор обычно выполняется с помощью программного обеспечения GPL, написанного Кляйнджунгом, или msieve, а решеточное просеивание - с помощью программного обеспечения GPL, написанного Франке и Кляйнджунгом; они распространяются в GGNFS.
- НФС@Дом
- ГГНФС
- фактор по gnfs
- КАДО-НФС
- msieve (который содержит код окончательной обработки, полиномиальный выбор, оптимизированный для меньших чисел, и реализацию линейного сита)
- кмГНФС
См. также
[ редактировать ]Примечания
[ редактировать ]- ^ Померанс, Карл (декабрь 1996 г.). «Сказка о двух решетах» (PDF) . Уведомления АМС . Том. 43, нет. 12. стр. 1473–1485.
- ^ Рибенбойм, Пауло (1972). Алгебраические числа . Уайли-Интерсайенс. ISBN 978-0-471-71804-8 .
- ^ Мерфи, Б.; Брент, Р.П. (1998), «О квадратичных полиномах для сита числового поля» , Australian Computer Science Communications , 20 : 199–213.
- ^ Франке, Йенс (2006), О проектах RSA 200 и более крупных (PDF)
- ^ Кляйнджунг, Торстен (октябрь 2006 г.). «О полиномиальном выборе для сита общего числового поля» (PDF) . Математика вычислений . 75 (256): 2037–2047. Бибкод : 2006MaCom..75.2037K . дои : 10.1090/S0025-5718-06-01870-9 . Проверено 13 декабря 2007 г.
- ^ Пол Лейланд (12 декабря 2003 г.). «NFSNET: первый год» . Презентация на семинаре EIDMA-CWI по факторингу больших чисел . Проверено 9 августа 2011 г.
- ^ «Добро пожаловать в NFSNET» . 23 апреля 2007 года. Архивировано из оригинала 22 октября 2007 года . Проверено 9 августа 2011 г.
- ^ «О NFSNET» . Архивировано из оригинала 9 мая 2008 года . Проверено 9 августа 2011 г.
Ссылки
[ редактировать ]- Арьен К. Ленстра и Х.В. Ленстра-младший (ред.). «Разработка решета числового поля». Конспект лекций по математике. (1993) 1554. Спрингер-Верлаг.
- Ричард Крэндалл и Карл Померанс . Простые числа: вычислительная перспектива (2001). 2-е издание, Спрингер. ISBN 0-387-25282-7 . Раздел 6.2: Решето числового поля, стр. 278–301.
- Мэтью Э. Бриггс: Введение в сито общего числового поля, 1998 г.