Factorizarea fracției continue

În matematică , în special în teoria numerelor , metoda factorizării prin fracție continuă (în limba engleză „ continue fraction factorization method ” , prescurtat cfrac ) este o metodă a teoriei numerelor care determină doi divizori ai unui număr natural , cu condiția să nu fie un număr prim . Prin aplicarea repetată a metodei obținem descompunerea în produs a factorilor primi ai acestui număr. Metoda este generală în sensul că se aplică tuturor numerelor întregi, indiferent de o anumită formă sau proprietăți.

Metoda de factorizare prin fracție continuă a fost publicată în 1931 de Derrick Henry Lehmer și Ralph Ernest Powers (în) , un matematician amator cunoscut și pentru rezultatele sale de calcul în teoria numerelor. A fost folosit doar târziu, deoarece mașinile de calcul nu erau suficient de rapide. În 1975, Michael A. Morrison și John Brillhart au programat metoda pe un computer mai mare și au reușit să obțină factorizarea celui de-al șaptelea număr Fermat . Metoda de factorizare a fracției continue a rămas metoda standard de factorizare a unor numere întregi „mari” care, în anii 1980, aveau până la cincizeci de zecimale. În 1990, un nou algoritm, metoda sitei pătratice a înlocuit metoda fracției continue.

Complexitatea timp a factorizare fracție continuă a unui întreg este în $NU$ ${\ displaystyle O \ left (e ^ {\ sqrt {2 \ log N \ log \ log N}} \ right)}$ .

Principiu

Algoritmul caută o congruență a formei

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

Pentru a face acest lucru, înmulțește congruențe adecvate ale formei . Folosind aceste congruențe, obținem o factorizare a lui N prin metoda factorizării Dixon . x 2 ≡ y 2 (mod N ). ${\ displaystyle x ^ {2} \ equiv y {\ bmod {N}}}$

Metoda folosește, pentru a găsi aceste congruențe, expansiunea continuă a fracției de . Această extindere oferă cele mai bune aproximări ale sub formă de fracții . Fiecare aproximare oferă o congruență a formei căutate , cu și . Deoarece fracția este o aproximare mai bună a , întregul este mic și este, cu o probabilitate ridicată, friabil și sunt necesare astfel de congruențe. ${\ sqrt {N}}$ ${\ sqrt {N}}$ $p / q$ ${\ displaystyle x ^ {2} \ equiv y {\ bmod {N}}}$ ${\ displaystyle x = p}$ ${\ displaystyle y = x ^ {2} -q}$ ${\ sqrt {N}}$ $y$

Elemente istorice

Primul pas către metoda continuării fracțiilor este metoda de factorizare Fermat descrisă de Pierre de Fermat în 1643. Acesta constă în găsirea a două pătrate și astfel încât . La fel , numerele întregi și sunt apoi divizori ai . $x ^ 2$ $y ^ 2$ ${\ displaystyle x ^ {2} -y ^ {2} = N}$ ${\ displaystyle N = x ^ {2} -y ^ {2} = (x + y) (xy)}$ $x + y$ $X y$ $NU$

În 1798, Adrien-Marie Legendre și-a publicat cartea Eseu despre teoria numerelor . Există o dezvoltare a metodei Fermat, în care diferența este un multiplu arbitrar al ; numerele și trebuie să îndeplinească condițiile , și . În conformitate cu aceste ipoteze, divizați și CMD și sunt divizori ai . ${\ displaystyle x ^ {2} -y ^ {2}}$ $NU$ $X$ $y$ ${\ displaystyle 0 <x, y <N}$ $x \ neq y$ ${\ displaystyle x + y \ neq N}$ $NU$ ${\ displaystyle x ^ {2} -y ^ {2} = (x + y) (xy)}$ ${\ displaystyle \ operatorname {pgcd} (N, x + y)}$ ${\ displaystyle \ operatorname {pgcd} (N, xy)}$ $NU$

Bibliografie

Carl Pomerance , „ A Tale of Two Sieves ” , Notices of the AMS , vol. 43, n o 12,Decembrie 1996, p. 1473-1485 ( citește online ).

Derrick H. Lehmer și Ralph E. Powers, „ On Factoring Large Numbers ” , Buletinul American Mathematical Society , vol. 37, n o 10,1931, p. 770–776 ( DOI 10.1090 / S0002-9904-1931-05271-X ).

Michael A. Morrison și John Brillhart, „ A Method of Factoring and the Factorization of F 7 ”, American Mathematical Society , vol. 29, nr . 129,ianuarie 1975, p. 183–205 ( DOI 10.2307 / 2005475 , JSTOR 2005475 , citiți online )

Samuel S. Wagstaff, Jr. , The Joy of Factoring , Providence, RI, American Mathematical Society,2013, 293 p. ( ISBN 978-1-4704-1048-3 , prezentare online )