Факторизация целых чисел

Нерешенная проблема в информатике :

Можно ли решить задачу факторизации целых чисел за полиномиальное время на классическом компьютере?

В математике факторизация целых чисел — это разложение положительного целого числа на произведение целых чисел. Каждое положительное целое число, большее 1, является либо произведением двух или более целых множителей, больших 1, в этом случае оно называется составным числом , либо не является таковым, в этом случае оно называется простым числом . Например, $15$ является составным числом, потому что $15 = 3 \cdot 5$ , но $7$ является простым числом, потому что его нельзя разложить таким образом. Если один из множителей является составным, его, в свою очередь, можно записать в виде произведения меньших множителей, например, $60 = 3 \cdot 20 = 3 \cdot (5 \cdot 4)$ . Продолжение этого процесса до тех пор, пока каждый множитель не станет простым, называется разложением на простые множители ; результат всегда уникален с точностью до порядка множителей по теореме о разложении на простые множители .

Чтобы разложить небольшое целое число $n$ с помощью устной или бумажной арифметики, самым простым методом является пробное деление : проверка того, делится ли число на простые числа $2$ , $3$ , $5$ и так далее, вплоть до квадратного корня из $n$ . Для больших чисел, особенно при использовании компьютера, более эффективны различные более сложные алгоритмы факторизации. Алгоритм факторизации на простые числа обычно включает проверку того, является ли каждый множитель простым, каждый раз, когда множитель находится.

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

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

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

Разложение простого числа

Разложение $n = 864$ на простые числа как $25 \times 3 3$

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

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

Текущее состояние дел

Среди $b$ -битных чисел наиболее сложными для практического факторизации с использованием существующих алгоритмов являются те полупростые числа , множители которых имеют схожий размер. По этой причине эти целые числа используются в криптографических приложениях.

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

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

Сложность времени

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

Существуют опубликованные алгоритмы, которые быстрее, чем $O((1 + ε) b)$ для всех положительных $ε$ , то есть субэкспоненциальные . По состоянию на 2022 год ^{[обновлять]}алгоритм с наилучшим теоретическим асимптотическим временем работы — это решето общего числового поля (GNFS), впервые опубликованное в 1993 году ^[6] , работающее на $b$ -битном числе $n$ за время:

\exp \left(\left(\left({\tfrac {8}{3}}\right)^{\frac {2}{3}}+o(1)\right)\left(\log n\right)^{\frac {1}{3}}\left(\log \log n\right)^{\frac {2}{3}}\right).

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

Чтобы говорить о таких классах сложности , как P, NP и co-NP, задачу необходимо сформулировать как задачу принятия решения .

Задача принятия решения (разложение целых чисел) — Для каждого натурального числа и имеет ли $n$ множитель, меньший $k,$ чем 1? $n$ $к$

Известно, что он находится как в NP , так и в co-NP , что означает, что ответы "да" и "нет" могут быть проверены за полиномиальное время. Ответ "да" может быть удостоверен путем демонстрации факторизации $n = d ( .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠н/г⁠ )$ с $d \leq k$ . Ответ «нет» может быть подтвержден путем демонстрации факторизации $n$ на различные простые числа, все из которых больше $k$ ; можно проверить их простоту с помощью теста простоты AKS , а затем умножить их, чтобы получить $n$ . Основная теорема арифметики гарантирует, что существует только одна возможная строка увеличивающихся простых чисел, которая будет принята, что показывает, что проблема находится как в UP, так и в co-UP.^[8] Известно, что она находится в BQP из-за алгоритма Шора.

Предполагается, что задача находится за пределами всех трех классов сложности P, NP-complete, ^[9] и co-NP-complete . Поэтому она является кандидатом на класс сложности NP-intermediate .

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

Алгоритмы факторинга

Специального назначения

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

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

Судебное отделение
Факторизация колеса
Алгоритм Ро Полларда , который имеет два общих варианта для определения групповых циклов : один по Флойду и один по Бренту.
Алгоритмы факторизации алгебраических групп , среди которых алгоритм Полларда $p - 1$ , алгоритм Уильямса $p + 1$ и факторизация эллиптической кривой Ленстры
Метод факторизации Ферма
Метод факторизации Эйлера
Специальное числовое поле сито
Разность двух квадратов

Универсальный

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

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

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

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

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

L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]=e^{(1+o(1)){\sqrt {(\log n)(\log \log n)}}}

в little-o и L-нотации . Некоторые примеры таких алгоритмов — метод эллиптической кривой и квадратичное решето . Другой такой алгоритм — метод отношений групп классов , предложенный Шнорром ^[11] , Сейзеном ^[12] и Ленстрой ^[13] , который они доказали, только предполагая недоказанную обобщенную гипотезу Римана .

Строгое время выполнения

^{Ленстра и Померанс [14]} строго доказали, что вероятностный алгоритм Шнорра–Сейзена–Ленстры имеет ожидаемое время работы $L n [⁠ 1 / 2 ⁠, 1+ o (1)]$ путем замены предположения GRH на использование множителей. Алгоритм использует группу классов положительных бинарных квадратичных форм дискриминанта $Δ,$ обозначенную как $G$ $Δ$ . $G$ $Δ$ — это множество троек целых чисел $($ $a$ $,$ $b$ $,$ $c$ $)$ , в которых эти целые числа являются взаимно простыми.

Алгоритм Шнорра – Зейсена – Ленстры

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

Обозначим через $P Δ$ множество всех простых чисел $q$ с символом Кронекера $(⁠ Δ / д ⁠) = 1$ . Построив наборгенераторовG $Δ$ и простые формы $f$ $q$ из $G$ $Δ$ с $q$ в $P$ $Δ,$ получим последовательность соотношений между набором генераторов и $f$ $q$ . Размер $q$ можно ограничить величиной $c$ $0$ $(log|$ $Δ$ $|)$ $2 для$ $некоторой$ константы $c$ $0$ .

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

Пусть $n —$ число, которое нужно разложить на множители.

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

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

Ожидаемое время работы

Алгоритм, как указано, является вероятностным алгоритмом , поскольку он делает случайный выбор. Его ожидаемое время выполнения составляет не более $L n [⁠ 1 / 2 ⁠, 1+ o (1)]$ .^[14]

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

Орифейлевская факторизация
Алгоритм Баха для генерации случайных чисел с помощью их факторизации
Каноническое представление положительного целого числа
Факторизация
Мультипликативное разбиение
$p-$ адическая оценка
Целочисленное разбиение — способ записи числа в виде суммы положительных целых чисел.

Примечания

^ Lenstra, Arjen K. (2011), «Целочисленная факторизация», в van Tilborg, Henk CA; Jajodia, Sushil (ред.), Encyclopedia of Cryptography and Security , Бостон, MA: Springer US, стр. 611–618, doi :10.1007/978-1-4419-5906-5_455, ISBN 978-1-4419-5905-8, получено 2022-06-22
^ "[Cado-nfs-discuss] 795-битная факторизация и дискретные логарифмы". Архивировано из оригинала 2019-12-02.
^ Kleinjung, Thorsten; Aoki, Kazumaro; Franke, Jens; Lenstra, Arjen K.; Thomé, Emmanuel; Bos, Joppe W.; Gaudry, Pierrick; Kruppa, Alexander; Montgomery, Peter L.; Osvik, Dag Arne; te Riele, Herman JJ; Timofeev, Андрей; Zimmermann, Paul (2010). "Factorization of a 768-Bit RSA Modulus" (PDF) . В Rabin, Tal (ред.). Advances in Cryptology - CRYPTO 2010, 30-я ежегодная конференция по криптологии, Санта-Барбара, Калифорния, США, 15-19 августа 2010 г. Труды . Lecture Notes in Computer Science. Vol. 6223. Springer. pp. 333–350. doi :10.1007/978-3-642-14623-7_18.
^ Кранц, Стивен Г. (2011), Доказательство в пудинге: Изменение природы математического доказательства, Нью-Йорк: Springer, стр. 203, doi :10.1007/978-0-387-48744-1, ISBN 978-0-387-48908-7, г-н 2789493
^ Арора, Санджив ; Барак, Боаз (2009), Сложность вычислений, Кембридж: Издательство Кембриджского университета, стр. 230, doi : 10.1017/CBO9780511804090, ISBN 978-0-521-42426-4, MR 2500087, S2CID 215746906
^ Buhler, JP; Lenstra, HW Jr.; Pomerance, Carl (1993). «Разложение целых чисел на множители с помощью решета числового поля». Развитие решета числового поля. Lecture Notes in Mathematics. Vol. 1554. Springer. pp. 50–94. doi :10.1007/BFb0091539. hdl :1887/2149. ISBN 978-3-540-57013-4. Получено 12 марта 2021 г. .
^ Вандерсипен, Ливен МК; и др. (2001). «Экспериментальная реализация алгоритма квантовой факторизации Шора с использованием ядерного магнитного резонанса». Nature . 414 (6866): 883–887. arXiv : quant-ph/0112176 . Bibcode :2001Natur.414..883V. doi :10.1038/414883a. PMID 11780055. S2CID 4400832.
^ Лэнс Фортноу (13 сентября 2002 г.). «Блог о сложности вычислений: Класс сложности недели: Факторизация».
^ Голдрайх, Одед ; Вигдерсон, Ави (2008), «IV.20 Вычислительная сложность», в Гауэрс, Тимоти ; Барроу-Грин, Джун ; Лидер, Имре (ред.), The Princeton Companion to Mathematics , Принстон, Нью-Джерси: Princeton University Press, стр. 575–604, ISBN 978-0-691-11880-2, г-н 2467561. См. в частности стр. 583.
^ ab Дэвид Брессо и Стэн Вагон (2000). Курс вычислительной теории чисел . Key College Publishing/Springer. стр. 168–69. ISBN 978-1-930190-10-8.
^ Шнорр, Клаус П. (1982). «Усовершенствованный анализ и улучшения некоторых алгоритмов факторизации». Журнал алгоритмов . 3 (2): 101–127. doi :10.1016/0196-6774(82)90012-8. MR 0657269. Архивировано из оригинала 24 сентября 2017 г.
^ Сейсен, Мартин (1987). «Вероятностный алгоритм факторизации с квадратичными формами отрицательного дискриминанта». Математика вычислений . 48 (178): 757–780. doi : 10.1090/S0025-5718-1987-0878705-X . MR 0878705.
^ Lenstra, Arjen K (1988). «Быстрая и строгая факторизация при обобщенной гипотезе Римана» (PDF) . Indagationes Mathematicae . 50 (4): 443–454. doi :10.1016/S1385-7258(88)80022-2.
^ ab Lenstra, HW; Pomerance, Carl (июль 1992 г.). "Строгая временная граница для факторизации целых чисел" (PDF) . Журнал Американского математического общества . 5 (3): 483–516. doi : 10.1090/S0894-0347-1992-1137100-0 . MR 1137100.

Ссылки

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

Внешние ссылки

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