www.wikidata.uk-ua.nina.az

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

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

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

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

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

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

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

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

ρ-алгоритм Поларда має складність .

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

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

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

Алгоритм Поліґа-Геллмана має складність , але може бути ефективним для чисел спеціального виду.

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

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

Див. також

Джерела

Посилання

  • . ІТ Блог. 24 вересня 2007. Архів оригіналу за 16 травня 2019. Процитовано 13 грудня 2021. (укр.)[неавторитетне джерело]


Це незавершена стаття з математики.
Ви можете допомогти проєкту, виправивши або дописавши її.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Faktoriza ciya cilogo chisla rozkladannya zadanogo cilogo chisla na prosti mnozhniki Na vidminu vid zadachi rozpiznavannya prostoti chisla faktorizaciya jmovirno ye skladnoyu zadacheyu Peredbachuvana skladnist zadachi faktorizaciyi lezhit v osnovi kriptostijkosti deyakih algoritmiv shifruvannya z vidkritim klyuchem takih yak RSA Zmist 1 Algoritmi faktorizaciyi 2 Teoretichni problemi 3 Realizaciya 3 1 Funkciyi na movi Haskell 4 Div takozh 5 Dzherela 6 PosilannyaAlgoritmi faktorizaciyi RedaguvatiTrivialnim algoritmom faktorizaciyi chisel ye povnij perebir mozhlivih dilnikiv do n displaystyle sqrt n Skladnist cogo algoritmu dorivnyuye O N 1 2 displaystyle O N 1 2 Odnak vin shvidko znahodit neveliki dilniki j zastosovuyetsya dlya yih poshuku zokrema yak pochatkovij krok u deyakih inshih algoritmah Metod Ferma u zagalnomu vipadku tezh maye skladnist O n displaystyle O sqrt n ale ye dosit efektivnim koli dva mnozhniki blizki odin do odnogo priblizno rivni mizh soboyu Metod Lemana kombinuye trivialnij algoritm dlya poshuku malih dilnikiv do n 1 3 displaystyle n 1 3 ta ideyi sho zakladeni v metodi Ferma Cej algoritm stav pershim skladnist yakogo O n 1 3 displaystyle O n 1 3 arifmetichnih operacij bula menshoyu nizh O n displaystyle O sqrt n Nini vin stanovit suto istorichnij interes r algoritm Polarda maye skladnist O N 1 4 displaystyle O N 1 4 Metod faktorizaciyi Diksona metod neperervnih drobiv metod kvadratichnogo resheta i metod na osnovi eliptichnih krivih en mayut obchislyuvalnu skladnistO exp c ln N ln ln N 1 2 displaystyle O exp c ln N ln ln N 1 2 Dlya faktorizaciyi chisel ponad 10100 najefektivnishim algoritmom faktorizaciyi ye metod resheta chislovogo polya z obchislyuvalnoyu skladnistyu O exp c ln N 1 3 ln ln N 2 3 displaystyle O exp c ln N 1 3 ln ln N 2 3 dzherelo Na 32 bitnih procesorah dlya chisel u diapazoni vid 1010 do 1018 tobto dovzhinoyu vid 32 do 60 bit najshvidshim ye metod kvadratichnih form Shenksa Vin zastosovuyetsya yak dopomizhnij u bagatoh realizaciyah potuzhnishih metodiv dlya faktorizaciyi promizhnih chisel yaki ne mayut malih dilnikiv Algoritm Poliga Gellmana maye skladnist O n displaystyle O sqrt n ale mozhe buti efektivnim dlya chisel specialnogo vidu Teoretichni problemi RedaguvatiPitannya pro isnuvannya algoritmu faktorizaciyi z polinomialnoyu skladnistyu na klasichnomu komp yuteri ye odniyeyu z vazhlivih vidkritih problem suchasnoyi teoriyi chisel U toj zhe chas dlya sporidnenoyi zadachi pro rozpiznavannya prostoti chisla isnuye polinomialne rishennya AKS test prostoti Rozv yazok zadachi faktorizaciyi z polinomialnoyu skladnistyu mozhlivij na kvantovomu komp yuteri za dopomogoyu algoritmu Shora Peredbachuvana skladnist zadachi faktorizaciyi lezhit v osnovi kriptostijkosti deyakih algoritmiv shifruvannya z vidkritim klyuchem takih yak RSA Realizaciya RedaguvatiFunkciyi na movi Haskell Redaguvati Nizhche navedeno realizaciyu trivialnogo algoritmu pereborom prostih dilnikiv na movi programuvannya Haskell primes Integer primes eratosthenes 2 where eratosthenes x xs x eratosthenes filter 0 mod x xs factorization Integer gt Integer factorization 1 factorization n x factorization n div x where x head y y lt takeWhile lt n primes n mod y 0 Div takozh RedaguvatiFaktorial Riven kriptostijkostiDzherela RedaguvatiPosilannya RedaguvatiAlgoritmi rozkladu na mnozhniki faktorizaciya IT Blog 24 veresnya 2007 Arhiv originalu za 16 travnya 2019 Procitovano 13 grudnya 2021 ukr neavtoritetne dzherelo Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Otrimano z https uk wikipedia org w index php title Faktorizaciya cilih chisel amp oldid 39704816