Kontinuerlig fraktion faktorisering

I matematik , især i talteori , er metoden til faktorisering ved fortsat fraktion (på engelsk " fortsat fraktion faktoriseringsmetode " , forkortet cfrac ) en metode til talteori, der bestemmer to delere af et naturligt tal , forudsat at det ikke er et primtal . Ved gentagen anvendelse af metoden opnår vi nedbrydningen i produkt af primfaktorer af dette tal. Metoden er generel i den forstand, at den gælder for alle heltal, uanset en bestemt form eller egenskaber.

Faktoriseringen metode kædebrøk blev offentliggjort i 1931 af Derrick Henry Lehmer og Ralph Ernest Powers (i) , en amatør matematiker også kendt for sine beregningsresultater i talteori. Det blev kun brugt sent, fordi beregningsmaskinerne ikke var hurtige nok. I 1975 programmerede Michael A. Morrison og John Brillhart metoden på en større computer og var i stand til at opnå faktorisering af det syvende Fermat-nummer . Den kontinuerlige fraktionsfaktoriseringsmetode forblev standardmetoden til faktorisering af "store" heltal, der i løbet af 1980'erne havde op til halvtreds decimaler. I 1990 erstattede en ny algoritme, den kvadratiske sigmetode , den kontinuerlige fraktionsmetode.

Den tid kompleksiteten af kontinuerlig fraktion faktorisering af et heltal er i $IKKE$ ${\ displaystyle O \ left (e ^ {\ sqrt {2 \ log N \ log \ log N}} \ right)}$ .

Princip

Algoritmen ser efter en kongruens af formularen

{\ displaystyle x ^ {2} \ equiv y ^ {2} {\ bmod {N}}}

For at gøre dette multiplicerer det passende kongruenser af formularen . Ved hjælp af disse kongruenser opnår vi en faktorisering af N ved Dixon-faktoriseringsmetoden . x 2 ≡ y 2 (mod N ). ${\ displaystyle x ^ {2} \ equiv y {\ bmod {N}}}$

Metoden bruger, til at finde disse kongruenser, den fortsatte fraktionsudvidelse af . Denne udvidelse giver de bedste tilnærmelser til i form af brøker . Hver tilnærmelse giver en kongruens af den søgte form , med og . Da fraktionen er en bedre tilnærmelse af , er heltalet lille og er med stor sandsynlighed sprød , og der er kun behov for sådanne kongruenser. ${\ sqrt {N}}$ ${\ sqrt {N}}$ $p / q$ ${\ displaystyle x ^ {2} \ equiv y {\ bmod {N}}}$ ${\ displaystyle x = p}$ ${\ displaystyle y = x ^ {2} -q}$ ${\ sqrt {N}}$ $y$

Historiske elementer

Det første skridt mod metoden med fortsatte fraktioner er Fermat-faktoriseringsmetoden beskrevet af Pierre de Fermat i 1643. Den består i at finde to firkanter og sådan, at . Ligesom heltalene og er derefter divisorer af . $x ^ 2$ $y ^ 2$ ${\ displaystyle x ^ {2} -y ^ {2} = N}$ ${\ displaystyle N = x ^ {2} -y ^ {2} = (x + y) (xy)}$ $x + y$ $xy$ $IKKE$

I 1798 udgav Adrien-Marie Legendre sin bog Essay on the theory of numbers . Der er en udvikling af Fermats metode, hvor forskellen er et vilkårligt multiplum af ; numrene og skal opfylde betingelserne , og . Under disse antagelser er division og gcds og delere af . ${\ displaystyle x ^ {2} -y ^ {2}}$ $IKKE$ $x$ $y$ ${\ displaystyle 0 <x, y <N}$ $x \ neq y$ ${\ displaystyle x + y \ neq N}$ $IKKE$ ${\ displaystyle x ^ {2} -y ^ {2} = (x + y) (xy)}$ ${\ displaystyle \ operatorname {pgcd} (N, x + y)}$ ${\ displaystyle \ operatorname {pgcd} (N, xy)}$ $IKKE$

Bibliografi

Carl Pomerance , " A Tale of Two Sieves ", Notices of the AMS , vol. 43, nr . 12,December 1996, s. 1473-1485 ( læs online ).

Derrick H. Lehmer og Ralph E. Powers, " On Factoring Large Numbers ", Bulletin of the American Mathematical Society , bind. 37, nr . 10,1931, s. 770–776 ( DOI 10.1090 / S0002-9904-1931-05271-X ).

Michael A. Morrison og John Brillhart, " A Method of Factoring and the Factorization of F 7 ", American Mathematical Society , bind. 29, nr . 129,januar 1975, s. 183–205 ( DOI 10.2307 / 2005475 , JSTOR 2005475 , læs online )

Samuel S. Wagstaff, Jr. , glæden ved faktorering , Providence, RI, American Mathematical Society,2013, 293 s. ( ISBN 978-1-4704-1048-3 , online præsentation )