Ciągła faktoryzacja frakcji

W matematyce , zwłaszcza w teorii liczb , metoda faktoryzacji przez ułamek ciągły (w języku angielskim „ metoda ciągłego rozkładania na czynniki ” , w skrócie cfrac ) jest metodą teorii liczb, która określa dwa dzielniki liczby naturalnej , pod warunkiem, że nie jest to liczba pierwsza . Poprzez wielokrotne stosowanie metody otrzymujemy rozkład na iloczyn czynników pierwszych tej liczby. Metoda jest ogólna w tym sensie, że ma zastosowanie do wszystkich liczb całkowitych, niezależnie od określonego kształtu lub właściwości.

Metoda faktoryzacji przez ułamek ciągły została opublikowana w 1931 roku przez Derricka Henry'ego Lehmera i Ralpha Ernesta Powersa (in) , matematyka-amatora, znanego również z wyników obliczeń w teorii liczb. Został użyty późno, ponieważ maszyny liczące nie były wystarczająco szybkie. W 1975 roku Michael A. Morrison i John Brillhart zaprogramowali metodę na większym komputerze i byli w stanie uzyskać faktoryzację siódmej liczby Fermata . Metoda ciągłego rozkładania na frakcje pozostała standardową metodą rozkładania na czynniki „dużych” liczb całkowitych, które w latach 80. miały do pięćdziesięciu miejsc po przecinku. W 1990 roku nowy algorytm, metoda sita kwadratowego , zastąpił metodę frakcji ciągłej.

Złożoność ciągłego frakcji faktoryzacji liczby całkowitej znajduje się w $NIE$ ${\ Displaystyle O \ lewo (e ^ {\ sqrt {2 \ log N \ log \ log N}} \ po prawej)}$ .

Zasada

Algorytm szuka zgodności postaci

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

Aby to zrobić, mnoży odpowiednie kongruencje formy . Korzystając z tych kongruencji, otrzymujemy faktoryzację N metodą faktoryzacji Dixona . x 2 ≡ y 2 (mod N ). ${\ Displaystyle x ^ {2} \ equiv y {\ bmod {N}}}$

Zastosowania sposobu, dla znalezienia tych kongruencji, w ciągłej ekspansji frakcję o . To rozszerzenie zapewnia najlepsze przybliżenia w postaci ułamków . Każde przybliżenie zapewnia kongruencję poszukiwanej formy , z i . Ponieważ ułamek jest lepszym przybliżeniem , liczba całkowita jest mała iz dużym prawdopodobieństwem jest krucha i potrzeba niewiele takich kongruencji. ${\ sqrt {N}}$ ${\ sqrt {N}}$ $p / q$ ${\ Displaystyle x ^ {2} \ equiv y {\ bmod {N}}}$ ${\ displaystyle x = p}$ ${\ displaystyle y = x ^ {2} -q}$ ${\ sqrt {N}}$ $y$

Elementy historyczne

Pierwszym krokiem w kierunku metody ułamków ciągłych jest metoda faktoryzacji Fermata opisana przez Pierre de Fermata w 1643 roku. Polega ona na znalezieniu dwóch kwadratów i tak dalej . Podobnie jak liczby całkowite, a następnie są dzielnikami . $x ^ 2$ $y ^ 2$ ${\ Displaystyle x ^ {2} -y ^ {2} = N}$ ${\ Displaystyle N = x ^ {2} -y ^ {2} = (x + y) (xy)}$ $x + y$ $xy$ $NIE$

W 1798 roku Adrien-Marie Legendre opublikował swoją książkę Esej o teorii liczb . Opracowano metodę Fermata, w której różnica jest dowolną wielokrotnością ; liczby i muszą spełniać warunki , i . Przy tych założeniach dziel i gcds i są dzielnikami . ${\ Displaystyle x ^ {2} -y ^ {2}}$ $NIE$ $x$ $y$ ${\ Displaystyle 0 <x, y <N}$ $x \ neq y$ ${\ Displaystyle x + y \ neq N}$ $NIE$ ${\ Displaystyle x ^ {2} -y ^ {2} = (x + y) (xy)}$ ${\ displaystyle \ operatorname {pgcd} (N, x + y)}$ ${\ displaystyle \ operatorname {pgcd} (N, xy)}$ $NIE$

Bibliografia

Carl Pomerance , „ Opowieść o dwóch sitach ”, Notices of the AMS , vol. 43 N O 12,Grudzień 1996, s. 1473-1485 ( czytaj online ).

Derrick H. Lehmer i Ralph E. Powers, „ On Factoring Large Numbers ”, Biuletyn Amerykańskiego Towarzystwa Matematycznego , tom. 37 N O 10,1931, s. 770–776 ( DOI 10.1090 / S0002-9904-1931-05271-X ).

Michael A. Morrison i John Brillhart, „ Metoda faktoryzacji i faktoryzacji F 7 ”, Amerykańskie Towarzystwo Matematyczne , tom. 29 N O 129styczeń 1975, s. 183–205 ( DOI 10.2307 / 2005475 , JSTOR 2005475 , czytaj online )

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