Факторизация
Материал из Википедии — свободной энциклопедии
Факториза́ция — разложение числа на множители.
В криптографии факторизацией называют разложение числа на простые множители. На предположении о сложности данного процесса основывается криптостойкость некоторых алгоритмов шифрования с открытым ключом, таких, как RSA.
Наиболее тривиальным алгоритмом факторизации чисел является полный перебор возможных делителей. Сложность этого алгоритма равна O(N1 / 2). ρ-алгоритм Полларда имеет сложность O(N1 / 4). Метод непрерывных дробей, метод квадратичного решета и метод на основе эллиптических кривых имеют сложность O(exp[c(ln(N)ln(ln(N)))1 / 2].В настоящее время самым эффективным алгоритмом факторизации является метод решета числового поля со сложностью O(exp[cln(N)1 / 3ln(ln(N))2 / 3]).
Вопрос о существовании алгоритма факторизации с полиномиальной сложностью на классическом компьютере является одной из важных открытых проблем современной теории чисел. В то же время доказано, что родственная задача о распознавании простоты числа является полиномиально разрешимой и для неё существует много эффективных тестов простоты.
Решение задачи факторизации с полиномиальной сложностью возможно на квантовом компьютере с помощью алгоритма Шора.
[править] Реализация
[править] Функции на языке Haskell
primes :: [Integer]
primes = eratosthenes [2..]
where
eratosthenes (x:xs) = x:eratosthenes (filter ((/= 0).(`mod` x)) xs)
factorization :: Integer -> [Integer]
factorization 1 = []
factorization n = x:factorization (n `div` x)
where
x = head [y | y <- (takeWhile (<= n) primes), n `mod` y == 0]
