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