Fatoração de fração contínua

Em matemática , especialmente na teoria dos números , o método de fatoração por fração contínua (em inglês " método de fatoração de fração contínua " , abreviado cfrac ) é um método da teoria dos números que determina dois divisores de um número natural , desde que não seja um número primo . Pela aplicação repetida do método, obtemos a decomposição em produto de fatores primos desse número. O método é geral no sentido de que se aplica a todos os inteiros, independentemente de uma forma ou propriedades específicas.

O método de fatoração por fração contínua foi publicado em 1931 por Derrick Henry Lehmer e Ralph Ernest Powers (in) , um matemático amador também conhecido por seus resultados de cálculo na teoria dos números. Só foi usado tarde porque as máquinas de calcular não eram rápidas o suficiente. Em 1975, Michael A. Morrison e John Brillhart programaram o método em um computador maior e foram capazes de obter a fatoração do sétimo número de Fermat . O método de fatoração de fração contínua continuou sendo o método padrão de fatoração de inteiros “grandes” que, durante a década de 1980, tinham até cinquenta casas decimais. Em 1990, um novo algoritmo, o método da peneira quadrática , substituiu o método da fração contínua.

A complexidade de tempo da fatoração de fração contínua de um inteiro está em $NÃO$ ${\ displaystyle O \ left (e ^ {\ sqrt {2 \ log N \ log \ log N}} \ right)}$ .

Princípio

O algoritmo procura uma congruência da forma

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

Para fazer isso, ele multiplica as congruências apropriadas do formulário . Usando essas congruências, obtemos uma fatoração de N pelo método de fatoração de Dixon . x 2 ≡ y 2 (mod N ). ${\ displaystyle x ^ {2} \ equiv y {\ bmod {N}}}$

O método usa, para encontrar essas congruências, a expansão contínua da fração de . Esta expansão fornece as melhores aproximações na forma de frações . Cada aproximação fornece uma congruência da forma procurada , com e . Como a fração é uma aproximação melhor de , o inteiro é pequeno e é, com alta probabilidade, friável , e poucas congruências desse tipo são necessárias. ${\ sqrt {N}}$ ${\ sqrt {N}}$ $p / q$ ${\ displaystyle x ^ {2} \ equiv y {\ bmod {N}}}$ ${\ displaystyle x = p}$ ${\ displaystyle y = x ^ {2} -q}$ ${\ sqrt {N}}$ $y$

Elementos históricos

O primeiro passo para o método das frações contínuas é o método de fatoração de Fermat descrito por Pierre de Fermat em 1643. Consiste em encontrar dois quadrados e tal . Por exemplo , os inteiros e são divisores de . $x ^ 2$ $y ^ 2$ ${\ displaystyle x ^ {2} -y ^ {2} = N}$ ${\ displaystyle N = x ^ {2} -y ^ {2} = (x + y) (xy)}$ $x + y$ $xy$ $NÃO$

Em 1798, Adrien-Marie Legendre publicou seu livro Ensaio sobre a teoria dos números . Há um desenvolvimento do método de Fermat, onde a diferença é um múltiplo arbitrário de ; os números e devem satisfazer as condições , e . Sob essas premissas, divide e gcds e são divisores de . ${\ displaystyle x ^ {2} -y ^ {2}}$ $NÃO$ $x$ $y$ ${\ displaystyle 0 <x, y <N}$ $x \ neq y$ ${\ displaystyle x + y \ neq N}$ $NÃO$ ${\ displaystyle x ^ {2} -y ^ {2} = (x + y) (xy)}$ ${\ displaystyle \ operatorname {pgcd} (N, x + y)}$ ${\ displaystyle \ operatorname {pgcd} (N, xy)}$ $NÃO$

Bibliografia

Carl Pomerance , " A Tale of Two Sieves " , Notices of the AMS , vol. 43, n o 12,Dezembro de 1996, p. 1473-1485 ( ler online ).

Derrick H. Lehmer e Ralph E. Powers, “ On Factoring Large Numbers, ” Bulletin of the American Mathematical Society , vol. 37, n o 10,1931, p. 770-776 ( DOI 10.1090 / S0002-9904-1931-05271-X ).

Michael A. Morrison e John Brillhart, " Um Método de Factoring e a Factorização de F 7 ", American Mathematical Society , vol. 29, n o 129,janeiro de 1975, p. 183–205 ( DOI 10.2307 / 2005475 , JSTOR 2005475 , leia online )

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