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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

Найбільш тривіальним алгоритмом факторизації чисел є повний перебір можливих дільників. Складність цього алгоритму дорівнює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[ред.ред. код]

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

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

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

Посилання[ред.ред. код]