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

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

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

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

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

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

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

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

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

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

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

Див. також

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

Джерела

1. Василенко, 2003, с. 57.
2. Василенко, 2003, с. 106.

Посилання

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