Відкрити головне меню

Факториза́ція цілого числа — розкладання заданого числа на прості множники, розклад оператора на добуток декількох операторів нижчого порядку.[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.

ПосиланняРедагувати