Целочисленная факторизация

Нерешенная проблема в информатике : Может ли целочисленная факторизация быть решена за полиномиальное время на классическом компьютере? (больше нерешенных проблем в информатике)

В теории чисел , целое число , разложение является разложение составного числа в произведение меньших чисел. Если эти множители дополнительно ограничиваются простыми числами , процесс называется простой факторизацией .

Когда числа достаточно велики, не известен эффективный неквантовый алгоритм целочисленной факторизации . В 2019 году Фабрис Будо, Пьер Годри, Аврора Гильевич, Надя Хенингер, Эммануэль Томе и Пол Циммерманн разложили на множители 240-значное число ( RSA-240 ), используя примерно 900 основных лет вычислительной мощности. ^[1] Исследователи подсчитали, что 1024-битный модуль RSA займет примерно в 500 раз больше времени. ^[2] Однако не было доказано, что не существует эффективного алгоритма. Предполагаемая сложность этой проблемы лежит в основе широко используемых алгоритмов в криптографии, таких как RSA . Многие области математики иИнформатика была привлечена к решению этой проблемы, включая эллиптические кривые , алгебраическую теорию чисел и квантовые вычисления .

Не все числа заданной длины одинаково сложно разложить на множители. Самыми сложными примерами этих проблем (для известных в настоящее время методов) являются полупростые числа , произведение двух простых чисел. Когда они оба большие, например, длиной более двух тысяч бит , выбираются случайным образом и примерно одинакового размера (но не слишком близко, например, чтобы избежать эффективной факторизации методом факторизации Ферма ), даже самые быстрые алгоритмы разложения на простые множители на самым быстрым компьютерам может потребоваться достаточно времени, чтобы сделать поиск непрактичным; то есть по мере увеличения числа разрядов простых чисел, разлагаемых на множители, количество операций, необходимых для выполнения факторизации на любом компьютере, резко возрастает.

Многие криптографические протоколы основаны на сложности факторизации больших составных целых чисел или связанной проблеме, например, проблеме RSA . Алгоритм, который эффективно учитывает произвольное целое число, сделает криптографию с открытым ключом на основе RSA небезопасной.

Разложение на простые числа [ править ]

По основной теореме арифметики каждое натуральное число имеет единственное разложение на простые множители . (По соглашению 1 - это пустой продукт .) Проверить , является ли целое число простым, можно за полиномиальное время , например, с помощью теста простоты AKS . Однако, если они составные, тесты на полиномиальное время не дают понимания того, как получить коэффициенты.

Учитывая общий алгоритм целочисленной факторизации, любое целое число может быть разложено на составляющие его простые множители путем повторного применения этого алгоритма. Ситуация более сложная со специализированными алгоритмами факторизации, преимущества которых могут не быть реализованы также или даже не реализованы с факторами, полученными во время разложения. Например, если n = 171 × p × q, где p < q - очень большие простые числа, пробное деление быстро произведет множители 3 и 19, но потребует p делений, чтобы найти следующий множитель. В качестве контрастного примера, если nявляется произведением простых чисел 13729, 1372933 и 18848997161, где 13729 × 1372933 = 18848997157 , метод факторизации Ферма начинается с a = ⌈ √ n ⌉ = 18848997159, что сразу дает b = √ a ² - n = √ 4 = 2 и отсюда множители a - b = 18848997157 и a + b = 18848997161 . Хотя они легко распознаются как составные и простые соответственно, метод Ферма потребует гораздо больше времени, чтобы разложить составное число на множители, поскольку начальное значение⌈ √ 18848997157 ⌉ = 137292 для a далеко не 1372933.

Текущее состояние [ править ]

Среди b- битных чисел сложнее всего разложить на множители с использованием существующих алгоритмов те, которые являются произведением двух простых чисел одинакового размера. По этой причине эти целые числа используются в криптографических приложениях. Самым крупным из таких полупростых чисел, который когда-либо учитывался, был RSA-250 , 829-битное число с 250 десятичными знаками, в феврале 2020 года. Общее время вычислений составило примерно 2700 ядерно-лет вычислений с использованием Intel Xeon Gold 6130 на частоте 2,1 ГГц. Как и все недавние записи факторизации, эта факторизация была завершена высокооптимизированной реализацией сита общего числового поля, запущенного на сотнях машин.

Сложность и сложность [ править ]

Не опубликовано ни одного алгоритма , который мог бы разложить все целые числа на множители за полиномиальное время , то есть разложить b- битное число n на множители за время O ( b ^k ) для некоторой константы k . Ни существование, ни отсутствие таких алгоритмов не было доказано, но обычно предполагается, что их не существует и, следовательно, проблема не в классе P. ^{[3] [4]} Проблема явно в классе NP, но обычно предполагается, что он не является NP-полным , хотя это не было доказано. ^[5]

Есть опубликованные алгоритмы, которые быстрее, чем O ((1 +  ε ) ^b ) для всех положительных ε , то есть субэкспоненциальные . Опубликованный алгоритм с наилучшим асимптотическим временем работы ^{[ когда? ]} - решето общего числового поля ( GNFS ), работающее с b- битным числом n во времени: ^{[ требуется пояснение ]}

${\ displaystyle \ exp \ left (\ left ({\ sqrt [{3}] {\ frac {64} {9}}} + o (1) \ right) (\ ln n) ^ {\ frac {1}) {3}} (\ ln \ ln n) ^ {\ frac {2} {3}} \ right).}$

Для современных компьютеров GNFS - лучший опубликованный алгоритм для больших n (более 400 бит). Для квантового компьютера , однако, Питер Шор обнаружил алгоритм в 1994 году , который решает его в полиномиальное время. Это будет иметь серьезные последствия для криптографии, если квантовые вычисления станут масштабируемыми. Алгоритм Шора занимает только O ( b ³ ) времени и O ( b ) пространства на входных b- битных числах. В 2001 году алгоритм Шора был впервые реализован с использованием методов ЯМР на молекулах, содержащих 7 кубитов. ^[6]

Неизвестно, какие именно классы сложности содержат вариант решения задачи целочисленной факторизации (то есть: имеет ли n коэффициент меньше k ?). Известно, что он присутствует как в NP, так и в co-NP , что означает, что оба ответа «да» и «нет» могут быть проверены за полиномиальное время. Ответ «да» может быть подтвержден факторизацией n = d ( n / d ) с d ≤ k . Ответ "нет" может быть подтвержден демонстрацией факторизации n на различные простые числа, все больше k.; можно проверить их простоту, используя тест на простоту AKS , а затем умножить их, чтобы получить n . Основная теорема арифметики гарантирует , что существует только одна возможная строка увеличивающихся простых чисел , которые будут приняты, что свидетельствует о том , что проблема в обоих UP и со-UP. ^[7] Известно, что он входит в BQP из-за алгоритма Шора.

Предполагается, что проблема находится вне всех трех классов сложности P, NP-полной и co-NP-полной . Таким образом, он является кандидатом в NP-средний класс сложности. Если бы можно было доказать, что он является либо NP-полным, либо co-NP-полным, это означало бы NP = co-NP, очень неожиданный результат, и поэтому многие подозревают, что целочисленная факторизация находится за пределами обоих этих классов. Многие люди пытались найти для него классические алгоритмы с полиномиальным временем, но потерпели неудачу, поэтому многие подозревают, что он находится за пределами P.

Напротив, проблема решения "Является ли n составным числом?" (или эквивалентно: «Является ли n простым числом?») оказывается намного проще, чем проблема определения множителей n . Задача составного / простого числа может быть решена за полиномиальное время (в количестве b цифр n ) с помощью теста простоты AKS . Кроме того, существует несколько вероятностных алгоритмов, которые могут очень быстро проверить простоту на практике, если кто-то готов допустить исчезающе малую вероятность ошибки. Простота проверки простоты - важная часть алгоритма RSA , так как для начала необходимо найти большие простые числа.

Алгоритмы факторинга [ править ]

Специального назначения [ править ]

Время работы специального алгоритма факторинга зависит от свойств числа, подлежащего факторизации, или от одного из его неизвестных факторов: размера, особой формы и т. Д. Параметры, определяющие время работы, различаются в зависимости от алгоритма.

Важным подклассом специализированных алгоритмов факторинга являются алгоритмы категории 1 или первой категории , время работы которых зависит от размера наименьшего простого множителя. Учитывая целое число неизвестной формы, эти методы обычно применяются перед методами общего назначения для удаления небольших факторов. ^[8] Например, наивное пробное деление - это алгоритм Категории 1.

• Пробный отдел
• Факторизация колес
• Алгоритм ро Полларда
• Алгоритмы факторизации Алгебраическое-группы , среди которых Полларда р  - 1 алгоритм , Williams' р  + 1 алгоритм , и Ленстра эллиптической кривой факторизационные
• Метод факторизации Ферма
• Метод факторизации Эйлера
• Специальное числовое сито

Универсальный [ править ]

Алгоритм общего назначения факторинга, также известный как категории 2 , вторая категория , или Kraitchik семейного алгоритм, ^[8] имеет время , которое зависит исключительно от размера целого числа должны быть учтено. Это тип алгоритма, который используется для факторизации чисел RSA . Большинство алгоритмов факторинга общего назначения основаны на методе сравнения квадратов .

• Алгоритм Диксона
• Факторизация непрерывной дроби (CFRAC)
• Квадратное сито
• Рациональное сито
• Общее числовое поле сито
• Факторизация квадратных форм Шанкса (SQUFOF)

Другие известные алгоритмы [ править ]

• Алгоритм Шора для квантовых компьютеров

Эвристическое время выполнения [ править ]

В теории чисел существует множество алгоритмов целочисленного разложения, которые эвристически ожидали время работы.

${\ displaystyle L_ {n} \ left [{\ tfrac {1} {2}}, 1 + o (1) \ right] = e ^ {(1 + o (1)) {\ sqrt {(\ log n ) (\ журнал \ журнал n)}}}}$

в маленькой и L-нотации . Некоторые примеры этих алгоритмов - метод эллиптической кривой и квадратное решето . Другой такой алгоритм - это метод групповых отношений классов, предложенный Шнорром ^[9] Сейсеном ^[10] и Ленстрой ^[11], который они доказали только в предположении недоказанной обобщенной гипотезы Римана (GRH) .

Жесткое время работы [ править ]

Ленстра и Померанс ^[12] строго доказали, что вероятностный алгоритм Шнорра – Зейсена – Ленстры имеет ожидаемое время выполнения путем замены допущения GRH использованием множителей. Алгоритм использует группу классов положительных бинарных квадратичных форм с дискриминантом А обозначаемых G _А .G _Δ - это набор троек целых чисел ( a , b , c ), в котором эти числа являются относительными простыми числами.${\ displaystyle L_ {n} \ left [{\ tfrac {1} {2}}, 1 + o (1) \ right]}$

Алгоритм Шнорра – Сейсена – Ленстры [ править ]

Дано целое число n, которое будет факторизовано, где n - нечетное положительное целое число, большее определенной константы. В этом алгоритме разложения дискриминант Δ выбирается кратным n , Δ = - dn , где d - некоторый положительный множитель. Алгоритм ожидает, что для одного d существует достаточно гладких форм в G _Δ . Ленстра и Померанс показывают, что выбор d может быть ограничен небольшим набором, чтобы гарантировать результат гладкости.

Обозначим через P _Δ множество всех простых чисел q с символом Кронекера . Путем построения набора образующих группы G _Δ и простых форм f _q группы G _Δ с q в P _Δ получается последовательность отношений между набором образующих и f _q . Размер q может быть ограничен для некоторой константы .${\ displaystyle \ left ({\ tfrac {\ Delta} {q}} \ right) = 1}$${\ Displaystyle c_ {0} (\ журнал | \ Delta |) ^ {2}}$${\ displaystyle c_ {0}}$

Отношение , которое будет использовано это отношение между произведением полномочий, которое равно нейтральным элементом из G _А . Эти отношения будут использоваться для построения так называемой неоднозначной формы G _Δ , которая является элементом G _Δ деления порядка 2. Посредством вычисления соответствующей факторизации Δ и взятия gcd эта неоднозначная форма обеспечивает полную факторизацию простых чисел. из п . Этот алгоритм состоит из следующих основных этапов:

Пусть n будет факторизованным числом.

1. Пусть Δ - отрицательное целое число с Δ = - dn , где d - множитель, а Δ - отрицательный дискриминант некоторой квадратичной формы.
2. Возьмем т первых простых чисел , для некоторых .${\ displaystyle p_ {1} = 2, p_ {2} = 3, p_ {3} = 5, \ dots, p_ {t}}$${\displaystyle t\in {\mathbb {N} }}$
3. Пусть - случайная простая форма группы G _Δ с .${\displaystyle f_{q}}$${\displaystyle \left({\tfrac {\Delta }{q}}\right)=1}$
4. Найдите порождающий X группы G _Δ
5. Соберите последовательность отношений между множеством X и { f _q  : q ∈ P _Δ }, удовлетворяющую:${\displaystyle \left(\prod _{x\in X_{}}x^{r(x)}\right).\left(\prod _{q\in P_{\Delta }}f_{q}^{t(q)}\right)=1}$
6. Построить неоднозначную форму, которая является элементом f ∈ G _Δ порядка деления 2, чтобы получить взаимно простую факторизацию наибольшего нечетного делителя Δ, в которой${\displaystyle (a,b,c)}$${\displaystyle \Delta =-4ac{\text{ or }}a(a-4c){\text{ or }}(b-2a)(b+2a)}$
7. Если неоднозначная форма обеспечивает факторизацию n, тогда остановитесь, в противном случае найдите другую неоднозначную форму, пока не будет найдено факторизация n . Чтобы предотвратить создание бесполезных неоднозначных форм, создайте 2-силовскую группу Sll ₂ (Δ) группы G (Δ).

Чтобы получить алгоритм факторизации любого положительного целого числа, необходимо добавить к этому алгоритму несколько шагов, таких как пробное деление и тест суммы Якоби .

Ожидаемое время работы [ править ]

Заявленный алгоритм является вероятностным, поскольку он делает случайный выбор. Ожидаемое время работы - самое большее . ^[12]${\displaystyle L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]}$

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

• Алгоритм Баха для генерации случайных чисел с их факторизацией
• Каноническое представление положительного целого числа
• Факторизация
• Мультипликативный раздел
• Разделение (теория чисел) - способ записи числа в виде суммы положительных целых чисел.

Примечания [ править ]

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

• Ричард Крэндалл и Карл Померанс (2001). Простые числа: вычислительная перспектива . Springer. ISBN 0-387-94777-9.Глава 5: Алгоритмы экспоненциального факторинга, стр. 191–226. Глава 6: Алгоритмы субэкспоненциального факторинга, стр. 227–284. Раздел 7.4: Метод эллиптических кривых, стр. 301–313.
• Дональд Кнут . Искусство компьютерного программирования , Том 2: получисловые алгоритмы , третье издание. Аддисон-Уэсли, 1997. ISBN 0-201-89684-2 . Раздел 4.5.4: Факторинг на простые числа, стр. 379–417. 
• Сэмюэл С. Вагстафф младший (2013). Радость факторинга . Провиденс, Род-Айленд: Американское математическое общество. ISBN 978-1-4704-1048-3..
• Уоррен-младший, Генри С. (2013). Восторг хакера (2-е изд.). Эддисон Уэсли - ISBN Pearson Education, Inc.  978-0-321-84268-8.

Внешние ссылки [ править ]

• msieve - SIQS и NFS - помог завершить некоторые из крупнейших известных публичных факторизаций
• Ричард П. Брент, "Недавний прогресс и перспективы алгоритмов целочисленной факторизации", Вычислительная техника и комбинаторика " , 2000 г., стр. 3–22. Скачать
• Маниндра Агравал , Нирадж Каял, Нитин Саксена, «ПРИМЕРЫ находится в П.» Анналы математики 160 (2): 781-793 (2004). Версия от августа 2005 г. PDF
• Эрик В. Вайсштейн, «RSA-640 Factored» Заголовок новостей MathWorld , 8 ноября 2005 г.