Kvadratichne resheto angl quadratic sieve QS algoritm faktorizaciyi cilih chisel na praktici najshvidshij dlya chisel do 10100 Asipmtotichno ye drugim za shvidkistyu pislya zagalnogo resheta cifrovogo polya i znachno prostishij za nogo Ce metod faktorizaciyi zagalnogo priznachennya tobto chas jogo vikonannya zalezhit lishe vid rozmiru cilogo chisla na vhodi i ne zalezhit vid jogo viglyadu na vidminu vid specialnogo resheta chislovogo polya en Metod vinajshov matematik Karl Pomeranc en 1981 roku yak polipshennya linijnogo resheta Shroppelya 1 Zmist 1 Vstup 2 Ideya 3 Algoritm 4 Priklad roboti 5 Perevirka gladkosti prosiyuvannyam 6 PrimitkiVstupred Vizmemo napriklad chislo 2419 displaystyle 2419 nbsp Ce chislo skladene i ne dilitsya na zhodne z malih prostih chisel Ale mozhna pobachiti sho ce 2500 81 displaystyle 2500 81 nbsp tobto 2419 50 2 9 2 displaystyle 2419 50 2 9 2 nbsp Otzhe mi mozhemo rozklasti 2419 displaystyle 2419 nbsp yak riznicyu kvadrativ Ce ye 50 9 50 9 displaystyle 50 9 50 9 nbsp abo 41 59 displaystyle 41 times 59 nbsp Kozhne neparne skladene chislo mozhna rozklasti yak riznicyu kvadrativ n p q p q 2 2 p q 2 2 displaystyle n pq left frac p q 2 right 2 left frac p q 2 right 2 nbsp Sprobujmo znov z chislom 1649 Vono takozh skladene i ne maye malih prostih dilnikiv menshih nizh jogo logarifm Z 2419 mi vzyali pershij kvadrat bilshij vid nogo a same 50 2 displaystyle 50 2 nbsp i todi zauvazhili sho 50 2 2419 81 displaystyle 50 2 2419 81 nbsp sho ye kvadratom Mozhna podumati sho v poshuci kvadrativ mozhna projti poslidovnist x 2 n displaystyle x 2 n nbsp z x n 1 2 n 1 2 1 displaystyle x lceil n 1 2 rceil lceil n 1 2 rceil 1 dots nbsp Dlya n 1649 displaystyle n 1649 nbsp mayemo 41 2 n 32 displaystyle 41 2 n 32 nbsp 42 2 n 115 displaystyle 42 2 n 115 nbsp 43 2 n 200 displaystyle 43 2 n 200 nbsp 1 displaystyle vdots nbsp i ne bachimo kvadrativ pomizh pershih rezultativ Popri cyu nevdachu poperedni tri rivnyannya vzhe mozhna vikoristati dlya rozkladennya n displaystyle n nbsp Hocha ani 32 ani 200 ne ye kvadratami odnak yihnij dobutok kvadrat a same 80 2 displaystyle 80 2 nbsp otzhe z togo sho 41 2 32 mod n displaystyle 41 2 equiv 32 pmod n nbsp 43 2 200 mod n displaystyle 43 2 equiv 200 pmod n nbsp mayemo 41 2 43 2 80 2 mod n displaystyle 41 2 times 43 2 equiv 80 2 pmod n nbsp sho rivnoznachno 41 43 2 80 2 mod n displaystyle 41 times 43 2 equiv 80 2 pmod n nbsp 2 Mi znajshli rozv yazok dlya a 2 b 2 mod n displaystyle a 2 equiv b 2 pmod n nbsp Naskilki ce cikavo Zvisno isnuye bagato necikavih par a 2 b 2 mod n displaystyle a 2 equiv b 2 pmod n nbsp A same yaksho vzyati bud yake znachennya a displaystyle a nbsp i poklasti b a displaystyle b pm a nbsp Ale cej perelik ne vicherpuye vsi rozv yazki dlya cogo rivnyannya bo rozkladennya n displaystyle n nbsp yak riznicyu kvadrativ dalo b paru a b displaystyle a b nbsp z b a displaystyle b not pm a nbsp Dali bud yaka para a b displaystyle a b nbsp z a 2 b 2 mod n b a mod n displaystyle a 2 equiv b 2 pmod n b not equiv pm a pmod n nbsp 3 maye vesti do netrivialnogo rozkladu n displaystyle n nbsp cherez gcd a b n displaystyle gcd a b n nbsp Spravdi z 3 viplivaye sho n displaystyle n nbsp dilit a b a b displaystyle a b a b nbsp ale ne dilit zhoden z mnozhnikiv otzhe gcd a b n gcd a b n displaystyle gcd a b n gcd a b n nbsp mayut buti netrivialnimi dilnikami n displaystyle n nbsp NSD mozhna znajti cherez algoritm Evklida Zreshtoyu yaksho n displaystyle n nbsp maye shonajmenshe dva prostih mnozhniki todi ne menshe polovini rozv yazkiv a 2 b 2 mod n displaystyle a 2 equiv b 2 pmod n nbsp z a b displaystyle ab nbsp vzayemno prostim z n displaystyle n nbsp takozh zadovolnyayut b a mod n displaystyle b not equiv pm a pmod n nbsp sho i ye 3 Dovedennya Dlya stepeni neparnogo prostogo p u displaystyle p u nbsp kongruentnist y 2 1 mod p u displaystyle y 2 equiv 1 pmod p u nbsp maye rivno 2 rozv yazki otzhe z togo sho n displaystyle n nbsp dilimo ne mensh yak dvoma riznimi neparnimi prostimi kongruenciya y 2 1 mod n displaystyle y 2 equiv 1 pmod n nbsp maye shonajmenshe 4 rozv yazki Poznachimo ci znachennya yak y 1 y 2 y 3 y s displaystyle y 1 y 2 y 3 dots y s nbsp de y 1 1 displaystyle y 1 1 nbsp y 2 1 displaystyle y 2 1 nbsp Todi povnij perelik par kvadratichnih zalishkiv a b displaystyle a b nbsp za modulem n displaystyle n nbsp vzayemno prostih z n displaystyle n nbsp i z a 2 b 2 mod n displaystyle a 2 equiv b 2 pmod n nbsp zbigayetsya z usima parami a y i a displaystyle a y i a nbsp de a displaystyle a nbsp probigaye vsi zalishki vzayemno prosti z n displaystyle n nbsp a i 1 s displaystyle i 1 dots s nbsp Pari z i 1 2 displaystyle i 1 2 nbsp ne zadovolnyayut 3 todi yak inshi tak Z togo sho s 4 displaystyle s geq 4 nbsp dovedennya zavershene Ideyared V osnovi metodu lezhit taka ideya Pripustimo x displaystyle x nbsp i y displaystyle y nbsp ye cilimi takimi sho x 2 y 2 mod n displaystyle x 2 equiv y 2 pmod n nbsp ale x y mod n displaystyle x not equiv pm y pmod n nbsp Todi n displaystyle n nbsp dilit x 2 y 2 x y x y displaystyle x 2 y 2 x y x y nbsp ale ne dilit ani x y displaystyle x y nbsp ani x y displaystyle x y nbsp Zvidsi gcd x y n displaystyle gcd x y n nbsp maye buti netrivialnim dilnikom n displaystyle n nbsp Pripustimo sho mayemo rozklasti cile n displaystyle n nbsp Nehaj m n displaystyle m sqrt n nbsp rozglyanemo mnogochlen q x x m 2 n displaystyle q x x m 2 n nbsp Zauvazhimo sho q x x 2 2 m x m 2 n x 2 2 m x displaystyle q x x 2 2mx m 2 n approx x 2 2mx nbsp ye malim porivnyano z n displaystyle n nbsp yaksho absolyutne znachennya x displaystyle x nbsp male Algoritm kvadratichnogo resheta obiraye a i x m displaystyle a i x m nbsp i pereviryaye chi ye b i x m 2 p t displaystyle b i x m 2 p t nbsp gladkim Zauvazhimo sho a i x m 2 b i mod n displaystyle a i x m 2 equiv b i pmod n nbsp zvidsi n displaystyle n nbsp ye kvadratichnim zalishkom za modulem p displaystyle p nbsp Otzhe faktor baza povinna skladatis z prostih chisel p displaystyle p nbsp dlya yakih simvol Lezhandra n p 1 displaystyle left frac n p right 1 nbsp Okrim cogo tomu sho b i displaystyle b i nbsp mozhe buti vid yemnim 1 displaystyle 1 nbsp takozh vklyuchayemo do faktor bazi Algoritmred Vhid cile skladene chislo n displaystyle n nbsp yake ne ye stepenem prostogo Vihid netrivialnij dilnik d displaystyle d nbsp dlya n displaystyle n nbsp Obirayemo bazu dilnikiv S p 1 p 2 p t displaystyle S p 1 p 2 p t nbsp de p 1 1 displaystyle p 1 1 nbsp i p j j 2 displaystyle p j j geq 2 nbsp ye j 1 displaystyle j 1 nbsp e proste p displaystyle p nbsp dlya yakogo n displaystyle n nbsp ye kvadratichnim zalishkom za modulem p displaystyle p nbsp Obchisliti m n displaystyle m lfloor sqrt n rfloor nbsp Zibrati t 1 displaystyle t 1 nbsp dvijok a i b i displaystyle a i b i nbsp Znachennya x displaystyle x nbsp obirayemo v poryadku 0 1 2 displaystyle 0 pm 1 pm 2 dots nbsp Vstanoviti i 1 displaystyle i gets 1 nbsp Poki i t 1 displaystyle i leq t 1 nbsp robiti nastupne Obchisliti b q x x m 2 n displaystyle b q x x m 2 n nbsp i pereviriti poslidovnim dilennyam na elementi z S displaystyle S nbsp chi ye b p t displaystyle b p t nbsp gladkim Yaksho ni obirayemo novij x displaystyle x nbsp i povtoryuyemo Yaksho b displaystyle b nbsp ye p t displaystyle p t nbsp gladkim skazhimo b j 1 t p i e i j displaystyle b prod j 1 t p i e ij nbsp todi poklasti a i x m b i b v i v i 1 v i 2 v i t displaystyle a i gets x m b i gets b v i v i1 v i2 dots v it nbsp de v i j e i j mod 2 displaystyle v ij e ij mod 2 nbsp dlya 1 j t displaystyle 1 leq j leq t nbsp i i 1 displaystyle i gets i 1 nbsp Vikoristati linijnu algebru nad Z 2 displaystyle mathrm Z 2 nbsp dlya znahodzhennya nepustoyi pidmnozhini T 1 2 t 1 displaystyle T subseteq 1 2 dots t 1 nbsp takoyi sho i T v i 0 displaystyle sum i in T v i 0 nbsp Obchisliti x i T a i mod n displaystyle x prod i in T a i mod n nbsp Dlya kozhnogo j 1 j t displaystyle j 1 leq j leq t nbsp obchisliti l j i T e i j 2 displaystyle l j sum i in T e ij 2 nbsp Obchisliti y j 1 t p j l j mod n displaystyle y prod j 1 t p j l j mod n nbsp Yaksho x y mod n displaystyle x equiv pm y pmod n nbsp todi znajti inshu neporozhnyu pidmnozhinu T 1 2 t 1 displaystyle T subseteq 1 2 dots t 1 nbsp takih sho i T v i 0 displaystyle sum i in T v i 0 nbsp i perejti do etapu 5 U malojmovirnomu vipadku yaksho pidmnozhina T displaystyle T nbsp ne isnuye zaminiti dekilka z dvijok a i b i displaystyle a i b i nbsp novimi parami etap 3 i perejti na etap 4 Obchisliti d gcd x y n displaystyle d gcd x y n nbsp i povernuti d displaystyle d nbsp Priklad robotired Algoritm kvadratichnogo resheta dlya nahodzhennya netrivialnogo dilnika dlya n 24961 displaystyle n 24961 nbsp Obirayemo faktor bazu S 1 2 3 5 13 23 displaystyle S 1 2 3 5 13 23 nbsp rozmiru t 6 displaystyle t 6 nbsp 7 11 17 displaystyle 7 11 17 nbsp i 19 displaystyle 19 nbsp opusheni z S displaystyle S nbsp bo dlya cih prostih n p 1 displaystyle frac n p 1 nbsp Obchisliti m 2 4961 157 displaystyle m lfloor sqrt 2 4961 rfloor 157 nbsp Dali jdut dani zibrani dlya pershih t 1 displaystyle t 1 nbsp znachen x displaystyle x nbsp dlya yakih q x displaystyle q x nbsp ye 23 gladkih i displaystyle i nbsp x displaystyle x nbsp q x displaystyle q x nbsp faktorizaciya q x displaystyle q x nbsp a i displaystyle a i nbsp b i displaystyle b i nbsp 1 0 312 2 3 3 13 displaystyle 2 3 times 3 times 13 nbsp 157 1 1 1 0 1 0 2 1 3 3 displaystyle 3 nbsp 158 0 0 1 0 0 0 3 1 625 5 4 displaystyle 5 4 nbsp 156 1 0 0 0 0 0 4 2 320 2 6 5 displaystyle 2 6 times 5 nbsp 159 0 0 0 1 0 0 5 2 936 2 3 3 2 13 displaystyle 2 3 times 3 2 times 13 nbsp 155 1 1 0 0 1 0 6 4 960 2 6 3 5 displaystyle 2 6 times 3 times 5 nbsp 161 0 0 1 1 0 0 7 6 2160 2 4 3 3 5 displaystyle 2 4 times 3 3 times 5 nbsp 151 1 0 1 1 0 0 Vizmemo T 1 2 5 displaystyle T 1 2 5 nbsp 2 Mayemo v 1 v 2 v 5 0 displaystyle v 1 v 2 v 5 0 nbsp Obchislimo x a 1 a 2 a 5 mod n 936 displaystyle x a 1 a 2 a 5 mod n 936 nbsp Obchislimo l 1 1 l 2 3 l 3 2 l 4 0 l 5 1 l 6 0 displaystyle l 1 1 l 2 3 l 3 2 l 4 0 l 5 1 l 6 0 nbsp Obchislimo y 23 32 13 mod n 24025 displaystyle y 23 times 32 times 13 mod n 24025 nbsp Cherez te sho 936 24025 mod n displaystyle 936 equiv 24025 pmod n nbsp potribno vzyati nastupnu linijnu zalezhnist U vipadku T 2 4 6 displaystyle T 2 4 6 nbsp otrimuyemo takij samij vislid Nastupna T 3 6 7 v 3 v 6 v 7 0 displaystyle T 3 6 7 v 3 v 6 v 7 0 nbsp Obchislimo x a 3 a 6 a 7 mod n 23405 displaystyle x a 3 a 6 a 7 mod n 23405 nbsp Obchislimo l 1 1 l 2 5 l 3 2 l 4 3 l 5 0 l 6 0 displaystyle l 1 1 l 2 5 l 3 2 l 4 3 l 5 0 l 6 0 nbsp Obchislimo y 25 32 53 mod n 13922 displaystyle y 25 times 32 times 53 mod n 13922 nbsp Teper 23405 13922 mod n displaystyle 23405 not equiv pm 13922 pmod n nbsp otzhe obchislimo gcd x y n gcd 9483 24961 109 displaystyle gcd x y n gcd 9483 24961 109 nbsp Zvidki mayemo dva netrivialnih dilniki dlya 24961 displaystyle 24961 nbsp 109 displaystyle 109 nbsp i 229 displaystyle 229 nbsp Perevirka gladkosti prosiyuvannyamred Zamist perevirki na gladkist pereborom dilnikiv zastosovnoyi na etapi 3 1 vikoristovuyetsya efektivnisha tehnika vidoma yak prosiyuvannya angl sieving Spochatku zvernemo uvagu na te sho yaksho p displaystyle p nbsp ye neparnim prostim u faktor bazi i p displaystyle p nbsp dilit q x displaystyle q x nbsp todi p displaystyle p nbsp takozh dilit q x l p displaystyle q x lp nbsp dlya kozhnogo cilogo l displaystyle l nbsp y x x 2 n displaystyle y x x 2 n nbsp y x k p x k p 2 n displaystyle y x kp x kp 2 n nbsp y x k p x 2 2 x k p k p 2 n displaystyle y x kp x 2 2xkp kp 2 n nbsp y x k p y x 2 x k p k p 2 y x mod p displaystyle y x kp y x 2xkp kp 2 equiv y x pmod p nbsp Otzhe cherez rozv yazannya rivnyannya q x 0 mod p displaystyle q x equiv 0 pmod p nbsp dlya x displaystyle x nbsp dlya cogo isnuye bagato diyevih algoritmiv otrimuyemo odnu abo dvi zalezhno vid kilkosti rozv yazkiv u kvadratnogo rivnyannya poslidovnostej inshih znachen y displaystyle y nbsp dlya yakih p displaystyle p nbsp dilit q y displaystyle q y nbsp Takozh prosiyuvannya vikoristovuye vlastivist logarifma log 1 n p i 1 n log p i displaystyle log prod 1 n p i sum 1 n log p i nbsp Perebig prosiyuvannya takij Stvoryuyetsya masiv Q displaystyle Q nbsp proindeksovanij po x M x M displaystyle x M leq x leq M nbsp i kozhnij zapis inicializuyetsya lg q x displaystyle lg q x nbsp Nehaj x 1 x 2 displaystyle x 1 x 2 nbsp budut rozv yazkami dlya q x 0 mod p displaystyle q x equiv 0 pmod p nbsp de p displaystyle p nbsp ye neparnim prostim chislom z faktor bazi Todi znachennya lg p displaystyle lg p nbsp vidnimayut vid tih zapisiv v Q x displaystyle Q x nbsp dlya yakih x x 1 displaystyle x equiv x 1 nbsp abo x 2 mod p displaystyle x 2 pmod p nbsp i M x M displaystyle M leq x leq M nbsp Diya povtoryuyetsya dlya kozhnogo prostogo p displaystyle p nbsp u faktor bazi Vipadki z p 2 displaystyle p 2 nbsp i stepenyami prostih chisel mozhna obrobiti podibnim chinom Pislya prosiyuvannya zapisi v masivi Q x displaystyle Q x nbsp zi znachennyami blizkimi do 0 displaystyle 0 nbsp shvidshe za vse ye p t displaystyle p t nbsp gladki treba brati do uvagi pomilki okruglennya i ce mozhna pereviriti cherez faktorizaciyu q x displaystyle q x nbsp pereborom dilnikiv Primitkired Carl Pomerance Analysis and Comparison of Some Integer Factoring Algorithms in Computational Methods in Number Theory Part I H W Lenstra Jr and R Tijdeman eds Math Centre Tract 154 Amsterdam 1982 pp 89 139 Povnij perelik linijno zalezhnih pidmnozhin vektoriv takij 125 264 763 1456 2347 13457 1234567 Otrimano z https uk wikipedia org w index php title Kvadratichne resheto amp oldid 42412599