Jatkuva murto-jako

On matematiikka , erityisesti numero teoriassa , menetelmää tekijöihinjakoalgoritmi jatkuvalla osa (in Englanti " ketjumurtoluku tekijöihinjakoalgoritmi menetelmä " , lyhennettynä cfrac ) on menetelmä numero teoria, joka määrittää kaksi jakajia on luonnollinen luku , edellyttäen, että se ei ole alkuluku . Toistamalla menetelmää saadaan hajoaminen tämän luvun alkutekijöiden tuloksi . Menetelmä on yleinen siinä mielessä, että sitä sovelletaan kaikkiin kokonaislukuihin tietystä muodosta tai ominaisuuksista riippumatta.

Faktointimenetelmän jatkuvalla jakeella julkaisivat vuonna 1931 Derrick Henry Lehmer ja Ralph Ernest Powers (vuonna) , amatööri matemaatikko, joka tunnetaan myös laskentatuloksistaan lukuteoriassa. Sitä käytettiin vasta myöhään, koska laskukoneet eivät olleet riittävän nopeita. Vuonna 1975 Michael A. Morrison ja John Brillhart ohjelmoivat menetelmän suuremmalle tietokoneelle ja pystyivät saamaan seitsemännen Fermat-luvun tekijät . Jatkuva jakokerroinmenetelmä pysyi vakiomenetelmänä "suurten" kokonaislukujen laskemisessa, joilla oli 1980-luvulla enintään viisikymmentä desimaalia. Vuonna 1990 uusi algoritmi, toisen asteen seulamenetelmä , korvasi jatkuvan jakeen menetelmän.

Kokonaisluvun jatkuvan jakokertoimen aikakompleksi on $EI$ ${\ displaystyle O \ left (e ^ {\ sqrt {2 \ log N \ log \ log N}} \ right)}$ .

Periaate

Algoritmi etsii muodon yhteneväisyyttä

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

Tätä varten se kertoo lomakkeen asianmukaiset yhtymäkohdat . Näitä kongruensseja käyttämällä saadaan N: n kerroin Dixonin faktorointimenetelmällä . x 2 ≡ y 2 (mod N ). ${\ displaystyle x ^ {2} \ equiv y {\ bmod {N}}}$

Menetelmän käytöt, löytää näitä congruences, jatkuva osa laajeneminen on . Tämä laajeneminen tarjoaa parhaat likiarvot fraktioiden muodossa . Kukin approksimaatio antaa kongruenssi etsityn muodon , jossa ja . Koska murtoluku on parempi approksimaatio , kokonaisluku on pieni ja on suurella todennäköisyydellä mureneva , ja tällaisia yhtäläisyyksiä tarvitaan vähän. ${\ sqrt {N}}$ ${\ sqrt {N}}$ $p / q$ ${\ displaystyle x ^ {2} \ equiv y {\ bmod {N}}}$ ${\ displaystyle x = p}$ ${\ displaystyle y = x ^ {2} -q}$ ${\ sqrt {N}}$ $y$

Historialliset elementit

Ensimmäinen askel kohti menetelmä ketjumurtoluku on Fermat'n tekijöihinjakoalgoritmi menetelmä on kuvattu julkaisussa Pierre de Fermat vuonna 1643. Se on löytää kaksi ruutua ja siten, että . Kuten kokonaisluvut ja ovat sitten jakajia . $x ^ 2$ $y ^ 2$ ${\ displaystyle x ^ {2} -y ^ {2} = N}$ ${\ displaystyle N = x ^ {2} -y ^ {2} = (x + y) (xy)}$ $x + y$ $xy$ $EI$

Vuonna 1798 Adrien-Marie Legendre julkaisi kirjansa Essee numeroteoriasta . Fermat-menetelmää on kehitetty, jossa ero on mielivaltainen moninkertainen ; - numerot ja niiden on täytettävä ehdot , ja - . Näiden oletusten mukaan jaa ja gcds ja ovat jakajia . ${\ displaystyle x ^ {2} -y ^ {2}}$ $EI$ $x$ $y$ ${\ displaystyle 0 <x, y <N}$ $x \ neq y$ ${\ displaystyle x + y \ neq N}$ $EI$ ${\ displaystyle x ^ {2} -y ^ {2} = (x + y) (xy)}$ ${\ displaystyle \ operaattorin nimi {pgcd} (N, x + y)}$ ${\ displaystyle \ operaattorin nimi {pgcd} (N, xy)}$ $EI$

Bibliografia

Carl Pomerance , " Tarina kahdesta seulasta ", Ilmoitukset AMS: stä , voi. 43, n ° 12,Joulukuu 1996, s. 1473-1485 ( lue verkossa ).

Derrick H. Lehmer ja Ralph E. Powers, ” Suurten lukujen huomioon ottamisesta ”, Bulletin of the American Mathematical Society , voi. 37, n ° 10,1931, s. 770–776 ( DOI 10.1090 / S0002-9904-1931-05271-X ).

Michael A. Morrison ja John Brillhart, " A Factoring and Factorization of F 7 ", American Mathematical Society , voi. 29, n ° 129,tammikuu 1975, s. 183–205 ( DOI 10.2307 / 2005475 , JSTOR 2005475 , lue verkossa )

Samuel S.Wagstaff, Jr. , Faktoringin ilo , Providence, RI, American Mathematical Society,2013, 293 Sivumäärä ( ISBN 978-1-4704-1048-3 , online-esitys )