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

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

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

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

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

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

Алгоритм Поліґа-Геллмана має складність , але може бути ефективнішим для чисел спеціального виду.

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

Див. також[ред. | ред. код]

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

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