Lehmannin menetelmä

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 6. lokakuuta 2016 tarkistetusta versiosta . tarkastukset vaativat 45 muokkausta .

Lehmanin algoritmi (tai Sherman Lehmanin algoritmi ) jakaa tietyn luonnollisen luvun deterministisesti aritmeettisissa operaatioissa . Ensimmäisen algoritmin ehdotti amerikkalainen matemaatikko Sherman Lehman vuonna 1974 [1] . Tämä algoritmi oli ensimmäinen deterministinen kokonaislukufaktorointialgoritmi, jonka arvio oli pienempi kuin . Tällä hetkellä se on puhtaasti historiallisesti kiinnostava, eikä sitä pääsääntöisesti käytetä käytännössä. [2] $n$ $O(n^{{1/3}})$ $O({\sqrt {n)))$

Lehmannin menetelmä

Lehmannin menetelmä kehittää Fermatin faktorointimenetelmän ajatuksia ja etsii luvun jakajia käyttämällä yhtälöä jollekin kokonaisluvulle . Se perustuu seuraavaan lauseeseen. [2] $n$ $x^{2}-y^{2}=4 kn$ $k$

Lauseen lause [1]

Oletetaan, että se on positiivinen pariton kokonaisluku ja on sellainen kokonaisluku, että . Jos , missä ja ovat yksinkertaisia ja $n$ $r$ ${\displaystyle 1\leqslant r<n^{1/2))$ $n = pq$ $s$ $q$

\left({\frac {n}{r+1}}\right)^{1/2}<p\leqslant n^{1/2}

sitten on ei-negatiivisia kokonaislukuja , Ja Sellainen, että $x$ $y$ $k$

x^{2}-y^{2}=4kn,1\leqslant k\leqslant r

x\equiv k+1{\pmod {2}}

x\equiv k+1{\pmod {4}}

, jos outoa,

k

0\leqslant x-(4kn)^{1/2}\leqslant {\frac {1}{4(r+1)}}\left({\frac {n}{k}}\oikea) ^{1/2}

p=\min(\gcd(x+y,\;n),\;\gcd(xy,\;n))

Jos on alkuluku, tällaisia numeroita , ja ei ole olemassa. $n$ $x$ $y$ $k$

Muokattu Lehmannin menetelmä

Lauseen lause

Olkoon komposiittiluku, joka on kahden epäyhtälöt tyydyttävän parittoman koprimeluvun tulo . Sitten on luonnollisia lukuja ja sellaisia $n=pq$ ${\displaystyle n^{1/3}<p<q<n^{2/3))$ $x,\;y$ $k\geqslant 1$

1. Tasa-arvo pätee , 2. Epätasa-arvo pätee . [2] Tämän lauseen todistamiseksi tarvitsemme seuraavan lemman.

x^{2}-y^{2}=4 kn

k<n^{1/3}

0\leqslant x-\lfloor {\sqrt {4kn}}\rfloor <{\frac {n^{1/6}}{4{\sqrt {k}}}}+1

Lemma

Olkoon lauseen ehdot täyttyvät. Sitten on luonnollisia lukuja , että ja .

[3]

r,\;s

rs<n^{1/3}

\mid pr-qs\mid <n^{1/3}

Todiste lemasta

Jos , eli , niin lauseen väite pätee . Seuraavaksi lasketaan . $p=q$ $n=p^{2}$ $r=s=1$ $p<q$

Laajennetaan se jatkuvaksi murto - osaksi . Merkitään th konvergentti k :llä . Sitten ${\frac {q}{p))$ ${\frac {p_{j}}{q_{j}}}$ $j$ ${\frac {q}{p))$

$p_{0}=\left[{\frac {q}{p}}\right]$ ... _ _ $q_{0}=1$ ${\displaystyle 0<p_{0}q_{0}<n^{1/3))$

koska . Valitsemme ensimmäisen numeron siten ${\frac {q}{p}}<{\frac {n^{2/3}}{n^{1/3}}}=n^{1/3}$ $m$

${\displaystyle p_{m}q_{m}<n^{1/3))$ , . ${\displaystyle p_{m+1}q_{m+1}>n^{1/3))$

Sellainen luku varmasti löytyy, sillä viimeisellä sopivalla murtoluvulla on nimittäjä . Todistakaamme tämä ja hyväksykäämme lemman väite. On selvää, että . Edelleen, ${\displaystyle q_{N}=p>n^{1/3))$ ${\displaystyle r=p_{m))$ ${\displaystyle s=q_{m))$ $rs<n^{1/3}$

$\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}}}$

sopivien fraktioiden ominaisuudet.

Tarkastellaanpa tapausta ensin . Tässä tapauksessa ${\frac {p_{m+1}}{q_{m+1}}}\leqslant {\frac {q}{p}}$

$|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))))<{\frac {n^{1/2}}{n^{1/6}}}=n^{ 1 /3}$ ,

Q.E.D.

Harkitse nyt tapausta . Sitten käännämme eriarvoisuudet , mistä . Siksi jatkuvien murtolukujen ominaisuuksien perusteella epäyhtälöt ${\frac {p_{m+1}}{q_{m+1}}}>{\frac {q}{p}}$ ${\frac {p_{m+1}}{q_{m+1}}}>{\frac {q}{p}}>{\frac {p_{m}}{q_{m}} }$ ${\frac {q_{m}}{p_{m}}}>{\frac {p}{q}}>{\frac {q_{m+1}}{p_{m+1}} }$

${\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}}}$ . Täältä

$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))))<{\frac {n^{1/2}}{n^{1/6}}}= n ^{1/3}$

Lemma on todistettu. [3]

Lauseen todistus

Antaa ja olla parittomia jakajia . Antaa ja , Jos ja täyttää lausunnon Lemma, niin tasa-arvo pätee , Missä . Lemman mukaan kokonaisluku täyttää epäyhtälön . Näin ollen lauseen ensimmäinen väite täyttyy. $s$ $q$ $n$ $x=pr+qs$ $y=pr-qs$ $r$ $s$
$x^{2}-y^{2}=(pr+qs)^{2}-(pr-qs)^{2}=4rspq=4kn$
$k=rs$ $k$ $k<n^{1/3}$

Todistaaksemme toisen väitteen, asetamme , Koska , Sitten ja . Käyttämällä ylempää arviota saamme . Mistä se seuraa . Lause on todistettu. [neljä] $z=x-\lfloor {\sqrt {4bn}}\rfloor =pr+qs-\lfloor {\sqrt {4bn}}\rfloor$ $x^{2}=4kn+y^{2}$ $x\geqslant {\sqrt {4kn))$ $z\geqslant 0$ $y$
$n^{2/3}>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)$
$z<{\frac {n^{2/3}}{2{\sqrt {4kn}}}}+1={\frac {n^{1/6}}{4{\sqrt {k }}}}+1$

Algoritmi (muokattu)

Olkoon outo ja . $n$ $n>8$

Vaihe 1. Tilan tarkistaminen . Jos tekijöiden lisääminen ei ollut mahdollista tässä vaiheessa , siirry vaiheeseen 2. $a=2,\;3,\;\ldots ,\;\lfloor n^{1/3}\rfloor$ $a\mid n$ $n$

Vaihe 2. Jos vaiheessa 1 jakajaa ei löydy ja se on yhdistetty , niin , missä ovat alkuluvut , ja . Tarkista sitten kaikille , onko luku luonnollisen luvun neliö. Jos on, niin vertailu tehdään ja : $n$ $n = pq$ $p,\;q$ ${\displaystyle n^{1/3}<p\leqslant q<n^{2/3))$ $k=1,\;2,\;\ldots ,\;\lfloor n^{1/3}\rfloor$ $d=0,\;\ldots ,\;\left\lfloor {\frac {n^{1/6}}{4{\sqrt {k}}}}\right\rfloor +1$ $\left(\left\lfloor {\sqrt {4kn))\right\rfloor +d\right)^{2}-4kn$ $A=\left\lfloor {\sqrt {4kn))\right\rfloor +d$ $B={\sqrt {A^{2}-4 kn))$

A^{2}\equiv B^{2}{\pmod {n))

tai .

(AB)(A+B)\equiv 0{\pmod {n))

Tässä tapauksessa epäyhtälö tarkistetaan . Jos se täyttyy, se on jakaminen kahteen tekijään. $d^{*}=\gcd(AB,\;n)$ ${\näyttötyyli 1<d^{*}<n}$ $n=d^{*}\cdot (n/d^{*})$ $n$

Jos algoritmi ei ole löytänyt jakautumista kahdeksi tekijäksi, se on alkuluku. [5] $n$ $n$

Tämä algoritmi tarkistaa ensin, onko sillä alkujakajia, jotka eivät ylitä , ja sitten järjestää arvojen haun ja tarkistaa seuraavan lauseen toteutettavuuden. Jos haluttuja arvoja ja ei löydy, saamme, että luku on alkuluku. Näin ollen voimme pitää tätä algoritmia yksinkertaisuuden testinä [6] $n$ $\lfloor n^{1/3}\rfloor$ $k$ $d$ $x$ $y$ $n$ $n$

Työvoima

Lasketaan riippuvuus tekijöille jaetun luvun suuruudesta

Ensimmäinen askel on suorittaa jakooperaatiot luvun pienten jakajien löytämiseksi . $\lceil n^{1/3}\rceil$ $n$

Toisen vaiheen monimutkaisuus arvioidaan operaatioissa, joissa luku testataan , onko se täydellinen neliö. Toisen vaiheen monimutkaisuus arvioidaan ylhäältä arvon avulla $\left(\left\lfloor {\sqrt {4kn))\right\rfloor +d\right)^{2}-4kn$

${\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 )}<3\lceil n^{1/3}\rceil$ .
Siten kaiken monimutkaisuus on arvo . [6] $O(n^{{1/3}})$

Riippuvuus kertoimen luvun kapasiteetista

Useimmissa tapauksissa suoritusajan riippuvuus tutkittavan luvun bittisyvyydestä on tärkeämpi rooli. Kun arvolle on polynomiriippuvuus, saamme Lehmannin menetelmän suoritusajan eksponentiaalisen riippuvuuden faktoroidun luvun sanan pituudesta. [7]

${\displaystyle n\simeq 2^{l))$ , missä on bitin syvyys. $l$

$O(n^{1/3})=O(2^{l/3})=O(e^{l/3})$

Jotkut erikoistapaukset

Fermatin menetelmän parannuksena Lehmannin menetelmä riippuu myös merkittävästi luvun tekijöiden välisestä etäisyydestä, sen suoritusaika riippuu lineaarisesti etäisyydestä. Kuitenkin, jos tekijöiden välinen etäisyys on pieni, Lehmannin menetelmä häviää merkittävästi Fermat-menetelmälle .

Lukujen, joissa on pieni alkujakaja, tilanne on päinvastainen - Lehmann-menetelmä valitsee nopeasti alkutekijän peräkkäisten jakojen ansiosta vaiheessa yksi. [7]

Pseudokoodi

for $a\gets 2$ to $\lfloor n^{1/3}\rfloor$ do

a\vdots n

then return

a

end if

end for for $k\gets 1$ to $\lfloor n^{1/3}\rfloor$ do

for

d\gets 0

\left\lfloor {\frac {n^{1/6}}{4{\sqrt {k}}}}\right\rfloor +1

do if

isSquare((\lfloor {\sqrt {4kn}}\rfloor +d)^{2}-4kn)=true

then

A\gets \lfloor {\sqrt {4kn}}\rfloor +d

B\saa {\sqrt {A^{2}-4 kn))

1<gcd(A+B,n)<n

then return

gcd(A+B,n)

else if

1<gcd(AB,n)<n

then return

gcd(AB,n)

end if end if end for

end for

Selitykset:

$a\vdots n$ tarkoittaa, että on kokonaisluku jaollinen . $n$ $a$

Funktio palauttaa jos on täydellinen neliö ja muuten. $isSquare(a)$ $totta$ $a$ $false$

Funktio palauttaa lukujen ja :n suurimman yhteisen jakajan . [7] $gcd(a,b)$ $a$ $b$

Menetelmän rinnakkaisen toteutuksen mahdollisuudet

Yleinen idea

Rinnakkaistoteutus perustuu seuraavaan lähestymistapaan: [7]

Vaihe 1:
Jokaiselle tekijöihin jakamiseen liittyvälle laskennalliselle prosessille annetaan oma joukko mahdollisia jakajia joukosta . Laskennallinen prosessi tarkistaa vuorotellen jaollisuuden jakajajoukon elementeillä. Tietyin aikavälein pääkoordinaattoriprosessi " kyseenalaistaa" laskennalliset prosessit jakajan määrittämiseksi. Siinä tapauksessa, että yksinkertaisuuden tarkistaminen riittää , koordinaattoriprosessi, saatuaan tiedon jakajan sijainnista, lähettää signaalin muille prosesseille työn lopettamiseksi. Jos jakajaa ei löydy tai tavoitteena on löytää kaikki jakajat, jakajien haku jatkuu. ${\displaystyle \{2,\;3,\;4,\;\ldots \lfloor n^{1/3}\rfloor \))$ $n$ $n$

Vaihe 2:
Jokaiselle laskentaprosessille, kuten vaiheelle 1, annetaan oma numerosarja joukosta . Laskennallinen prosessi tarkistaa vuorotellen kaikki algoritmissa kuvatut ehdot ja määrittää, löytyykö ei-triviaali tekijä. Vastaavasti vaiheessa 1 koordinaattoriprosessi kyselyt ajoittain prosesseille jakajaa etsiessään ja päättää suorittaako laskelmat loppuun vai ei. $k$ ${\displaystyle \{2,\;3,\;4,\;\ldots \lfloor n^{1/3}\rfloor \))$

Tämän lähestymistavan soveltaminen mahdollistaa lineaarisen kiihtyvyyden saavuttamisen prosessien lukumäärän kasvaessa koneessa, jossa on hajautettu muisti. [7]

Toteutus GPGPU- tekniikalla

Jotta GPGPU -tekniikkaa käyttävä algoritmi voidaan toteuttaa onnistuneesti , on ratkaistava kaksi ongelmaa: [8]
1. Päätä jokaiselle algoritmin toiminnalle, kannattaako se suorittaa CPU :lla vai GPU :lla .
2. Määritä käytettyjen GPU -ytimien määrä .

Yllä kuvattua lähestymistapaa voidaan käyttää ongelman jakamiseen. [kahdeksan]

Vaihe 1:
Kaikki tämän vaiheen toiminnot tulee suorittaa GPU :lla .

Olkoon käytettävissä olevien GPU - ytimien lukumäärä , joukon elementtien lukumäärä . Harkitse kahta tapausta: 1. : Käytämme GPU- ytimiä . 2 .: Järjestä iteraatiot . Jokaisessa iteraatiossa suoritamme seuraavat jaot ytimille. Jokaisen iteraation lopussa päätämme, viedäänkö suoritus loppuun vai jatketaanko sitä. $ker$ $la$ ${\displaystyle \{2,\;3,\;4,\;\ldots \lfloor n^{1/3}\rfloor \))$
$la\leqslantker$ $la$
$la>ker$ $\left\lceil {\frac {la}{ker}}\right\rceil$ $ker$ $ker$

Vaihe 2:

Jaa GPU - ytimien kesken samalla tavalla kuin vaiheessa 1. Suorita vaiheet 1-3 jokaiselle GPU -ytimelle: 1. Tarkista, onko luku luonnollisen luvun neliö. 2. Jos saat positiivisen tuloksen edellisestä kappaleesta, laske ja . 3. Katso arvot ja tarkista kunto . 4. Tarkista arvoille ja , jotka läpäisivät viimeisen tarkistuksen, että kaksoisehto täyttyy . $k$
$\left(\left\lfloor {\sqrt {4kn))\right\rfloor +d\right)^{2}-4kn$
$A=\left\lfloor {\sqrt {4kn))\right\rfloor +d$ $B={\sqrt {A^{2}-4 kn))$
$A$ $B$ $A^{2}\equiv B^{2}{\pmod {n))$
$A$ $B$ $0<\gcd(A\pm B,\;n)<n$

On suositeltavaa suorittaa viimeinen piste CPU :lla , koska näiden toimintojen suorittamisen todennäköisyys on pieni ja GPU :n haaratarkistus on melko hidasta. [kahdeksan]

Esimerkki

Analysoidaan esimerkkiä , sitten , missä , tarkistamme, onko luku luvun jakaja . On helppo varmistaa, että niitä ei ole, sitten siirrymme seuraavaan kappaleeseen. $n=1387$ $a=1,\;2,\;3,\;\ldots ,\;\lfloor n^{1/3}\rfloor$ $\lfloor n^{1/3}\rfloor =11$ $a$ $n$

Tarkistamme kaikille ja kaikille , onko luku luonnollisen luvun neliö. Meidän tapauksessamme on olemassa ja sellaisia, että lauseke on täydellinen neliö ja on yhtä suuri kuin . Siksi ja . Sitten , täyttää epäyhtälön ja on luvun jakaja . Tämän seurauksena jaoimme luvun kahteen tekijään: ja . $k=1,\;2,\;3,\;\ldots ,\;11$ $d=0,\;1,\;\ldots ,\;4$ $\left(\left\lfloor {\sqrt {4kn))\right\rfloor +d\right)^{2}-4kn$ $k = 3$ $d=1$ $\left(\left\lfloor {\sqrt {4kn))\right\rfloor +d\right)^{2}-4kn$ $256=16^{2}$ $A=130$ $B=16$ $d^{*}=(AB;\;n)=19$ ${\näyttötyyli 1<d^{*}<n}$ $n$ $1387$ $73$ $19$

Muistiinpanot

↑ 1 2 Lehman, R. Sherman. Suurten kokonaislukujen faktorointi // Laskennan matematiikka. - 1974. - T. 28 , nro 126 . - S. 637-646 . - doi : 10.2307/2005940 .
↑ 1 2 3 Nesterenko, 2011 , s. 140.
↑ 1 2 Vasilenko, 2003 , s. 65-66.
↑ Nesterenko, 2011 , s. 142.
↑ Vasilenko, 2003 , s. 65.
↑ 1 2 Nesterenko, 2011 , s. 143.
↑ 1 2 3 4 5 Makarenko A.V., Pykhteev A.V., Efimov S.S. Rinnakkaislukujen tekijöiden määrittelyalgoritmien tutkimus klusterijärjestelmissä // Omsk State University. F. M. Dostojevski (Omsk). - 2012. - V. 4 , nro 66 . - S. 149-158 .
↑ 1 2 3 Zheltov S. A. Sherman–Lehman-menetelmän mukauttaminen tekijöiden muodostusongelman ratkaisemiseksi CUDA-laskentaarkkitehtuuriin // Russian State University for the Humanities (Moskova). - 2012. - T. 14 , nro 94 . - S. 84-91 .

Kirjallisuus

Vasilenko O. N. Lukuteoreettiset algoritmit kryptografiassa . - M .: MTSNMO , 2003. - 328 s. — ISBN 5-94057-103-4 . Arkistoitu 27. tammikuuta 2007 Wayback Machinessa
Aleksei Nesterenko. Johdatus nykyaikaiseen kryptografiaan . - MTSNMO , 2011. - 190 s.
Richard Crandall, Carl Pomerance. Laskennalliset näkökulmat . – 2. - Springer, 2011. - 597 s. — ISBN 0-387-25282-7 .

Lukuteoreettiset algoritmit
Yksinkertaisuustestit	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saksi Nightingale - Strassen
Alkulukujen löytäminen	Iterointi jakajien yli Eratosthenesin seula Atkinin seula Seula Sundarama
Faktorisointi	Iterointi jakajien yli Fermat menetelmä p −1 Pollardin menetelmä Pollardin ρ-algoritmi Lehmannin menetelmä Elliptisen käyrän menetelmä (Lenstran algoritmi) Dixonin algoritmi Neliömäinen seula
Diskreetti logaritmi	Gelfond-Shanks -algoritmi Polig-Hellman-algoritmi Pollardin ρ-menetelmä Pollardin kenguru-algoritmi Adlemanin algoritmi COS-algoritmi
GCD:n löytäminen	Eukleideen algoritmi Kehittynyt algoritmi Binäärinen algoritmi
Modulo-aritmetiikka	Montgomeryn algoritmi Kiinan jäännöslause
Lukujen kerto- ja jakolasku	Karatsuba-algoritmi Toom-Cook-algoritmi Schönhage-Strassen-algoritmi Fuhrer-algoritmi Harvey-van der Hoeven-algoritmi Burnickel-Ziegler-algoritmi
Neliöjuuren laskeminen	Tonelli-Shanks-algoritmi Berlekamp-Rabin-algoritmi