Перегляд вихідного коду сторінки Факторизація цілих чисел

'''Факториза́ція цілого числа'''&nbsp;— [[Факторизація|розкладання]] заданого [[цілі числа|цілого числа]] на [[Простий множник|прості множники]].

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

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

[[Метод факторизації Ферма|Метод Ферма]] у загальному випадку теж має складність <math>O(\sqrt n)</math> операцій, але є досить ефективним, коли два множники близькі один до одного (приблизно рівні між собою).

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

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

Для дуже великих чисел час виконання операцій над ними пропорційний їх довжині. З урахуванням цього фактору всі перелічені вище методи (із <u>поліноміальною оцінкою ''кількості операцій''</u>) мають ''<u>експоненційну'' [[Часова складність|часову складність]]</u> і для факторизації великих чисел практично непридатні{{sfn|Василенко|2003|с=57}}.

Субекспоненційну оцінку [[Обчислювальна складність|обчислювальної складності]] мають методи [[Метод факторизації Діксона|Діксона]], [[метод ланцюгових дробів|ланцюгових дробів]], [[Квадратичне решето|квадратичного решета]] й {{нп|факторизація на основі еліптичних кривих|еліптичних кривих||Lenstra elliptic-curve factorization}}  <math>O(\exp[c(\ln(N)\ln(\ln(N)))^{1/2}]</math>. 

Для факторизації чисел понад 10<sup>100</sup> найефективнішим алгоритмом факторизації є [[метод решета числового поля]] з обчислювальною складністю <math>O(\exp[c\ln(N)^{1/3}\ln(\ln(N))^{2/3}])</math>{{sfn|Василенко|2003|с=106}}.

== Теоретичні проблеми ==
Питання про [[існування]] алгоритму факторизації з [[клас P|поліноміальною складністю]] на класичному комп'ютері є однією з важливих відкритих проблем сучасної [[теорія чисел|теорії чисел]]. У той же час, для спорідненої задачі про розпізнавання простоти числа існує поліноміальне рішення&nbsp;— [[AKS тест простоти]].

Розв'язок задачі факторизації з поліноміальною складністю можливий на [[Квантовий комп'ютер|квантовому комп'ютері]] за допомогою [[Алгоритм Шора|алгоритму Шора]].

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

== Реалізація ==
=== Функції на мові Haskell ===
Нижче наведено реалізацію тривіального алгоритму (перебором простих дільників) на [[мова програмування|мові програмування]] [[Haskell]].
<syntaxhighlight lang="text">
 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]
</syntaxhighlight>

== Див. також ==
* [[Факторіал]]
* [[Алгоритм Поліґа — Геллмана]]
* [[Рівень криптостійкості]]

== Джерела ==
{{reflist}}

== Посилання ==
* {{cite article|author= Carl Pomerance |title= Analysis and Comparison of Some Integer Factoring Algorithms |work= Computational Methods in Number Theory, Part I |editor=H.W. Lenstra, Jr. and R. Tijdeman, eds. |publisher=Math. Centre Tract 154 |place=Amsterdam |year= 1982 |pages= 89-139}}
* {{книга
 |автор         = Василенко О. Н.
 |назва         = Теоретико-числовые алгоритмы в криптографии
 |посилання     = http://www.ict.edu.ru/ft/002416/book.pdf
 |місто         = Москва
 |видавництво   = [[Московський центр неперервної математичної освіти|МЦНМО]]
 |рік           = 2003
 |сторінок      = 326
 |сторінки      = 57—77
 |наклад        = 1000
 |ref           = Василенко
 |isbn          = 5-94057-103-4
}}{{ref-ru}}
{{Числа за подільністю}}
{{math-stub}}

[[Категорія:Теорія чисел]]
[[Категорія:Алгоритми факторизації]]
[[Категорія:Нерозв'язані проблеми інформатики]]
[[Категорія:Статті з прикладами коду]]