A fatoração de curva elíptica de Lenstra ou o método de fatoração de curva elíptica (ECM, do inglês Elliptic-Curve Method) é um algoritmo rápido, com tempo de execução sub-exponencial, para a fatoração de inteiros, que emprega curvas elípticas. Para a fatoração de uso geral, o ECM é o terceiro método de fatoração conhecido mais rápido. O segundo mais rápido é o crivo quadrático de múltiplos polinômios, e o mais rápido é o crivo do corpo de números geral. A fatoração de curva elíptica de Lenstra recebeu o nome em homenagem a Hendrik Lenstra. Trata-se de um algoritmo de fatoração de grupo algébrico.
De um ponto de vista prático, o ECM é considerado um algoritmo de fatoração de propósito específico, pois é o mais adequado para encontrar fatores pequenos. Atualmente, continua a ser o melhor algoritmo para divisores que não excedam 50 a 60 dígitos, dado que o seu tempo de execução é dominado pelo tamanho do menor fator p e não pelo tamanho do número n a ser fatorado. Frequentemente, o ECM é utilizado para extrair fatores pequenos de um inteiro muito grande com muitos fatores; se o inteiro restante continuar a ser composto, então ele possui apenas fatores grandes e é fatorado recorrendo a técnicas de uso geral. O maior fator encontrado utilizando o ECM até à data tem 83 dígitos decimais e foi descoberto a 7 de setembro de 2013 por R. Propper.50 largest factors found by ECM. Aumentar o número de curvas testadas melhora as hipóteses de se encontrar um fator, mas estas não são lineares em relação ao aumento do número de dígitos.
Algoritmo
Contexto
O método de fatoração de curva elíptica de Lenstra utiliza uma curva elíptica módulo n (ou seja, o número a ser fatorado) e multiplica um ponto aleatório P sobre a mesma. A multiplicação baseia-se na multiplicação de pontos da curva elíptica, que, por sua vez, é apenas a adição repetida de pontos da curva elíptica, descrita no artigo sobre curvas elípticas. Esta adição formaria um grupo no caso não modular e no caso em que n é primo, uma vez que (os inteiros módulo ) formam um grupo quando n é primo.
Quando se utilizam números modulares em vez de toda a gama de números inteiros, a adição de dois pontos na mesma curva elíptica envolveria calcular o coeficiente angular modular de uma corda que une e , e, assim, a divisão entre classes de resíduos módulo , efetuada através do algoritmo de Euclides estendido. Em particular, a divisão por algum inclui o cálculo do . Supondo que calculamos um coeficiente angular da forma com , se , o resultado da adição do ponto será , o ponto "no infinito" correspondente à intersecção da linha "vertical" que une com a curva. No entanto, se , a adição do ponto não produzirá um ponto significativo na curva; mas, mais importante ainda, é um fator não trivial de : o que significa que fatorámos o número com sucesso.
Os métodos de multiplicação habituais, como a multiplicação por duplicação, continuam a aplicar-se. A adição sucessiva ingênua não é necessária.
Processo O método de fatoração de curva elíptica de Lenstra para encontrar um fator de um dado número natural funciona da seguinte forma: Escolha uma curva elíptica aleatória sobre (os inteiros módulo ), com uma equação da forma juntamente com um ponto não trivial nela contido. Isto pode ser feito escolhendo primeiro valores aleatórios para , e em seguida definindo para garantir que o ponto se encontra na curva. Conforme discutido acima, definimos a adição e a multiplicação de um ponto na curva. Com repetições suficientes de adições, deveremos conseguir provocar uma falha na adição, encontrando assim um fator. Como resultado, calculamos na curva elíptica (), onde é o produto de muitos números pequenos. k pode ser o produto de números primos pequenos elevados a potências pequenas, como no algoritmo p-1, ou o fatorial para algum não muito grande. Isto pode ser efetuado de forma eficiente, processando um fator pequeno de cada vez. Digamos, para obter , primeiro calcula-se , depois , de seguida , e assim sucessivamente. é escolhido para ser pequeno o suficiente para que a adição pontual vezes possa ser executada num tempo razoável. Verifique o resultado da adição. Se concluirmos todos os cálculos acima sem encontrar elementos não invertíveis (), isso significa que a ordem da curva elíptica (módulo primos) não é suficientemente suave, pelo que precisamos tentar novamente com uma curva e ponto de partida diferentes. Se encontrarmos um , concluímos o processo: este é um fator não trivial de .
A complexidade de tempo depende do tamanho do menor fator primo do número e pode ser representada por , onde p é o menor fator de n, ou , na Notação L.
Explicação
Se p e q forem dois divisores primos de n, então implica que a mesma equação também é válida e Estas duas curvas elípticas mais pequenas com a adição são agora grupos genuínos. Se estes grupos tiverem Np e Nq elementos, respetivamente, então para qualquer ponto P na curva original, pelo teorema de Lagrange, ser o menor valor tal que na curva módulo p implica que k divide Np; além disso, . Uma afirmação análoga é válida para a curva módulo q. Quando a curva elíptica é escolhida de forma aleatória, então Np e Nq são números aleatórios próximos de e respetivamente (ver abaixo). Logo, é improvável que a maioria dos fatores primos de Np e Nq sejam os mesmos, e é bastante provável que, ao calcular eP, encontremos algum kP que seja ∞ mas não ou vice-versa. Quando isto acontece, kP não existe na curva original e, nos cálculos, descobrimos algum v cujo ou mas não ambos. Isto é, o forneceu um fator não trivial
O ECM é, na sua essência, uma melhoria do mais antigo algoritmo . O algoritmo encontra fatores primos p tais que é suave em potências b (b-powersmooth) para pequenos valores de b. Para qualquer e, que seja múltiplo de e qualquer a relativamente primo a p, pelo Pequeno teorema de Fermat temos . Em seguida, o tem grande probabilidade de produzir um fator de n. Contudo, o algoritmo falha quando tem grandes fatores primos, como é o caso para números que contêm primos fortes, por exemplo.
O ECM contorna este obstáculo considerando o grupo de uma curva elíptica aleatória sobre o corpo finito Zp, em vez de considerar o grupo multiplicativo de Zp, o qual tem sempre ordem
A ordem do grupo de uma curva elíptica sobre Zp varia (bastante aleatoriamente) entre e pelo teorema de Hasse, e é provável que seja suave para algumas curvas elípticas. Apesar de não existir prova de que se encontre uma ordem de grupo suave no intervalo de Hasse, utilizando métodos probabilísticos heurísticos, o Teorema de Canfield-Erdős-Pomerance com parâmetros adequadamente otimizados e a Notação L, podemos prever a necessidade de testar curvas antes de obtermos uma ordem de grupo suave. Esta estimativa heurística é muito fiável na prática.
Exemplo de uso
O exemplo que se segue provém de , com alguns detalhes acrescentados.
Queremos fatorar . Vamos escolher a curva elíptica , com o ponto pertencente a ela, e vamos tentar calcular o ponto .
O coeficiente angular da linha tangente em algum ponto na curva é . Utilizando , podemos calcular o ponto . Se o valor de não existir, como consequência de não possuir um inverso modular, então constitui um fator não trivial de .
Primeiro, calculamos . Utilizando a duplicação de ponto, temos , logo as coordenadas do ponto são
obtendo-se o ponto .
A seguir, calculamos . Temos . Como , o inverso modular de 106 existe. Utilizando o algoritmo de Euclides estendido, podemos obter que .
Sendo assim, podemos calcular as coordenadas de , tal como fizemos acima. As coordenadas do ponto são
Isto gera .
Depois disto, podemos calcular através da adição de ponto. A linha que une e tem o coeficiente angular , portanto as coordenadas de são
resultando no ponto .
Podemos, da mesma forma, calcular os pontos , , e assim por diante, mas calcular requer inverter , o que não é possível, visto que . Sendo assim, 599 é um divisor de 455839. Após uma rápida divisão, temos .
A razão pela qual isto funciona é que a curva tem pontos, ao passo que a tem pontos. Ademais, 640 e 777 são os menores inteiros positivos k tais que na curva e respetivamente. Visto que é um múltiplo de 640 mas não é um múltiplo de 777, temos na curva mas não na curva daí a adição repetida ter falhado aqui, providenciando a fatoração.
O algoritmo, com coordenadas projetivas
Antes de considerar o plano projetivo sobre , considere primeiro um espaço projetivo 'normal' sobre : Em vez de pontos, estudam-se as linhas que passam pela origem. Uma linha pode ser representada como um ponto não nulo , sob uma relação de equivalência ~ dada por: ⇔ ∃ c ≠ 0 tal que x' = cx, y' = cy e z' = cz. Sob esta relação de equivalência, o espaço é designado como o plano projetivo ; os pontos, representados por , correspondem a linhas num espaço tridimensional que passam pela origem. Note-se que o ponto não existe neste espaço, pois para desenhar uma linha em qualquer direção possível é necessário que pelo menos um entre x', y' ou z' seja ≠ 0. Agora observe-se que quase todas as linhas atravessam um determinado plano de referência - tal como o plano (X,Y,1) - ao passo que as linhas precisamente paralelas a este plano, possuindo coordenadas (X,Y,0), especificam direções de forma unívoca, como 'pontos no infinito' que são utilizados no plano afim (X,Y) sobre o qual se situam.
A coordenada corresponde a no espaço afim. HAL
No algoritmo, apenas é utilizada a estrutura de grupo de uma curva elíptica sobre o corpo . Dado que não precisamos necessariamente do corpo , um corpo finito também proporcionará uma estrutura de grupo numa curva elíptica. Contudo, considerar a mesma curva e operação sobre com não sendo um número primo não forma um grupo. O Método da Curva Elíptica tira proveito dos casos de falha da lei da adição.
Enunciamos agora o algoritmo em coordenadas projetivas. O elemento neutro é então dado pelo ponto no infinito . Seja um inteiro (positivo) a fatorar e considere-se a curva elíptica (um conjunto de pontos com alguma estrutura) .
Escolha com ≠ 0. Calcule . A curva elíptica fica, portanto, na forma de Weierstrass, dada por e, ao recorrer a coordenadas projetivas, a curva elíptica é dada pela equação homogênea . Possui o ponto . Selecione um limite superior para esta curva elíptica. Observação: Apenas se encontrarão fatores se a ordem do grupo da curva elíptica sobre (denotada por ) for B-suave, o que significa que todos os fatores primos de têm de ser menores ou iguais a . Calcule . Calcule (a multiplicação é uma adição repetida) no anel . Se o cálculo retornar com sucesso , tal significa que não é -suave ou que é primo. Retorne ao passo 2 para escolher outra curva. Se o cálculo falhar em algum ponto, isso significa que um divisor não trivial pode ser encontrado. Ele pode falhar porque a adição e a multiplicação não estão bem definidas caso não seja primo, mas isso apenas ocorre quando se tenta inverter um resíduo particular . Neste cenário, o fator é encontrado como de forma igual à descrita acima.
No ponto 5 é dito que, sob as circunstâncias adequadas, pode ser encontrado um divisor não trivial. Como assinalado no artigo de Lenstra (Factoring Integers with Elliptic Curves), a adição exige a suposição de . Se não forem e forem distintos (caso contrário, a adição funciona de forma semelhante, mas com pequenas diferenças), então a adição decorre do seguinte modo:
Para calcular: , , , , .
Se a adição falhar, tal dever-se-á a uma falha no cálculo de Especificamente, porque nem sempre pode ser calculado se não for primo (e, por isso, não é um corpo). Sem assumir que é um corpo, poderia calcular-se:
, , , , e simplificar se possível.
Este cálculo é sempre admissível e, caso o mdc da coordenada com ≠ (1 ou ), a simplificação falha, encontrando-se um divisor não trivial de .
Variante de duas fases