A matematikában , főleg a számelméletben , a folytonos tört frakcionálásának módszere (angolul: „ folytonos frakció faktorizációs módszer ” , rövidítve cfrac ) a számelmélet olyan módszere, amely meghatározza a természetes szám két osztóját , feltéve, hogy ez nem prímszám . A módszer ismételt alkalmazásával megkapjuk ennek a számnak a prímtényezők szorzatává történő bontását . A módszer általános abban az értelemben, hogy minden egész számra vonatkozik, függetlenül egy adott alaktól vagy tulajdonságoktól.
A folytonos frakcióval történő faktorizálási módszert Derrick Henry Lehmer és Ralph Ernest Powers (in) amatőr matematikus publikálta 1931-ben, a számelméleti számítási eredményeiről is ismert. Csak későn használták, mert a számológépek nem voltak elég gyorsak. 1975-ben Michael A. Morrison és John Brillhart egy nagyobb számítógépen programozták a módszert, és meg tudták szerezni a hetedik Fermat-szám faktorizálását . A folyamatos törtfaktorosítási módszer továbbra is a „nagy” egész számok faktorálásának szokásos módszere maradt, amelyeknek az 1980-as években akár ötven tizedesjegye is volt. 1990-ben egy új algoritmus, a másodfokú szita módszer váltotta fel a folyamatos frakció módszert.
Az idő összetettsége folyamatos frakció faktorizációja egész szám van .
Az algoritmus a forma kongruenciáját keresi
.Ehhez megsokszorozza a forma megfelelő egybevágásait . Ezeknek a kongruenciáknak a felhasználásával kapjuk az N faktorosítását a Dixon-féle faktorizációs módszerrel . x 2 ≡ y 2 (mod N ).
A módszer, hogy megtalálja ezeket congruences, a folyamatos frakció bővülése a . Ez a kiterjesztés biztosítja a legjobb közelítéseket frakciók formájában . Minden közelítés a keresett forma , a és a karakterekkel egybevág . Mivel a tört jobb közelítése , az egész szám kicsi, és nagy valószínűséggel törékeny , és kevés ilyen egybevetésre van szükség.
Az első lépés a folytonos törtek módszere felé a Pierre de Fermat által 1643-ban leírt Fermat-faktorizációs módszer . Két négyzet és olyan négyzet megtalálásából áll . Hasonlóan az egész számokhoz , majd ezek osztói .
1798 - ban Adrien-Marie Legendre kiadta Esszé a számelméletről című könyvét . Fermat módszerét fejlesztették, ahol a különbség tetszőleges többszöröse ; - a számokat és meg kell felelniük a feltételeknek , és - . Ezen feltételezések szerint oszd meg és oszd meg a gcds-t, és ezek osztói .