Факторизация целых чисел

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

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

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

Задача поиска эффективных способов разложения целых чисел на множители интересовала математиков с давних времён, особенно специалистов в области теории чисел. Существуют предположения о том, что Ферма был одним из первых, кто предложил метод разложения, заключающийся в том, чтобы представить число в виде разности квадратов $n=x^{2}-y^{2}$ , а затем, вычисляя $\gcd(n,x-y)$ , попытаться найти нетривиальный делитель $n$ . Данный способ позволяет находить два мало различающихся по величине делителя числа быстрее, чем простой перебор делителей^[1].

Далее Лежандр обнаружил, что при таком подходе достаточно получить сравнение $x^{2}\equiv y^{2}\mod n$ , и использовал для этого цепные дроби. Также Эйлером и Гауссом были предложены некоторые способы нахождения чисел, связанных этим сравнением^[1].