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

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

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

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

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

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

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

Многие криптографические протоколы основаны на сложности разложения больших составных целых чисел на множители или на связанной проблеме, например, на проблеме 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 , метод факторизации Ферма начнется с того, что немедленно дает и, следовательно, множители a - b = 18848997157 и a + b = 18848997161 . Хотя их легко распознать как составные и простые соответственно, метод Ферма потребует гораздо больше времени, чтобы разложить составное число на множители, потому что начальное значение для a далеко от 1372933.

Современное состояние дел

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

Сложность и сложность

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Жесткое время работы

Ленстра и Померанс строго доказали, что вероятностный алгоритм Шнорра – Зейсена – Ленстры имеет ожидаемое время выполнения путем замены допущения GRH использованием множителей. Алгоритм использует группу классов положительных бинарных квадратичных форм с дискриминантом А обозначаемых G А . G Δ - это набор троек целых чисел ( a , b , c ), в котором эти числа являются относительными простыми числами.

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

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

Обозначим через P Δ множество всех простых чисел q с символом Кронекера . Путем построения набора образующих группы G Δ и простых форм f q группы G Δ с q в P Δ получается последовательность отношений между набором образующих и f q . Размер q может быть ограничен для некоторой константы .

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

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

  1. Пусть Δ - отрицательное целое число с Δ = - dn , где d - множитель, а Δ - отрицательный дискриминант некоторой квадратичной формы.
  2. Возьмем т первых простых чисел , для некоторых .
  3. Пусть - случайная простая форма группы G Δ с .
  4. Найдите порождающий X группы G Δ
  5. Соберите последовательность отношений между множеством X и { f q  : qP Δ }, удовлетворяющую:
  6. Построим неоднозначную форму, которая является элементом fG Δ порядка деления 2, чтобы получить взаимно простую факторизацию наибольшего нечетного делителя Δ, в которой
  7. Если неоднозначная форма обеспечивает факторизацию n, тогда остановитесь, в противном случае найдите другую неоднозначную форму, пока не будет найдено факторизация n . Чтобы предотвратить появление бесполезных неоднозначных форм, создайте 2-силовскую группу Sll 2 (Δ) группы G (Δ).

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

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

Алгоритм, как указано, является вероятностным алгоритмом, поскольку он делает случайный выбор. Ожидаемое время работы - самое большее .

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

Примечания

использованная литература

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