Kontinuální faktorizace zlomků

V matematiky , zejména v teorii čísel , metoda faktorizace pokračující frakce (v angličtině „ pokračoval frakce metoda faktorizace “ , zkráceně cfrac ) je metoda teorie čísel, která určuje dva dělitele z a přirozené číslo , za předpokladu, že není prvočíslo . Opakovanou aplikací metody získáme rozklad na součin prvočísel tohoto čísla. Metoda je obecná v tom smyslu, že platí pro všechna celá čísla bez ohledu na konkrétní tvar nebo vlastnosti.

Způsob faktorizace pokračující frakce byla zveřejněna v roce 1931 Derrick Henry Lehmer a Ralph Ernest působností (v) , amatérské matematik také známé pro své výsledky výpočtů v teorii čísel. Bylo použito až pozdě, protože počítací stroje nebyly dostatečně rychlé. V roce 1975 Michael A. Morrison a John Brillhart naprogramovali metodu na větším počítači a dokázali získat faktorizaci sedmého Fermatova čísla . Metoda factorizace spojitých zlomků zůstala standardní metodou factoringu „velkých“ celých čísel, která měla během 80. let až padesát desetinných míst. V roce 1990 nahradil metodu kvadratického síta metodu spojitého zlomku nový algoritmus .

Časová složitost kontinuálního frakce faktorizace celé číslo je v $NE$ ${\ displaystyle O \ left (e ^ {\ sqrt {2 \ log N \ log \ log N}} \ right)}$ .

Zásada

Algoritmus hledá shodu formy

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

K tomu znásobí příslušnou kongruenci formy . Pomocí těchto kongruencí získáme faktorizaci N metodou Dixonovy faktorizace . x 2 ≡ y 2 (mod N ). ${\ displaystyle x ^ {2} \ equiv y {\ bmod {N}}}$

Metoda používá, najít tyto kongruence, na pokračující frakce expanzi ve . Tato expanze poskytuje nejlepší aproximace ve formě zlomků . Každá aproximace poskytuje shodu hledané formy s a . Vzhledem k tomu, že zlomek je lepší aproximací , je celé číslo malé a je s vysokou pravděpodobností drobivé a je zapotřebí jen málo takových shod. ${\ sqrt {N}}$ ${\ sqrt {N}}$ $p / q$ ${\ displaystyle x ^ {2} \ equiv y {\ bmod {N}}}$ ${\ displaystyle x = p}$ ${\ displaystyle y = x ^ {2} -q}$ ${\ sqrt {N}}$ $y$

Historické prvky

Prvním krokem k metodě spojitých zlomků je Fermatova faktorizační metoda, kterou popsal Pierre de Fermat v roce 1643. Skládá se z nalezení dvou čtverců a podobných . Stejně jako celá čísla a poté jsou děliteli . $x ^ 2$ $y ^ 2$ ${\ displaystyle x ^ {2} -y ^ {2} = N}$ ${\ displaystyle N = x ^ {2} -y ^ {2} = (x + y) (xy)}$ $x + y$ $xy$ $NE$

V roce 1798 vydal Adrien-Marie Legendre knihu Esej o teorii čísel . Existuje vývoj Fermatovy metody, kde rozdíl je libovolný násobek ; čísla a musí splňovat podmínky , a . Za těchto předpokladů rozděl a gcds a jsou děliteli . ${\ displaystyle x ^ {2} -y ^ {2}}$ $NE$ $X$ $y$ ${\ displaystyle 0 <x, y <N}$ $x \ neq y$ ${\ displaystyle x + y \ neq N}$ $NE$ ${\ displaystyle x ^ {2} -y ^ {2} = (x + y) (xy)}$ ${\ displaystyle \ operatorname {pgcd} (N, x + y)}$ ${\ displaystyle \ operatorname {pgcd} (N, xy)}$ $NE$

Bibliografie

Carl Pomerance , „ Příběh dvou sít “, sdělení AMS , sv. 43, N O 12Prosince 1996, str. 1473-1485 ( číst online ).

Derrick H. Lehmer a Ralph E. Powers, „ On Factoring Large Numbers “, Bulletin of American Mathematical Society , sv. 37, n o 10,1931, str. 770–776 ( DOI 10.1090 / S0002-9904-1931-05271-X ).

Michael A. Morrison a John Brillhart, „ Metoda factoringu a faktorizace F 7 “, American Mathematical Society , sv. 29, n o 129,ledna 1975, str. 183–205 ( DOI 10.2307 / 2005475 , JSTOR 2005475 , číst online )

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