Algoritm Lemana abo algoritm Shermana Lemana determinovano rozkladaye zadane naturalne chislo n displaystyle n na mnozhniki za O n 1 3 displaystyle O n 1 3 arifmetichnih operacij Algoritm zaproponuvav amerikanskij matematik Sherman Leman v 1974 roci 1 Cej algoritm stav pershim algoritmom faktorizaciyi cilih chisel skladnist yakogo mensha nizh O n displaystyle O sqrt n Na sogodni vin maye suto istorichnij interes i yak pravilo ne zastosovuyetsya na praktici 2 Zmist 1 Opis 2 Teoretichne obgruntuvannya 2 1 Formulyuvannya teoremi 2 2 Dovedennya teoremi 3 Algoritm 3 1 Psevdokod 4 Priklad 5 Skladnist 5 1 Kilkist operacij 5 2 Zalezhnist vid rozryadnosti 6 Porivnyannya z inshimi metodami 7 Mozhlivist paralelnih obchislen 7 1 Zagalna ideya 7 2 Realizaciya iz zastosuvannyam tehnologiyi GPGPU 8 Primitki 9 LiteraturaOpis red Spochatku algoritm pereviryaye chi maye n displaystyle n nbsp prosti dilniki yaki ne perevishuyut n 1 3 displaystyle lfloor n 1 3 rfloor nbsp Dali metod Lemana rozvivaye ideyi sho zakladeni v algoritmi Ferma i shukaye dilniki chisla n displaystyle n nbsp vikoristovuyuchi rivnist x 2 y 2 4 b n displaystyle x 2 y 2 4bn nbsp dlya deyakogo cilogo chisla b displaystyle b nbsp Vin bazuyetsya na nastupnij teoremi 2 Formulyuvannya teoremiNehaj n displaystyle n nbsp dodatne neparne cile chislo a r displaystyle r nbsp cile chislo take sho 1 r lt n 1 2 displaystyle 1 leqslant r lt n 1 2 nbsp Yaksho n p q displaystyle n pq nbsp de p displaystyle p nbsp i q displaystyle q nbsp prosti a takozh n r 1 1 2 lt p n 1 2 displaystyle left frac n r 1 right 1 2 lt p leqslant n 1 2 nbsp to todi isnuyut taki nevid yemni cili chisla x displaystyle x nbsp y displaystyle y nbsp k displaystyle k nbsp sho x 2 y 2 4 k n 1 k r displaystyle x 2 y 2 4kn 1 leqslant k leqslant r nbsp x k 1 mod 2 displaystyle x equiv k 1 pmod 2 nbsp x k 1 mod 4 displaystyle x equiv k 1 pmod 4 nbsp yaksho k displaystyle k nbsp neparne 0 x 4 k n 1 2 1 4 r 1 n k 1 2 displaystyle 0 leqslant x 4kn 1 2 leqslant frac 1 4 r 1 left frac n k right 1 2 nbsp i p min gcd x y n gcd x y n displaystyle p min gcd x y n gcd x y n nbsp Yaksho n displaystyle n nbsp proste to takih chisel x displaystyle x nbsp y displaystyle y nbsp k displaystyle k nbsp ne znajdetsya 1 Teoretichne obgruntuvannya red Formulyuvannya teoremi red Nehaj n p q displaystyle n pq nbsp mozhna zapisati yak dobutok dvoh neparnih vzayemno prostih chisel sho zadovolnyayut nerivnostyam n 1 3 lt p lt q lt n 2 3 displaystyle n 1 3 lt p lt q lt n 2 3 nbsp Todi znajdutsya taki naturalni chisla x y displaystyle x y nbsp i k 1 displaystyle k geqslant 1 nbsp sho 1 Vikonuyetsya rivnist x 2 y 2 4 k n displaystyle x 2 y 2 4kn nbsp pri k lt n 1 3 displaystyle k lt n 1 3 nbsp 2 Vikonuyetsya nerivnist 0 x 4 k n lt n 1 6 4 k 1 displaystyle 0 leqslant x lfloor sqrt 4kn rfloor lt frac n 1 6 4 sqrt k 1 nbsp 2 Dlya dovedennya ciyeyi teoremi potribna nastupna lema Lema Nehaj vikonano umovi teoremi Todi mozhna znajti taki naturalni chisla r s displaystyle r s nbsp sho r s lt n 1 3 displaystyle rs lt n 1 3 nbsp i p r q s lt n 1 3 displaystyle mid pr qs mid lt n 1 3 nbsp 3 Dovedennya lemi Yaksho p q displaystyle p q nbsp tobto n p 2 displaystyle n p 2 nbsp to tverdzhennya teoremi vikonuyetsya dlya r s 1 displaystyle r s 1 nbsp Dali budemo vvazhati p lt q displaystyle p lt q nbsp Rozklademo q p displaystyle frac q p nbsp v lancyugovij drib Poznachimo p j q j displaystyle frac p j q j nbsp j displaystyle j nbsp tij nablizhenij drib do q p displaystyle frac q p nbsp Todip 0 q p displaystyle p 0 left frac q p right nbsp q 0 1 displaystyle q 0 1 nbsp 0 lt p 0 q 0 lt n 1 3 displaystyle 0 lt p 0 q 0 lt n 1 3 nbsp oskilki q p lt n 2 3 n 1 3 n 1 3 displaystyle frac q p lt frac n 2 3 n 1 3 n 1 3 nbsp Oberemo pershij nomer m displaystyle m nbsp takij shop m q m lt n 1 3 displaystyle p m q m lt n 1 3 nbsp p m 1 q m 1 gt n 1 3 displaystyle p m 1 q m 1 gt n 1 3 nbsp Takij nomer obov yazkovo znajdetsya bo v ostannomu nablizhenomu drobi znamennik q N p gt n 1 3 displaystyle q N p gt n 1 3 nbsp Dovedemo sho r p m displaystyle r p m nbsp i s q m displaystyle s q m nbsp zadovolnyayut tverdzhennyu lemi Ochevidno sho r s lt n 1 3 displaystyle rs lt n 1 3 nbsp Dali r s q p r s p m 1 q m 1 1 s q m 1 displaystyle left frac r s frac q p right leqslant left frac r s frac p m 1 q m 1 right frac 1 sq m 1 nbsp za vlastivostyami lancyugovogo drobu Rozglyanemo spochatku vipadok p m 1 q m 1 q p displaystyle frac p m 1 q m 1 leqslant frac q p nbsp V comu vipadku p r q s p s r s q p p s s q m 1 p q m 1 p q m 1 p q m 1 p q m 1 q p m 1 n p m 1 q m 1 lt n 1 2 n 1 6 n 1 3 displaystyle pr qs ps left frac r s frac q p right leqslant frac ps sq m 1 frac p q m 1 sqrt frac p q m 1 frac p q m 1 leqslant sqrt frac p q m 1 sqrt frac q p m 1 sqrt frac n p m 1 q m 1 lt frac n 1 2 n 1 6 n 1 3 nbsp sho i potribno bulo dovesti Teper rozglyanemo vipadok p m 1 q m 1 gt q p displaystyle frac p m 1 q m 1 gt frac q p nbsp Nerivnosti prijmut viglyad p m 1 q m 1 gt q p gt p m q m displaystyle frac p m 1 q m 1 gt frac q p gt frac p m q m nbsp i todi q m p m gt p q gt q m 1 p m 1 displaystyle frac q m p m gt frac p q gt frac q m 1 p m 1 nbsp Vidpovidno za vlastivostyami lancyugovih drobiv vikonuyutsya nerivnosti1 r q s r p q s r q m 1 p m 1 1 r p m 1 displaystyle frac 1 rq leqslant left frac s r frac p q right leqslant left frac s r frac q m 1 p m 1 right frac 1 rp m 1 nbsp I todi1 s q p r r q s r p q r q r p m 1 q p m 1 q p m 1 q p m 1 q p m 1 p q m 1 n p m 1 q m 1 lt n 1 2 n 1 6 n 1 3 displaystyle 1 leqslant sq pr rq left frac s r frac p q right leqslant frac rq rp m 1 frac q p m 1 sqrt frac q p m 1 frac q p m 1 leqslant sqrt frac q p m 1 sqrt frac p q m 1 sqrt frac n p m 1 q m 1 lt frac n 1 2 n 1 6 n 1 3 nbsp Lemu dovedeno 3 Dovedennya teoremi red Pripustimo sho p displaystyle p nbsp i q displaystyle q nbsp neparni dilniki chisla n displaystyle n nbsp i nehaj x p r q s displaystyle x pr qs nbsp i y p r q s displaystyle y pr qs nbsp de r displaystyle r nbsp i s displaystyle s nbsp zadovolnyayut tverdzhennya lemi todi vikonuyetsya rivnist x 2 y 2 p r q s 2 p r q s 2 4 r s p q 4 k n displaystyle x 2 y 2 pr qs 2 pr qs 2 4rspq 4kn nbsp de k r s displaystyle k rs nbsp V silu lemi cile chislo k displaystyle k nbsp zadovolnyaye nerivnosti k lt n 1 3 displaystyle k lt n 1 3 nbsp Otzhe vikonano pershe tverdzhennya teoremi Dlya dovedennya drugogo tverdzhennya poklademo z x 4 b n p r q s 4 b n displaystyle z x lfloor sqrt 4bn rfloor pr qs lfloor sqrt 4bn rfloor nbsp tak yak x 2 4 k n y 2 displaystyle x 2 4kn y 2 nbsp to x 4 k n displaystyle x geqslant sqrt 4kn nbsp i z 0 displaystyle z geqslant 0 nbsp Vikoristovuyuchi ocinku zverhu dlya y displaystyle y nbsp otrimuyemo n 2 3 gt y 2 x 2 4 k n p r q s 4 k n p r q s 4 k n 2 4 k n p r q s 4 k n 2 4 k n z 1 displaystyle n 2 3 gt y 2 x 2 4kn pr qs sqrt 4kn pr qs sqrt 4kn geqslant 2 sqrt 4kn pr qs sqrt 4kn geqslant 2 sqrt 4kn z 1 nbsp Z cogo viplivaye sho z lt n 2 3 2 4 k n 1 n 1 6 4 k 1 displaystyle z lt frac n 2 3 2 sqrt 4kn 1 frac n 1 6 4 sqrt k 1 nbsp Teoremu dovedeno 4 Algoritm red Nehaj n displaystyle n nbsp neparne i n gt 8 displaystyle n gt 8 nbsp Krok 1 Dlya prostih a 2 3 n 1 3 displaystyle a 2 3 ldots lfloor n 1 3 rfloor nbsp pereviriti umovu a n displaystyle a mid n nbsp Yaksho na comu kroci ne vdalosya rozklasti n displaystyle n nbsp na mnozhniki to perehodimo do kroku 2 Krok 2 Yaksho na kroci 1 dilnik ne znajdeno i n displaystyle n nbsp skladene chislo to n p q displaystyle n pq nbsp de p q displaystyle p q nbsp prosti chisla i n 1 3 lt p q lt n 2 3 displaystyle n 1 3 lt p leqslant q lt n 2 3 nbsp Todi dlya vsih k 1 2 n 1 3 displaystyle k 1 2 ldots lfloor n 1 3 rfloor nbsp i vsih d 0 n 1 6 4 k 1 displaystyle d 0 ldots left lfloor frac n 1 6 4 sqrt k right rfloor 1 nbsp pereviriti chi ye chislo 4 k n d 2 4 k n displaystyle left left lfloor sqrt 4kn right rfloor d right 2 4kn nbsp kvadratom naturalnogo chisla Yaksho ce tak to dlya A 4 k n d displaystyle A left lfloor sqrt 4kn right rfloor d nbsp i B A 2 4 k n displaystyle B sqrt A 2 4kn nbsp vikonuyetsya vzyattya po modulyu A 2 B 2 mod n displaystyle A 2 equiv B 2 pmod n nbsp chi A B A B 0 mod n displaystyle A B A B equiv 0 pmod n nbsp U comu vipadku dlya d gcd A B n displaystyle d gcd A B n nbsp pereviryayetsya nerivnist 1 lt d lt n displaystyle 1 lt d lt n nbsp i yaksho cya nerivnist vikonuyetsya to n d n d displaystyle n d cdot n d nbsp rozklad n displaystyle n nbsp na dva mnozhniki Yaksho zh algoritm ne znajshov rozkladu n displaystyle n nbsp na dva mnozhniki to n displaystyle n nbsp proste chislo 5 Cej algoritm spochatku pereviryaye chi maye n displaystyle n nbsp prosti dilniki yaki ne perevishuyut n 1 3 displaystyle lfloor n 1 3 rfloor nbsp a potim pochinaye perebir znachen k displaystyle k nbsp i d displaystyle d nbsp dlya perevirki vikonannya teoremi U vipadku koli shukani znachennya x displaystyle x nbsp i y displaystyle y nbsp ne znajdeno otrimuyemo sho chislo n displaystyle n nbsp proste Takim chinom mozhna rozglyadati cej algoritm i yak test chisla n displaystyle n nbsp na prostotu 6 Psevdokod red for a 2 displaystyle a gets 2 nbsp to n 1 3 displaystyle lfloor n 1 3 rfloor nbsp do if a mod n 0 displaystyle a mod n 0 nbsp thenreturn a displaystyle a nbsp dd end ifend forfor k 1 displaystyle k gets 1 nbsp to n 1 3 displaystyle lfloor n 1 3 rfloor nbsp do for d 0 displaystyle d gets 0 nbsp to n 1 6 4 k 1 displaystyle left lfloor frac n 1 6 4 sqrt k right rfloor 1 nbsp doif i s S q u a r e 4 k n d 2 4 k n displaystyle isSquare lfloor sqrt 4kn rfloor d 2 4kn nbsp thenA 4 k n d displaystyle A gets lfloor sqrt 4kn rfloor d nbsp B A 2 4 k n displaystyle B gets sqrt A 2 4kn nbsp if 1 lt g c d A B n lt n displaystyle 1 lt gcd A B n lt n nbsp thenreturn g c d A B n displaystyle gcd A B n nbsp dd else if 1 lt g c d A B n lt n displaystyle 1 lt gcd A B n lt n nbsp thenreturn g c d A B n displaystyle gcd A B n nbsp dd end if dd end if dd end forend forPoyasnennya Funkciya i s S q u a r e a displaystyle isSquare a nbsp povertaye t r u e displaystyle true nbsp yaksho a displaystyle a nbsp ye povnim kvadratom i f a l s e displaystyle false nbsp v inshomu vipadku Funkciya g c d a b displaystyle gcd a b nbsp povertaye najbilshij spilnij dilnik chisel a displaystyle a nbsp i b displaystyle b nbsp 7 Priklad red Rozglyanemo priklad n 1387 displaystyle n 1387 nbsp n 1 3 11 displaystyle lfloor n 1 3 rfloor 11 nbsp Dlya a 2 3 5 7 11 displaystyle a 2 3 5 7 11 nbsp pereviryayemo chi ye chislo a displaystyle a nbsp dilnikom chisla n displaystyle n nbsp Ne vazhko perekonatis sho takih nemaye Perehodimo do nastupnogo kroku Dlya vsih k 1 2 3 11 displaystyle k 1 2 3 ldots 11 nbsp i vsih d 0 1 4 displaystyle d 0 1 ldots 4 nbsp pereviryayemo chi ye chislo 4 k n d 2 4 k n displaystyle left left lfloor sqrt 4kn right rfloor d right 2 4kn nbsp kvadratom naturalnogo chisla U nashomu vipadku dlya k 3 displaystyle k 3 nbsp i d 1 displaystyle d 1 nbsp viraz 4 k n d 2 4 k n displaystyle left left lfloor sqrt 4kn right rfloor d right 2 4kn nbsp dorivnyuye 256 yake ye kvadratom 256 16 2 displaystyle 256 16 2 nbsp Vidpovidno A 4 3 1387 1 130 displaystyle A lfloor sqrt 4 times 3 times 1387 rfloor 1 130 nbsp i B 16 displaystyle B 16 nbsp Todi d A B n 19 displaystyle d A B n 19 nbsp zadovolnyaye nerivnosti 1 lt d lt n displaystyle 1 lt d lt n nbsp i ye dilnikom chisla n displaystyle n nbsp U rezultati mi rozklali chislo 1387 displaystyle 1387 nbsp na dva mnozhniki 73 displaystyle 73 nbsp i 19 displaystyle 19 nbsp Skladnist red Kilkist operacij red Na pershomu kroci treba zrobiti n 1 3 displaystyle lceil n 1 3 rceil nbsp operacij dlya poshuku malih dilnikiv chisla n displaystyle n nbsp Skladnist drugogo kroku ocinyuyetsya v operaciyah perevirki chi ye chislo 4 k n d 2 4 k n displaystyle left left lfloor sqrt 4kn right rfloor d right 2 4kn nbsp povnim kvadratom Kilkist operacij ocinyuyetsya zverhu velichinoyu n 1 6 4 k 1 n 1 6 1 k 2 n 1 3 n 1 6 lt 3 n 1 3 displaystyle frac n 1 6 4 sum k 1 lfloor n 1 6 rfloor frac 1 sqrt k 2 lceil n 1 3 rceil lfloor n 1 6 rfloor lt 3 lceil n 1 3 rceil nbsp Takim chinom skladnist usogo algoritmu O n 1 3 displaystyle O n 1 3 nbsp operacij 6 Zalezhnist vid rozryadnosti red Dlya velikih chisel isnuye zalezhnist chasu vikonannya operacij vid yih rozryadnosti Napriklad skladannya dvoh chisel potrebuye chasu sho linijno zalezhit vid dovzhini bilshogo z nih a chas mnozhennya j dilennya she bilshij tobto zalezhit vid dovzhini chisel nelinijno polinomialno Otzhe metod potrebuye polinomialnoyi kilkosti operacij O n 1 3 displaystyle O n 1 3 nbsp ale chas kozhnoyi operaciyi shonajmenshe linijno zalezhit vid dovzhini rozryadnosti chisla Takim chinom vinikaye eksponencijna zalezhnist chasu vikonannya algoritmu vid rozryadnosti chisla sho faktorizuyetsya O n n 1 3 displaystyle O n n 1 3 nbsp 7 n 2 l displaystyle n simeq 2 l nbsp de l displaystyle l nbsp rozryadnist O n 1 3 O 2 l 3 O e l 3 displaystyle O n 1 3 O 2 l 3 O e l 3 nbsp Porivnyannya z inshimi metodami red Yak pokrashennya metodu Ferma metod Lemana takozh istotno zalezhit vid vidstani mizh mnozhnikami chisla chas jogo vikonannya linijno zalezhit vid distanciyi dzherelo Odnak yaksho riznicya mizh mnozhnikami mala to metod Lemana znachno prograye metodu Ferma dzherelo Dlya chisel iz nevelikim prostim dilnikom situaciya insha metod Lemana zavdyaki poslidovnomu dilennyu na pershomu kroci dosit shvidko vidilit prostij mnozhnik 7 Mozhlivist paralelnih obchislen red Zagalna ideya red Paralelna realizaciya bazuyetsya na nastupnomu pidhodi 7 Krok 1 Kozhnomu obchislyuvalnomu procesu sho bere uchast u faktorizaciyi vidayetsya svij nabir potencijnih dilnikiv z mnozhini 2 3 4 n 1 3 displaystyle 2 3 4 ldots lfloor n 1 3 rfloor nbsp Obchislyuvalnij proces pochergovo pereviryaye n displaystyle n nbsp na kratnist chislam zi svogo naboru dilnikiv Cherez deyaki promizhki chasu golovnij proces koordinator opituye obchislyuvalni procesi na predmet viyavlennya dilnika U vipadku koli dostatno pereviriti n displaystyle n nbsp na prostotu proces koordinator otrimavshi informaciyu pro znajdennya dilnika nadsilaye inshim procesam signal pro zavershennya roboti Yaksho zh dilnik ne znajdeno chi potribno znajti vsi dilniki poshuk prodovzhuyetsya Krok 2 Kozhnomu obchislyuvalnomu procesu analogichno z krokom 1 vidayetsya svij nabir chisel k displaystyle k nbsp z mnozhini 2 3 4 n 1 3 displaystyle 2 3 4 ldots lfloor n 1 3 rfloor nbsp Obchislyuvalnij proces po cherzi pereviryaye vsi umovi opisani v algoritmi viznachayuchi chi znajdenij netrivialnij mnozhnik Analogichno z krokom 1 proces koordinator periodichno opituye procesi shodo znajdennya dilnika i prijmaye rishennya pro pripinennya chi prodovzhennya obchislen Zastosuvannya cogo pidhodu dozvolyaye otrimati linijne priskorennya pri zbilshenni kilkosti procesiv na komp yuteri z rozdilenoyu pam yattyu 7 Realizaciya iz zastosuvannyam tehnologiyi GPGPU red Dlya uspishnoyi realizaciyi algoritmu iz zastosuvannyam tehnologiyi GPGPU treba virishiti dva pitannya 8 Dlya kozhnoyi operaciyi algoritmu virishiti de varto yiyi vikonuvati na CP chi na grafichnomu procesori Viznachiti kilkist yader grafichnogo procesora sho zastosovuyutsya Opisanij vishe pidhid mozhna zastosovuvati dlya rozbittya zadachi 8 Krok 2 Usi operaciyi cogo kroku slid vikonuvati na grafichnomu procesori Nehaj k e r displaystyle ker nbsp kilkist dostupnih yader grafichnogo procesora l a displaystyle la nbsp kilkist elementiv mnozhini 2 3 4 n 1 3 displaystyle 2 3 4 ldots lfloor n 1 3 rfloor nbsp Rozglyanemo dva vipadki l a k e r displaystyle la leqslant ker nbsp Vikoristayemo l a displaystyle la nbsp yader grafichnogo procesora l a gt k e r displaystyle la gt ker nbsp Vikonayemo l a k e r displaystyle left lceil frac la ker right rceil nbsp iteracij Na kozhnij iteraciyi vikonuyemo k e r displaystyle ker nbsp operacij dilennya na k e r displaystyle ker nbsp yadrah U kinci kozhnoyi iteraciyi viznachayemo zavershiti proces chi ni Krok 2 Rozpodiliti k displaystyle k nbsp mizh yadrami grafichnogo procesora tak zhe yak i v kroci 1 Na kozhnomu yadri vikonati 1 3 Pereviriti chi ye chislo 4 k n d 2 4 k n displaystyle left left lfloor sqrt 4kn right rfloor d right 2 4kn nbsp kvadratom naturalnogo chisla U vipadku otrimannya pozitivnogo rezultatu na poperednomu punkti obchisliti A 4 k n d displaystyle A left lfloor sqrt 4kn right rfloor d nbsp i B A 2 4 k n displaystyle B sqrt A 2 4kn nbsp Dlya znachen A displaystyle A nbsp i B displaystyle B nbsp pereviriti umovu A 2 B 2 mod n displaystyle A 2 equiv B 2 pmod n nbsp Dlya znachen A displaystyle A nbsp i B displaystyle B nbsp sho projshli ostannyu perevirku pereviriti vikonannya umovi 0 lt gcd A B n lt n displaystyle 0 lt gcd A pm B n lt n nbsp Ostannij punkt krashe vikonuvati na CP oskilki jmovirnist vikonannya cih operacij dosit mala a taka perevirka na grafichnomu procesori vidbuvayetsya dosit povilno 8 Primitki red a b Lehman R Sherman Factoring Large Integers Mathematics of Computation 1974 T 28 126 S 637 646 DOI 10 2307 2005940 a b v Nesterenko 2011 s 140 a b Vasilenko 2003 s 65 66 Nesterenko 2011 s 142 Vasilenko 2003 s 65 a b Nesterenko 2011 s 143 a b v g d Makarenko A V Pyhteev A V Efimov S S ISSLEDOVANIE PARALLELNYH ALGORITMOV FAKTORIZACII CELYH ChISEL V VYChISLITELNYH KLASTERNYH SISTEMAH Omskij gosudarstvennyj universitet im F M Dostoevskogo Omsk 2012 T 4 66 S 149 158 a b v Zheltov S A ADAPTACIYa METODA ShERMANA LEMANA REShENIYa ZADAChI FAKTORIZACII K VYChISLITELNOJ ARHITEKTURE CUDA Rossijskij gosudarstvennyj gumanitarnyj universitet Moskva 2012 T 14 94 S 84 91 Literatura red Vasilenko O N Teoretiko chislovye algoritmy v kriptografii M MCNMO 2003 328 s ISBN 5 94057 103 4 Aleksej Nesterenko Vvedenie v sovremennuyu kriptografiyu MCNMO 2011 190 s Richard Crandall Carl Pomerance A Computational Perspectives 2nd Springer 2011 597 s ISBN 0 387 25282 7 Otrimano z https uk wikipedia org w index php title Metod Lemana amp oldid 40554428
