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

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

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

Алгоритми факторизації

Тривіальним алгоритмом факторизації чисел є повний перебір можливих дільників (до ${\sqrt {n}}$). Складність цього алгоритму дорівнює $O(N^{1/2})$ операцій. Однак, він швидко знаходить невеликі дільники й застосовується для їх пошуку (зокрема, як початковий крок у деяких інших алгоритмах).

Метод Ферма у загальному випадку теж має складність $O({\sqrt {n}})$ операцій, але є досить ефективним, коли два множники близькі один до одного (приблизно рівні між собою).

Метод Лемана комбінує тривіальний алгоритм для пошуку малих дільників (до $n^{1/3}$) та ідеї, що закладені в методі Ферма. Цей алгоритм став першим, складність якого ($O(n^{1/3})$ арифметичних операцій) була меншою, ніж $O({\sqrt {n}})$. Нині він становить суто історичний інтерес.
Метод квадратичних форм Шенкса, який оперує числами, що не перевищують $2{\sqrt {n}}$, має оцінку складності $O(n^{1/4})$. На 32-бітних процесорах він є найшвидшим для чисел у діапазоні від 10¹⁰ до 10¹⁸ (тобто, довжиною від 33 до 60 біт). Його застосовують як допоміжний у багатьох реалізаціях потужніших методів — для факторизації проміжних чисел, які не мають малих дільників.

Імовірнісний ρ-алгоритм Полларда порівняно швидко знаходить невеликі дільники (якщо такі є) і теж має складність $O(n^{1/4})$ операцій.

Для дуже великих чисел час виконання операцій над ними пропорційний їх довжині. З урахуванням цього фактору всі перелічені вище методи (із поліноміальною оцінкою кількості операцій) мають експоненційну часову складність і для факторизації великих чисел практично непридатні.

Субекспоненційну оцінку обчислювальної складності мають методи Діксона, ланцюгових дробів, квадратичного решета й еліптичних кривих $O(\exp[c(\ln(N)\ln(\ln(N)))^{1/2}]$.

Для факторизації чисел понад 10¹⁰⁰ найефективнішим алгоритмом факторизації є метод решета числового поля з обчислювальною складністю $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]

Див. також

• Факторіал
• Алгоритм Поліґа — Геллмана
• Рівень криптостійкості

Посилання

• Carl Pomerance. Analysis and Comparison of Some Integer Factoring Algorithms. — Amsterdam : Math. Centre Tract 154, 1982. — С. 89-139.
• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — Москва : МЦНМО, 2003. — С. 57—77. — 1000 прим. — ISBN 5-94057-103-4.(рос.)