Перейти до вмісту

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

Матеріал з Вікіпедії — вільної енциклопедії.

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

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

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

[ред. | ред. код]

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

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

Метод Лемана комбінує тривіальний алгоритм для пошуку малих дільників (до ) та ідеї, що закладені в методі Ферма. Цей алгоритм став першим, складність якого ( арифметичних операцій) була меншою, ніж . Нині він становить суто історичний інтерес.
Метод квадратичних форм Шенкса, який оперує числами, що не перевищують , має оцінку складності . На 32-бітних процесорах він є найшвидшим для чисел у діапазоні від 1010 до 1018 (тобто, довжиною від 33 до 60 біт). Його застосовують як допоміжний у багатьох реалізаціях потужніших методів — для факторизації проміжних чисел, які не мають малих дільників.

Імовірнісний ρ-алгоритм Полларда порівняно швидко знаходить невеликі дільники (якщо такі є) і теж має складність операцій.

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

Субекспоненційну оцінку обчислювальної складності мають методи Діксона, ланцюгових дробів, квадратичного решета й еліптичних кривих[en] .

Для факторизації чисел понад 10100 найефективнішим алгоритмом факторизації є метод решета числового поля з обчислювальною складністю [2].

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

[ред. | ред. код]

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

Див. також

[ред. | ред. код]

Джерела

[ред. | ред. код]

Посилання

[ред. | ред. код]