stringtranslate.com

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

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

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

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

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

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

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

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

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

Простое разложение

Простое разложение n = 864 как 2 5 × 3 3

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

Учитывая общий алгоритм факторизации целых чисел, любое целое число можно разложить на составляющие его простые множители путем многократного применения этого алгоритма. Ситуация сложнее со специальными алгоритмами факторизации, преимущества которых могут быть не реализованы так же или даже вообще не реализованы с факторами, полученными при декомпозиции. Например, если n = 171 × p × q , где p < q — очень большие простые числа, пробное деление быстро даст множители 3 и 19, но для нахождения следующего множителя потребуется p делений. В качестве контрастного примера: если n является произведением простых чисел 13729 , 1372933 и 18848997161 , где 13729 × 1372933 = 18848997157 , метод факторизации Ферма начнется с ⌈ √ n ⌉ = 18848997159 , что немедленно дает b = √ а 2 - п знак равно √ 4 = 2 и, следовательно, множители a − b = 18848997157 и a + b = 18848997161 . Хотя их легко распознать как составные и простые соответственно, методу Ферма потребуется гораздо больше времени для факторизации составного числа, поскольку начальное значение ⌈ √ 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 ( bk ) для некоторой константы k . Ни существование, ни отсутствие таких алгоритмов не доказано, но обычно предполагается, что они не существуют и, следовательно, проблема не в классе P. [4] [5] Проблема явно находится в классе NP, но обычно подозревают, что он не NP-полный , хотя это не доказано. [6]

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

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

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

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

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

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

Спец. Назначение

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

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

Общее назначение

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

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

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

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

в обозначениях Little- O и L. Некоторыми примерами этих алгоритмов являются метод эллиптических кривых и квадратичное сито . Другим таким алгоритмом является метод отношений групп классов , предложенный Шнорром [11] , Зейсеном [12] и Ленстрой [13] , который они доказали, только предполагая недоказанную обобщенную гипотезу Римана (GRH) .

Строгое время работы

Ленстра и Померанс [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. Путем расчета соответствующей факторизации Δ и взятия НОД эта неоднозначная форма обеспечивает полную факторизацию простых чисел. из н . Этот алгоритм состоит из следующих основных шагов:

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

  1. Пусть ∆ — отрицательное целое число с ∆ = − dn , где d — множитель, а ∆ — отрицательный дискриминант некоторой квадратичной формы.
  2. Возьмем t первых простых чисел p 1 = 2, p 2 = 3, p 3 = 5, ..., p t для некоторого t ∈ N .
  3. Пусть f q — случайная простая форма группы G ∆ такая, что (Δ/д) = 1 .
  4. Найдите порождающий набор X группы G Δ .
  5. Соберите последовательность отношений между множеством X и { f q  : q ∈ P Δ } , удовлетворяющую:
  6. Постройте неоднозначную форму ( a , b , c ) , которая является элементом f ∈ G Δ порядка деления 2, чтобы получить взаимно простую факторизацию наибольшего нечетного делителя Δ , в которой Δ = −4 ac или Δ = a ( a − 4 в ) или Δ знак равно ( б - 2 а )( б + 2 а ) .
  7. Если неоднозначная форма обеспечивает факторизацию n, остановитесь, в противном случае найдите другую неоднозначную форму, пока не будет найдена факторизация n . Чтобы предотвратить возникновение бесполезных неоднозначных форм, создайте 2-силовскую группу Sll 2 (Δ) группы G (Δ) .

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

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

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

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

Примечания

  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 г.
  3. ^ Кляйнджунг; и другие. (18 февраля 2010 г.). «Факторизация 768-битного модуля RSA» (PDF) . Международная ассоциация криптологических исследований . Проверено 9 августа 2010 г. {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
  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. ^ Гольдрайх, Одед ; Вигдерсон, Ави (2008), «IV.20 Вычислительная сложность», Гауэрс, Тимоти ; Барроу-Грин, июнь ; Лидер, Имре (ред.), The Princeton Companion to Mathematics , Принстон, Нью-Джерси: Princeton University Press, стр. 575–604, ISBN 978-0-691-11880-2, МР  2467561. См., в частности, стр. 583.
  7. ^ Бюлер, JP; Ленстра, Х.В. младший; Померанс, Карл (1993). «Факторизация целых чисел с помощью сита числового поля». Разработка решета числового поля. Конспект лекций по математике. Том. 1554. Спрингер. стр. 50–94. дои : 10.1007/BFb0091539. hdl : 1887/2149. ISBN 978-3-540-57013-4. Проверено 12 марта 2021 г.
  8. ^ Вандерсипен, Ливен МК; и другие. (2001). «Экспериментальная реализация алгоритма квантового факторинга Шора с использованием ядерного магнитного резонанса». Природа . 414 (6866): 883–887. arXiv : Quant-ph/0112176 . Бибкод : 2001Natur.414..883V. дои : 10.1038/414883a. PMID  11780055. S2CID  4400832.
  9. ^ Лэнс Фортноу (13 сентября 2002 г.). «Блог о сложности вычислений: Класс сложности недели: факторинг».
  10. ^ AB Дэвид Брессуд и Стэн Вагон (2000). Курс вычислительной теории чисел . Издательство Ключевого колледжа / Springer. стр. 168–69. ISBN 978-1-930190-10-8.
  11. ^ Шнорр, Клаус П. (1982). «Усовершенствованный анализ и улучшения некоторых алгоритмов факторинга». Журнал алгоритмов . 3 (2): 101–127. дои : 10.1016/0196-6774(82)90012-8. MR  0657269. Архивировано из оригинала 24 сентября 2017 года.
  12. ^ Сейсен, Мартин (1987). «Алгоритм вероятностной факторизации с квадратичными формами отрицательного дискриминанта». Математика вычислений . 48 (178): 757–780. doi : 10.1090/S0025-5718-1987-0878705-X . МР  0878705.
  13. ^ Ленстра, Арьен К. (1988). «Быстрая и строгая факторизация в соответствии с обобщенной гипотезой Римана» (PDF) . Indagationes Mathematicae . 50 (4): 443–454. дои : 10.1016/S1385-7258(88)80022-2.
  14. ^ аб Ленстра, HW; Померанс, Карл (июль 1992 г.). «Жесткие сроки факторизации целых чисел» (PDF) . Журнал Американского математического общества . 5 (3): 483–516. дои : 10.1090/S0894-0347-1992-1137100-0 . МР  1137100.

Рекомендации

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