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

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

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

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

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

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

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

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

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

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

  1. Факторизація цілих чисел // Великий тлумачний словник сучасної української мови (з дод. і допов.) / уклад. і гол. ред. В. Т. Бусел. — 5-те вид. — К. ; Ірпінь : Перун, 2005. — ISBN 966-569-013-2.

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


Сигма Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.