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

Матеріал з Вікіпедії — вільної енциклопедії.

Факториза́ція — розклад заданого числа на прості множники, розклад оператора на добуток декількох операторів нижчого порядку.^[1]

На відміну від задачі розпізнавання простоти числа, факторизація імовірно є складною задачею.

[ред.] Алгоритми факторизації

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

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

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

[ред.] Застосування в криптографії

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

[ред.] Реалізація

[ред.] Функції на мові Haskell

Нижче наведено приклад реалізації алгоритму факторизації на мові програмування 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]

[ред.] Дивіться також

• Факторіал

[ред.] Джерела

[ред.] Ресурси інтернет

• Стаття про алгоритми розкладу на множники(укр.)