Разложение числа на множители

Введение

Разложение числа на произведение

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

In number theory, integer factorization is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors, in which case it is called a composite number, or it is not, in which case it is called a prime number. For example, 15 is a composite number because 1=15 = 3 · 5, but 7 is a prime number because it cannot be decomposed in this way. If one of the factors is composite, it can in turn be written as a product of smaller factors, for example 1=60 = 3 · 20 = 3 · (5 · 4). Continuing this process until every factor is prime is called prime factorization; the result is always unique up to the order of the factors by the prime factorization theorem. To factorize a small integer n using mental or pen and paper arithmetic, the simplest method is trial division: checking if the number is divisible by prime numbers 2, 3, 5, and so on, up to the square root of n. For larger numbers, especially when using a computer, various more sophisticated factorization algorithms are more efficient. A prime factorization algorithm typically involves testing whether each factor is prime each time a factor is found. When the numbers are sufficiently large, no efficient non quantum integer factorization algorithm is known. However, it has not been proven that such an algorithm does not exist. The presumed difficulty of this problem is important for the algorithms used in cryptography such as RSA public key encryption and the RSA digital signature. Many areas of mathematics and computer science have been brought to bear on the problem, including elliptic curves, algebraic number theory, and quantum computing. Not all numbers of a given length are equally hard to factor. The hardest instances of these problems (for currently known techniques) are semiprimes, the product of two prime numbers. When they are both large, for instance more than two thousand bits long, randomly chosen, and about the same size (but not too close, for example, to avoid efficient factorization by Fermat's factorization method), even the fastest prime factorization algorithms on the fastest computers can take enough time to make the search impractical; that is, as the number of digits of the integer being factored increases, the number of operations required to perform the factorization on any computer increases drastically. Many cryptographic protocols are based on the difficulty of factoring large composite integers or a related problem—for example, the RSA problem. An algorithm that efficiently factors an arbitrary integer would render RSA based public key cryptography insecure.

Первичное разложение

Согласно основной теореме арифметики, каждое положительное целое число имеет единственное в своем роде простое разложение на множители. (По соглашению, 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 является делителем 10 от 1372933.

Современное состояние техники

Среди b-битных чисел, наиболее сложными для факторизации на практике с использованием существующих алгоритмов являются полупростые числа, чьи множители имеют близкий размер. По этой причине именно эти числа используются в криптографических приложениях. В 2019 году Фабрис Будот, Пьеррик Годри, Аврора Гильевич, Надя Хеннигер, Эммануэль Томе и Поль Циммерманн разложили на множители 240-значное (795-битное) число (RSA 240), используя приблизительно 900 ядерных лет вычислительной мощности. Исследователи оценили, что факторизация 1024-битного модуля RSA потребует примерно в 500 раз больше времени. Самым большим полупростым числом, которое было разложено на множители на сегодняшний день, является RSA 250 – 829-битное число с 250 десятичными цифрами, что было сделано в феврале 2020 года. Общее время вычислений составило около 2700 ядерных лет на процессорах Intel Xeon Gold 6130 с частотой 2,1 ГГц. Как и все последние рекорды факторизации, это разложение было выполнено с использованием высокооптимизированной реализации общего решета числового поля, работающего на сотнях машин.

Временная сложность

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

Для современных компьютеров GNFS является лучшим опубликованным алгоритмом для больших n (более чем около 400 бит). Однако для квантового компьютера Питер Шор в 1994 году открыл алгоритм, решающий эту задачу за полиномиальное время. Алгоритм Шора требует времени O(b^3) и пространства O(b) для b-битных входных данных. В 2001 году алгоритм Шора был впервые реализован с использованием методов ЯМР на молекулах, предоставляющих семь кубитов. Чтобы говорить о классах сложности, таких как P, NP и co NP, задача должна быть сформулирована как задача принятия решения. Известно, что она принадлежит как NP, так и co NP, что означает, что ответы "да" и "нет" могут быть проверены за полиномиальное время. Ответ "да" может быть подтвержден представлением разложения на множители с d ≤ k. Ответ "нет" может быть подтвержден представлением разложения n на различные простые числа, все большие, чем k; их простоту можно проверить с помощью теста простоты AKS, а затем перемножить их, чтобы получить n. Основная теорема арифметики гарантирует, что существует только одна возможная последовательность возрастающих простых чисел, которая будет принята, что показывает, что задача принадлежит как UP, так и co UP. Известно, что она принадлежит BQP благодаря алгоритму Шора. Предполагается, что задача не принадлежит ни одному из трех классов сложности P, NP-полная и co NP-полная. Следовательно, она является кандидатом в класс NP промежуточной сложности. В отличие от этого, задача принятия решения "Является ли n составным числом?" (или, эквивалентно: "Является ли n простым числом?") представляется гораздо более простой, чем задача определения множителей n. Задачу о составности/простоте можно решить за полиномиальное время (относительно числа b цифр n) с помощью теста простоты AKS. Кроме того, существует несколько вероятностных алгоритмов, которые могут очень быстро проверить простоту на практике, если кто-то готов принять пренебрежимо малую вероятность ошибки. Простота проверки простоты является важной частью алгоритма RSA, поскольку для начала необходимо найти большие простые числа.

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

Универсальный алгоритм факторизации, также известный как алгоритм категории 2, второго типа или семейства Крайтчика, Сейзена и Ленстры, который они доказали, лишь предполагая непроверенную обобщённую гипотезу Римана.