Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

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

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

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

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

Наиболее тривиальным алгоритмом факторизации чисел является полный перебор возможных делителей. Сложность этого алгоритма равна 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:Факторизація

Викия-сеть

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