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

Нерешенная задача в информатике :

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

(еще нерешенные проблемы по информатике)

В теории чисел факторизация целых чисел — это разложение целого положительного числа в произведение целых чисел. Каждое положительное целое число больше 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 а 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$ . Ни существование, ни отсутствие таких алгоритмов не доказано, но обычно предполагается, что их не существует. ^[4]^[5]

Существуют опубликованные алгоритмы, которые быстрее, чем $O((1 + ε) б)$ для всех положительных $ε$ , то есть субэкспоненциально . По состоянию на 2022 год ^[update]алгоритмом с лучшим теоретическим асимптотическим временем работы является решето общего числового поля (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(b 3)$ время и $пространство O(b)$ на $входах b$ -битных чисел. В 2001 году алгоритм Шора был впервые реализован с использованием методов ЯМР на молекулах, содержащих семь кубитов. ^[7]

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

Проблема принятия решения (целочисленная факторизация) — для любых натуральных чисел $n$ и $k$ , имеет ли $n$ коэффициент меньший, чем $k,$ кроме 1?

Известно, что он находится как в 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 )$ с $d \leq k$ . Ответ «нет» можно подтвердить, продемонстрировав разложение $n$ на отдельные простые числа, все больше $k$ ; их простоту можно проверить с помощью теста простоты AKS , а затем умножить их, чтобы получить $n$ . Фундаментальная теорема арифметики гарантирует, что будет принята только одна возможная строка возрастающих простых чисел, что показывает, что проблема заключается как в UP , так и в co-UP. ^[8] Известно, что он находится в BQP благодаря алгоритму Шора.

Предполагается, что проблема находится за пределами всех трех классов сложности: P, NP-полная, ^[9]и со-NP-полный . Таким образом, он является кандидатом на класс сложности NP-среднего уровня .

Напротив, проблема решения «Является ли $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$ с символом Кронекера $(Δ / q) знак равно 1$ . Путем построения набора образующих G $группы Δ$ и простых форм $q в$ G $Δ с$ q $Δ$ P $создается q$ отношений между набором образующих и $f f$ последовательность . Размер $q$ может быть ограничен $c 0 (log| Δ |) 2$ для некоторой постоянной $c 0$ .

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

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

Пусть $∆$ — отрицательное целое число с $∆ = - dn$ , где $d$ — множитель, а $∆$ — отрицательный дискриминант некоторой квадратичной формы.
Возьмем $t$ первых простых чисел $p 1 = 2, p 2 = 3, p 3 = 5, ..., p t$ для некоторого $t \in N$ .
Пусть $f q$ — случайная простая форма группы $G ∆$ такая, что $(Д / q) знак равно 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 в)$ или $Δ знак равно (б - 2 а)(б + 2 а)$ .
Если неоднозначная форма обеспечивает факторизацию $n$ , остановитесь, в противном случае найдите другую неоднозначную форму, пока не будет найдена факторизация $n$ . Чтобы предотвратить возникновение бесполезных неоднозначных форм, создайте 2-силовскую группу $Sll 2 (Δ)$ группы $G (Δ)$ .

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

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

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

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

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

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

^ Ленстра, Арьен К. (2011), «Целочисленный факторинг» , в ван Тилборге, Хенк, Калифорния; Джаджодиа, Сушил (ред.), Энциклопедия криптографии и безопасности , Бостон, Массачусетс: Springer US, стр. 611–618, doi : 10.1007/978-1-4419-5906-5_455 , ISBN 978-1-4419-5905-8 , получено 22 июня 2022 г.
^ «[Cado-nfs-discuss] 795-битный факторинг и дискретные логарифмы» . Архивировано из оригинала 2 декабря 2019 г.
^ Кляйнъунг, Торстен; Аоки, Кадзумаро; Франке, Йенс; Ленстра, Арьен К.; Томе, Эммануэль; Бос, Йоппе В.; Годри, Пьеррик; Круппа, Александр; Монтгомери, Питер Л.; Освик, Даг Арне; те Риле, Герман Дж.Дж.; Тимофеев Андрей; Циммерманн, Пол (2010). «Факторизация 768-битного модуля RSA» (PDF) . У Рабина, Таль (ред.). Достижения в криптологии — CRYPTO 2010, 30-я ежегодная конференция по криптологии, Санта-Барбара, Калифорния, США, 15–19 августа 2010 г. Материалы . Конспекты лекций по информатике. Том. 6223. Спрингер. стр. 333–350. дои : 10.1007/978-3-642-14623-7_18 .
^ Кранц, Стивен Г. (2011), Доказательство в пудинге: меняющаяся природа математического доказательства , Нью-Йорк: Springer, стр. 203, номер домена : 10.1007/978-0-387-48744-1 , ISBN. 978-0-387-48908-7 , МР 2789493
^ Арора, Санджив ; Барак, Боаз (2009), Вычислительная сложность , Кембридж: Издательство Кембриджского университета, стр. 230, номер домена : 10.1017/CBO9780511804090 , ISBN 978-0-521-42426-4 , МР 2500087 , S2CID 215746906
^ Бюлер, JP; Ленстра, Х.В. младший; Померанс, Карл (1993). «Факторизация целых чисел с помощью сита числового поля». Разработка решета числового поля . Конспект лекций по математике. Том. 1554. Спрингер. стр. 50–94. дои : 10.1007/BFb0091539 . hdl : 1887/2149 . ISBN 978-3-540-57013-4 . Проверено 12 марта 2021 г.
^ Вандерсипен, Ливен МК; и другие. (2001). «Экспериментальная реализация алгоритма квантового факторинга Шора с использованием ядерного магнитного резонанса». Природа . 414 (6866): 883–887. arXiv : Quant-ph/0112176 . Бибкод : 2001Natur.414..883V . дои : 10.1038/414883a . ПМИД 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 .
^ Перейти обратно: ^а ^б Дэвид Брессуд и Стэн Вагон (2000). Курс вычислительной теории чисел . Издательство Ключевого колледжа / Springer. стр. 168–69 . ISBN 978-1-930190-10-8 .
^ Шнорр, Клаус П. (1982). «Усовершенствованный анализ и улучшения некоторых алгоритмов факторинга» . Журнал алгоритмов . 3 (2): 101–127. дои : 10.1016/0196-6774(82)90012-8 . МР 0657269 . Архивировано из оригинала 24 сентября 2017 года.
^ Сейсен, Мартин (1987). «Алгоритм вероятностной факторизации с квадратичными формами отрицательного дискриминанта» . Математика вычислений . 48 (178): 757–780. doi : 10.1090/S0025-5718-1987-0878705-X . МР 0878705 .
^ Ленстра, Арьен К. (1988). «Быстрая и строгая факторизация в соответствии с обобщенной гипотезой Римана» (PDF) . Indagationes Mathematicae . 50 (4): 443–454. дои : 10.1016/S1385-7258(88)80022-2 .
^ Перейти обратно: ^а ^б Ленстра, HW; Померанс, Карл (июль 1992 г.). «Жесткие сроки факторизации целых чисел» (PDF) . Журнал Американского математического общества . 5 (3): 483–516. дои : 10.1090/S0894-0347-1992-1137100-0 . МР 1137100 .

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

Ричард Крэндалл и Карл Померанс (2001). Простые числа: вычислительная перспектива . Спрингер. 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-е изд.). Аддисон Уэсли - Pearson Education, Inc. ISBN 978-0-321-84268-8 .

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

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

[1] Ленстра, Арьен К. (2011), «Целочисленный факторинг» , в ван Тилборге, Хенк, Калифорния; Джаджодиа, Сушил (ред.), Энциклопедия криптографии и безопасности , Бостон, Массачусетс: Springer US, стр. 611–618, doi : 10.1007/978-1-4419-5906-5_455 , ISBN 978-1-4419-5905-8 , получено 22 июня 2022 г.

[2] «[Cado-nfs-discuss] 795-битный факторинг и дискретные логарифмы» . Архивировано из оригинала 2 декабря 2019 г.

[rsa768-3] Кляйнъунг, Торстен; Аоки, Кадзумаро; Франке, Йенс; Ленстра, Арьен К.; Томе, Эммануэль; Бос, Йоппе В.; Годри, Пьеррик; Круппа, Александр; Монтгомери, Питер Л.; Освик, Даг Арне; те Риле, Герман Дж.Дж.; Тимофеев Андрей; Циммерманн, Пол (2010). «Факторизация 768-битного модуля RSA» (PDF) . У Рабина, Таль (ред.). Достижения в криптологии — CRYPTO 2010, 30-я ежегодная конференция по криптологии, Санта-Барбара, Калифорния, США, 15–19 августа 2010 г. Материалы . Конспекты лекций по информатике. Том. 6223. Спрингер. стр. 333–350. дои : 10.1007/978-3-642-14623-7_18 .

[4] Кранц, Стивен Г. (2011), Доказательство в пудинге: меняющаяся природа математического доказательства , Нью-Йорк: Springer, стр. 203, номер домена : 10.1007/978-0-387-48744-1 , ISBN. 978-0-387-48908-7 , МР 2789493

[5] Арора, Санджив ; Барак, Боаз (2009), Вычислительная сложность , Кембридж: Издательство Кембриджского университета, стр. 230, номер домена : 10.1017/CBO9780511804090 , ISBN 978-0-521-42426-4 , МР 2500087 , S2CID 215746906

[6] Бюлер, JP; Ленстра, Х.В. младший; Померанс, Карл (1993). «Факторизация целых чисел с помощью сита числового поля». Разработка решета числового поля . Конспект лекций по математике. Том. 1554. Спрингер. стр. 50–94. дои : 10.1007/BFb0091539 . hdl : 1887/2149 . ISBN 978-3-540-57013-4 . Проверено 12 марта 2021 г.

[7] Вандерсипен, Ливен МК; и другие. (2001). «Экспериментальная реализация алгоритма квантового факторинга Шора с использованием ядерного магнитного резонанса». Природа . 414 (6866): 883–887. arXiv : Quant-ph/0112176 . Бибкод : 2001Natur.414..883V . дои : 10.1038/414883a . ПМИД 11780055 . S2CID 4400832 .

[8] Лэнс Фортноу (13 сентября 2002 г.). «Блог о сложности вычислений: Класс сложности недели: факторинг» .

[9] Гольдрейх, Одед ; Вигдерсон, Ави (2008), «IV.20 Вычислительная сложность», Гауэрс, Тимоти ; Барроу-Грин, июнь ; Лидер, Имре (ред.), The Princeton Companion to Mathematics , Принстон, Нью-Джерси: Princeton University Press, стр. 575–604, ISBN 978-0-691-11880-2 , МР 2467561 . См., в частности , стр. 583 .

[Bressoud_and_Wagon-10] Перейти обратно: ^а ^б Дэвид Брессуд и Стэн Вагон (2000). Курс вычислительной теории чисел . Издательство Ключевого колледжа / Springer. стр. 168–69 . ISBN 978-1-930190-10-8 .

[1982-schnorr-11] Шнорр, Клаус П. (1982). «Усовершенствованный анализ и улучшения некоторых алгоритмов факторинга» . Журнал алгоритмов . 3 (2): 101–127. дои : 10.1016/0196-6774(82)90012-8 . МР 0657269 . Архивировано из оригинала 24 сентября 2017 года.

[1987-seysen-12] Сейсен, Мартин (1987). «Алгоритм вероятностной факторизации с квадратичными формами отрицательного дискриминанта» . Математика вычислений . 48 (178): 757–780. doi : 10.1090/S0025-5718-1987-0878705-X . МР 0878705 .

[1988-lenstra-13] Ленстра, Арьен К. (1988). «Быстрая и строгая факторизация в соответствии с обобщенной гипотезой Римана» (PDF) . Indagationes Mathematicae . 50 (4): 443–454. дои : 10.1016/S1385-7258(88)80022-2 .

[lenstra-pomerance-14] Перейти обратно: ^а ^б Ленстра, HW; Померанс, Карл (июль 1992 г.). «Жесткие сроки факторизации целых чисел» (PDF) . Журнал Американского математического общества . 5 (3): 483–516. дои : 10.1090/S0894-0347-1992-1137100-0 . МР 1137100 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

v т Это Допущения о вычислительной сложности
Number theoretic	Integer factorization Phi-hiding RSA problem Strong RSA Quadratic residuosity Decisional composite residuosity Higher residuosity
Group theoretic	Discrete logarithm Diffie-Hellman Decisional Diffie–Hellman Computational Diffie–Hellman
Pairings	External Diffie–Hellman Sub-group hiding Decision linear
Lattices	Shortest vector problem (gap) Closest vector problem (gap) Learning with errors Ring learning with errors Short integer solution
Non-cryptographic	Exponential time hypothesis Unique games conjecture Planted clique conjecture

v т Это Теоретико-числовые алгоритмы
Primality tests	AKS APR Baillie–PSW Elliptic curve Pocklington Fermat Lucas Lucas–Lehmer Lucas–Lehmer–Riesel Proth's theorem Pépin's Quadratic Frobenius Solovay–Strassen Miller–Rabin
Prime-generating	Sieve of Atkin Sieve of Eratosthenes Sieve of Pritchard Sieve of Sundaram Wheel factorization
Integer factorization	Continued fraction (CFRAC) Dixon's Lenstra elliptic curve (ECM) Euler's Pollard's rho p − 1 p + 1 Quadratic sieve (QS) General number field sieve (GNFS) Special number field sieve (SNFS) Rational sieve Fermat's Shanks's square forms Trial division Shor's
Multiplication	Ancient Egyptian Long Karatsuba Toom–Cook Schönhage–Strassen Fürer's
Euclidean division	Binary Chunking Fourier Goldschmidt Newton-Raphson Long Short SRT
Discrete logarithm	Baby-step giant-step Pollard rho Pollard kangaroo Pohlig–Hellman Index calculus Function field sieve
Greatest common divisor	Binary Euclidean Extended Euclidean Lehmer's
Modular square root	Cipolla Pocklington's Tonelli–Shanks Berlekamp Kunerth
Other algorithms	Chakravala Cornacchia Exponentiation by squaring Integer square root Integer relation (LLL; KZ) Modular exponentiation Montgomery reduction Schoof Trachtenberg system
Italics indicate that algorithm is for numbers of special forms

v т Это Наборы целых чисел на основе делимости
Overview	Integer factorization Divisor Unitary divisor Divisor function Prime factor Fundamental theorem of arithmetic
Factorization forms	Prime Composite Semiprime Pronic Sphenic Square-free Powerful Perfect power Achilles Smooth Regular Rough Unusual
Constrained divisor sums	Perfect Almost perfect Quasiperfect Multiply perfect Hemiperfect Hyperperfect Superperfect Unitary perfect Semiperfect Practical Erdős–Nicolas
With many divisors	Abundant Primitive abundant Highly abundant Superabundant Colossally abundant Highly composite Superior highly composite Weird
Aliquot sequence-related	Untouchable Amicable (Triple) Sociable Betrothed
Base-dependent	Equidigital Extravagant Frugal Harshad Polydivisible Smith
Other sets	Arithmetic Deficient Friendly Solitary Sublime Harmonic divisor Descartes Refactorable Superperfect