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

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

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

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

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

Для факторизації чисел понад 10¹⁰⁰ найефективнішим алгоритмом факторизації є метод решета числового поля з обчислювальною складністю $O(\exp [c\ln (N{)}^{1/3}\ln (\ln (N){)}^{2/3}])$Шаблон:Sfn.

Теоретичні проблеми

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

Див. також

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

Посилання

• Шаблон:Cite article
• Шаблон:КнигаШаблон:Ref-ru