Lehmanns metode

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 6. oktober 2016; checks kræver 45 redigeringer .

Lehmans algoritme (eller Sherman Lehmans algoritme ) faktoriserer deterministisk et givet naturligt tal i aritmetiske operationer. Algoritmen blev første gang foreslået af den amerikanske matematiker Sherman Lehman i 1974 [1] . Denne algoritme var den første deterministiske heltalsfaktoriseringsalgoritme med et estimat mindre end . I øjeblikket er det af rent historisk interesse og bruges som regel ikke i praksis. [2] $n$ $O(n^{{1/3}})$ $O({\sqrt {n)))$

Lehmanns metode

Lehmanns metode udvikler ideerne om Fermats faktoriseringsmetode og leder efter divisorer af tallet ved hjælp af lighed for et eller andet heltal . Den er baseret på følgende teorem. [2] $n$ $x^{2}-y^{2}=4kn$ $k$

Udtalelse af sætningen [1]

Antag, at det er et positivt ulige heltal og er et heltal, således at . Hvis , hvor og er enkle og $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}

så er der ikke-negative heltal , og , sådan at $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}}

, hvis ulige,

k

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

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

Hvis er prime, sådanne tal , og eksisterer ikke. $n$ $x$ $y$ $k$

Ændret Lehmanns metode

Udtalelse af sætningen

Lad et sammensat tal, der er produktet af to ulige coprimtal, der opfylder ulighederne . Så er der naturlige tal og sådan noget $n=pq$ ${\displaystyle n^{1/3}<p<q<n^{2/3))$ $x,\;y$ $k\geqslant 1$

1. Ligheden holder for , 2. Uligheden holder . [2] For at bevise denne sætning har vi brug for følgende Lemma.

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

k<n^{1/3}

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

Lemma

Lad sætningens betingelser være opfyldt. Så er der naturlige tal sådan, at og .

[3]

r,\;s

rs<n^{1/3}

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

Bevis for Lemma

Hvis det vil sige , så gælder sætningens påstand for . Dernæst vil vi tælle . $p=q$ $n=p^{2}$ $r=s=1$ $p<q$

Lad os udvide det til en fortsat brøk . Vi betegner th konvergent med k . Derefter ${\frac {q}{p))$ ${\frac {p_{j}}{q_{j}}}$ $j$ ${\frac {q}{p))$

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

fordi . Vi vælger det første tal sådan ${\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))$

Et sådant tal er sikker på at blive fundet, da den sidste passende brøk har en nævner . Lad os bevise det og tilfredsstille lemmaets påstand. Det er åbenlyst . Yderligere, $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}}}$

egenskaber af egnede fraktioner.

Lad os overveje sagen først . I dette tilfælde ${\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.

Overvej nu sagen . Så vender vi ulighederne , hvorfra . Derfor, ved egenskaberne af fortsatte fraktioner, ulighederne ${\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}}}$ . Herfra

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

Lemmaet er bevist. [3]

Bevis for sætningen

Lad og være ulige delere af . Lad og , hvor og tilfredsstille Lemma's udsagn, så gælder ligheden , hvor . Ved Lemma opfylder et heltal uligheden . Følgelig er den første påstand i sætningen opfyldt. $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}$

For at bevise den anden påstand sætter vi , Siden , derefter og . Ved at bruge det øverste estimat for får vi . Hvorfra følger det . Sætningen er blevet bevist. [fire] $z=x-\lgulv {\sqrt {4 mia.}}\rgulv =pr+qs-\lgulv {\sqrt {4 mia.}}\rgulv$ $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$

Algoritme (ændret)

Lad ulige og . $n$ $n>8$

Trin 1. For at kontrollere tilstanden . Hvis det på dette trin ikke var muligt at faktorisere, så gå til trin 2. $a=2,\;3,\;\ldots ,\;\lgulv n^{1/3}\rgulv$ $a\mid n$ $n$

Trin 2. Hvis divisoren i trin 1 ikke findes og er sammensat , så , hvor er primtal , og . Så kontroller for alle og alle , om tallet er kvadratet af et naturligt tal. Hvis det er, sammenlignes der for og : $n$ $n=pq$ $p,\;q$ ${\displaystyle n^{1/3}<p\leqslant q<n^{2/3))$ $k=1,\;2,\;\ldots ,\;\lgulv n^{1/3}\rgulv$ $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=\venstre\lgulv {\sqrt {4kn))\right\rgulv +d$ $B={\sqrt {A^{2}-4kn))$

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

eller .

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

I dette tilfælde kontrolleres uligheden for . Hvis det er opfyldt, så er en faktorisering i to faktorer. $d^{*}=\gcd(AB,\;n)$ $1<d^{*}<n$ $n=d^{*}\cdot (n/d^{*})$ $n$

Hvis algoritmen ikke har fundet en dekomponering i to faktorer, så er det et primtal. [5] $n$ $n$

Denne algoritme kontrollerer først, om den har primdivisorer, der ikke overstiger , og arrangerer derefter en søgning efter værdier og for at kontrollere gennemførligheden af følgende sætning. Hvis de ønskede værdier og ikke findes, får vi, at tallet er primtal. Således kan vi betragte denne algoritme som en test af et tal for enkelhed [6] $n$ $\lfloor n^{1/3}\rfloor$ $k$ $d$ $x$ $y$ $n$ $n$

Møjsommelighed

Beregning af afhængigheden af størrelsen af det faktoriserede tal

Det første trin er at udføre divisionsoperationer for at finde små divisorer af tallet . $\lceil n^{1/3}\rceil$ $n$

Kompleksiteten af det andet trin estimeres i operationerne med at teste tallet for at se, om det er et perfekt kvadrat. Kompleksiteten af den anden fase estimeres ovenfra af værdien $\left(\left\lfloor {\sqrt {4kn))\right\rfloor +d\right)^{2}-4kn$

${\frac {n^{1/6}}{4}}\sum _{k=1}^{\lgulv n^{1/6}\rgulv}{{\frac {1}{\ sqrt {k}}}+2(\lceil n^{1/3}\rceil -\lfloor n^{1/6}\rfloor )}<3\lceil n^{1/3}\rceil$ .
Således er altings kompleksitet værdien . [6] $O(n^{{1/3}})$

Afhængighed af kapaciteten af det faktoriserede tal

I de fleste tilfælde spiller eksekveringstidens afhængighed af bitdybden af det undersøgte nummer en vigtigere rolle. Ved at have en polynomiel afhængighed for værdien får vi en eksponentiel afhængighed af Lehmann-metodens udførelsestid af ordlængden af det faktoriserede tal. [7]

${\displaystyle n\simeq 2^{l))$ , hvor er bitdybden. $l$

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

Nogle særlige tilfælde

Som en forbedring af Fermats metode afhænger Lehmanns metode også væsentligt af afstanden mellem tallets faktorer, dens udførelsestid afhænger lineært af afstanden. Men hvis afstanden mellem faktorerne er lille, taber Lehmann-metoden betydeligt til Fermat-metoden .

For tal med en lille primtalsdivisor er situationen omvendt - Lehmann-metoden vil takket være successive divisioner i trin et hurtigt vælge en primfaktor. [7]

Pseudokode

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

a\vdots n

then return

-en

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\får \lgulv {\sqrt {4kn}}\rgulv +d

B\får {\sqrt {A^{2}-4kn))

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

Forklaringer:

$a\vdots n$ betyder, at det er heltal deleligt med . $n$ $-en$

Funktionen returnerer if er et perfekt kvadrat og andet. $isSquare(a)$ $rigtigt$ $-en$ $falsk$

Funktionen returnerer den største fælles divisor af tal og . [7] $gcd(a,b)$ $-en$ $b$

Muligheder for parallel implementering af metoden

Generel idé

Den parallelle implementering er baseret på følgende tilgang: [7]

Trin 1:
Hver beregningsproces involveret i faktorisering får sit eget sæt af potentielle divisorer fra sættet . Beregningsprocessen kontrollerer skiftevis for delelighed med elementer i dens sæt af divisorer. Med nogle tidsintervaller "stiller hovedkoordinatorprocessen spørgsmålstegn ved beregningsprocesserne for at bestemme divisoren". I det tilfælde, hvor det er nok at kontrollere for enkelhed, sender koordinatorprocessen, efter at have modtaget information om divisorens placering, et signal til resten af processerne om at afslutte arbejdet. Findes divisoren ikke, eller målet er at finde alle divisorer, fortsætter søgningen efter divisorer. ${\displaystyle \{2,\;3,\;4,\;\ldots \lgulv n^{1/3}\rgulv \))$ $n$ $n$

Trin 2:
Hver beregningsproces, i lighed med trin 1, får sit eget sæt tal fra sættet . Beregningsprocessen kontrollerer på skift alle de betingelser, der er beskrevet i algoritmen, og bestemmer, om der findes en ikke-triviel faktor. På samme måde, med trin 1, poller koordinatorprocessen periodisk processerne på tidspunktet for at finde divisoren og beslutter, om beregningerne skal afsluttes eller ej. $k$ ${\displaystyle \{2,\;3,\;4,\;\ldots \lgulv n^{1/3}\rgulv \))$

Anvendelsen af denne tilgang gør det muligt at opnå en lineær acceleration med en stigning i antallet af processer på en maskine med distribueret hukommelse. [7]

Implementering ved hjælp af GPGPU- teknologi

For at implementere en algoritme med succes ved hjælp af GPGPU- teknologi , skal to problemer løses: [8]
1. For hver operation af algoritmen skal du beslutte, om det er værd at udføre den på CPU'en eller på GPU'en .
2. Bestem antallet af brugte GPU- kerner .

Fremgangsmåden beskrevet ovenfor kan bruges til at opdele problemet. [otte]

Trin 1:
Alle handlinger i dette trin skal udføres på GPU'en .

Lad være antallet af tilgængelige GPU- kerner , være antallet af elementer i sættet . Overvej to tilfælde: 1. : Vi bruger GPU- kerner . 2 .: Organiser iterationer . Ved hver iteration udfører vi de næste delinger på kernerne. Ved slutningen af hver iteration bestemmer vi, om vi skal fuldføre eller fortsætte eksekveringen. $ker$ $la$ ${\displaystyle \{2,\;3,\;4,\;\ldots \lgulv n^{1/3}\rgulv \))$
$la\leqslantker$ $la$
$la>ker$ $\left\lceil {\frac {la}{ker}}\right\rceil$ $ker$ $ker$

Trin 2:

Fordel mellem GPU - kerner på samme måde som i trin 1. Udfør trin 1-3 på hver GPU -kerne: 1. Tjek, om tallet er et kvadrat af et naturligt tal. 2. I tilfælde af at opnå et positivt resultat i det foregående afsnit, beregne og . 3. For værdier og tjek tilstanden . 4. For værdierne og , som bestod den sidste kontrol, skal du kontrollere opfyldelsen af den dobbelte betingelse . $k$
$\left(\left\lfloor {\sqrt {4kn))\right\rfloor +d\right)^{2}-4kn$
$A=\venstre\lgulv {\sqrt {4kn))\right\rgulv +d$ $B={\sqrt {A^{2}-4kn))$
$EN$ $B$ $A^{2}\equiv B^{2}{\pmod {n))$
$EN$ $B$ $0<\gcd(A\pm B,\;n)<n$

Det er tilrådeligt at udføre det sidste punkt på CPU'en , da sandsynligheden for at udføre disse operationer er lille, og grenkontrol på GPU'en er ret langsom. [otte]

Eksempel

Lad os analysere eksemplet med , så for , hvor , vi tjekker om tallet er en divisor af tallet . Det er nemt at sikre sig, at der ikke er nogen, så går vi videre til næste afsnit. $n=1387$ $a=1,\;2,\;3,\;\ldots ,\;\lgulv n^{1/3}\rgulv$ $\lfloor n^{1/3}\rfloor =11$ $-en$ $n$

For alle og enhver tjekker vi, om tallet er kvadratet af et naturligt tal. I vores tilfælde er der og sådan, at udtrykket er et perfekt kvadrat og er lig med . Derfor og . Derefter opfylder uligheden og er en divisor af tallet . Som et resultat dekomponerede vi tallet i to faktorer: og . $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$ $1<d^{*}<n$ $n$ $1387$ $73$ $19$

Noter

↑ 1 2 Lehman, R. Sherman. Faktorering af store heltal // Beregningsmatematik. - 1974. - T. 28 , nr. 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. Undersøgelse af parallelle heltalsfaktoriseringsalgoritmer i computerklyngesystemer // Omsk State University. F. M. Dostojevskij (Omsk). - 2012. - V. 4 , nr. 66 . - S. 149-158 .
↑ 1 2 3 Zheltov S. A. Tilpasning af Sherman-Lehman-metoden til løsning af faktoriseringsproblemet til CUDA-computerarkitekturen // Russian State University for the Humanities (Moskva). - 2012. - T. 14 , nr. 94 . - S. 84-91 .

Litteratur

Vasilenko O. N. Talteoretiske algoritmer i kryptografi . - M .: MTSNMO , 2003. - 328 s. — ISBN 5-94057-103-4 . Arkiveret 27. januar 2007 på Wayback Machine
Alexey Nesterenko. En introduktion til moderne kryptografi . - MTSNMO , 2011. - 190 s.
Richard Crandall, Carl Pomerance. A beregningsmæssige perspektiver . — 2. - Springer, 2011. - 597 s. — ISBN 0-387-25282-7 .

Talteoretiske algoritmer
Enkelthedstest	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
At finde primtal	Iteration over divisorer Sigte af Eratosthenes Atkins si Sigte Sundarama
Faktorisering	Iteration over divisorer Fermat metode p −1 Pollard metode Pollards ρ-algoritme Lehmanns metode Elliptisk kurvemetode (Lenstras algoritme) Dixons algoritme Firkantet sigte
Diskret logaritme	Gelfond-Shanks algoritme Polig-Hellman algoritme Pollards ρ-metode Pollards kængurualgoritme Adlemans algoritme COS algoritme
Finder GCD	Euklids algoritme Avanceret algoritme Binær algoritme
Modulo aritmetik	Montgomerys algoritme Kinesisk restsætning
Multiplikation og division af tal	Karatsuba algoritme Toom-Cook algoritme Schönhage-Strassen algoritme Fuhrer algoritme Harvey-van der Hoeven algoritme Burnickel-Ziegler algoritme
Beregning af kvadratroden	Tonelli-Shanks algoritme Berlekamp-Rabin algoritme

Lehmanns metode

Lehmanns metode

Ændret Lehmanns metode

Udtalelse af sætningen

Lemma

Bevis for sætningen

Algoritme (ændret)

Møjsommelighed

Beregning af afhængigheden af ​​størrelsen af ​​det faktoriserede tal

Afhængighed af kapaciteten af ​​det faktoriserede tal

Nogle særlige tilfælde

Pseudokode

Muligheder for parallel implementering af metoden

Generel idé

Implementering ved hjælp af GPGPU- teknologi

Eksempel

Noter

Litteratur

Beregning af afhængigheden af størrelsen af det faktoriserede tal

Afhængighed af kapaciteten af det faktoriserede tal