Kontinuerlig brøkfaktorisering

I matematikk , spesielt i tallteori , er metoden for faktorisering av fortsatt brøkdel (på engelsk " fortsatt brøkdelingsfaktorisering metode " , forkortet cfrac ) en metode for tallteori som bestemmer to deler av et naturlig tall , forutsatt at det ikke er et primtall . Ved gjentatt anvendelse av metoden får vi nedbrytning til produkt av primfaktorer av dette tallet. Metoden er generell i den forstand at den gjelder alle heltall, uavhengig av en bestemt form eller egenskaper.

Faktoriseringsmetoden ved fortsatt fraksjon ble publisert i 1931 av Derrick Henry Lehmer og Ralph Ernest Powers (in) , en amatørmatematiker som også er kjent for sine beregningsresultater i tallteori. Den ble bare brukt sent fordi beregningsmaskinene ikke var raske nok. I 1975 programmerte Michael A. Morrison og John Brillhart metoden på en større datamaskin og klarte å oppnå faktorisering av det syvende Fermat-nummeret . Den kontinuerlige fraksjonsfaktoriseringsmetoden forble standardmetoden for å ta i betraktning “store” heltall som i løpet av 1980-årene hadde opptil femti desimaler. I 1990 erstattet en ny algoritme, den kvadratiske silmetoden den kontinuerlige brøkmetoden.

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

Prinsipp

Algoritmen ser etter en kongruens av skjemaet

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

For å gjøre dette multipliserer det passende kongruenser av skjemaet . Ved å bruke disse kongruensene får vi en faktorisering av N ved Dixon-faktoriseringsmetoden . x 2 ≡ y 2 (mod N ). ${\ displaystyle x ^ {2} \ equiv y {\ bmod {N}}}$

Metoden bruker, for å finne disse kongruensene, den fortsatte brøkekspansjonen av . Denne utvidelsen gir de beste tilnærmingene i form av brøker . Hver tilnærming gir en kongruens av den søkte formen , med og . Siden brøken er en bedre tilnærming til , er heltallet lite og er med stor sannsynlighet sprø , og det er lite slike kongruenser som trengs. ${\ 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 trinnet mot metoden for fortsatte fraksjoner er Fermat-faktoriseringsmetoden beskrevet av Pierre de Fermat i 1643. Den består i å finne to firkanter og slik at . Som , heltallene og er da delere av . $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 ga Adrien-Marie Legendre ut boka Essay on the theory of numbers . Det er en utvikling av Fermats metode, der forskjellen er et vilkårlig multiplum av ; tallene og må tilfredsstille vilkårene , og . Under disse forutsetningene, del og gcds og er delere av . ${\ 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, n o 12Desember 1996, s. 1473-1485 ( les online ).

Derrick H. Lehmer og Ralph E. Powers, “ On Factoring Large Numbers, ” Bulletin of the American Mathematical Society , vol. 37, n o 101931, 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 , vol. 29, nr . 129,januar 1975, s. 183–205 ( DOI 10.2307 / 2005475 , JSTOR 2005475 , les online )

Samuel S. Wagstaff, Jr. , gleden ved faktorisering , Providence, RI, American Mathematical Society,2013, 293 s. ( ISBN 978-1-4704-1048-3 , online presentasjon )