Wikia

Математика

Факторизация

Обсуждение0
1413статей на этой вики

Факториза́ция — разложение данного числа на простые множители.

В отличие от задачи распознавания простоты числа, факторизация предположительно является сложной задачей.

Алгоритмы факторизации Править

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

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

Решение задачи факторизации с полиномиальной сложностью возможно на квантовом компьютере с помощью алгоритма Шора.

Применение в криптографии Править

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

Реализация Править

Функции на языке 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]uk:Факторизація

Викия-сеть

Случайная вики