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

Найбільш тривіальним алгоритмом факторизації чисел є повний перебір можливих дільників. Складність цього алгоритму дорівнює ${\displaystyle O(N^{1/2})}$. ρ-алгоритм Поларда має складність ${\displaystyle O(N^{1/4})}$. Метод факторизації Діксона, метод неперервних дробів, метод квадратичного решета і метод на основі еліптичних кривих мають складність${\displaystyle O(\exp[c(\ln(N)\ln(\ln(N)))^{1/2}]}$. В наш час найефективнішим алгоритмом факторизації є метод решета числового поля зі складністю ${\displaystyle O(\exp[c\ln(N)^{1/3}\ln(\ln(N))^{2/3}])}$.

Алгоритм Поліґа-Геллмана має складність ${\displaystyle O({\sqrt {n}})}$, але може бути ефективнішим для чисел спеціального виду.

Питання про існування алгоритму факторизації з поліноміальною складністю на класичному комп'ютері є однією з важливих відкритих проблем сучасної теорії чисел. У той же час, для спорідненої задачі про розпізнавання простоти числа існує поліноміальне рішення — AKS тест простоти.

Рішення задачі факторизації з поліноміальною складністю можливо на квантовому комп'ютері за допомогою алгоритму Шора.

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

• Факторіал

• Алгоритми розкладу на множники (факторизація). ІТ Блог. 24 вересня 2007. Процитовано 13 грудня 2021.(укр.)^{[неавторитетне джерело]}