Факториза́ція цілого числа — (розкладання) заданого цілого числа на (прості множники).
На відміну від задачі (розпізнавання простоти) числа, факторизація ймовірно є (складною задачею). Передбачувана складність задачі факторизації лежить в основі криптостійкості деяких алгоритмів шифрування з відкритим ключем, таких як (RSA).
Алгоритми факторизації
Тривіальним алгоритмом факторизації чисел є (повний перебір) можливих дільників (до ). Складність цього алгоритму дорівнює
операцій. Однак, він швидко знаходить невеликі дільники й застосовується для їх пошуку (зокрема, як початковий крок у деяких інших алгоритмах).
(Метод Ферма) у загальному випадку теж має складність операцій, але є досить ефективним, коли два множники близькі один до одного (приблизно рівні між собою).
(Метод Лемана) комбінує тривіальний алгоритм для пошуку малих дільників (до ) та ідеї, що закладені в методі Ферма. Цей алгоритм став першим, складність якого (
арифметичних операцій) була меншою, ніж
. Нині він становить суто історичний інтерес.
(Метод квадратичних форм Шенкса), який оперує числами, що не перевищують , має оцінку складності
. На 32-бітних процесорах він є найшвидшим для чисел у діапазоні від 1010 до 1018 (тобто, довжиною від 33 до 60 біт). Його застосовують як допоміжний у багатьох реалізаціях потужніших методів — для факторизації проміжних чисел, які не мають малих дільників.
Імовірнісний (ρ-алгоритм Полларда) порівняно швидко знаходить невеликі дільники (якщо такі є) і теж має складність операцій.
Для дуже великих чисел час виконання операцій над ними пропорційний їх довжині. З урахуванням цього фактору всі перелічені вище методи (із поліноміальною оцінкою кількості операцій) мають експоненційну (часову складність) і для факторизації великих чисел практично непридатні.
Субекспоненційну оцінку (обчислювальної складності) мають методи (Діксона), , (квадратичного решета) й [en].
Для факторизації чисел понад 10100 найефективнішим алгоритмом факторизації є (метод решета числового поля) з обчислювальною складністю .
Теоретичні проблеми
Питання про (існування) алгоритму факторизації з (поліноміальною складністю) на класичному комп'ютері є однією з важливих відкритих проблем сучасної теорії чисел. У той же час, для спорідненої задачі про розпізнавання простоти числа існує поліноміальне рішення — (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]
Див. також
- (Факторіал)
- (Алгоритм Поліґа — Геллмана)
- (Рівень криптостійкості)
Джерела
- Василенко, 2003, с. 57.
- Василенко, 2003, с. 106.
Посилання
- Carl Pomerance. Analysis and Comparison of Some Integer Factoring Algorithms. — Amsterdam : Math. Centre Tract 154, 1982. — С. 89-139.
- Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — Москва : (МЦНМО), 2003. — С. 57—77. — 1000 прим. — .(рос.)
![]() | Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет