Fatoração de curva elíptica de Lenstra 📖 Wikipedia

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.^[1] 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.

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 ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ (os inteiros módulo ${\displaystyle n}$) 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 ${\displaystyle P}$ e ${\displaystyle Q}$, e, assim, a divisão entre classes de resíduos módulo ${\displaystyle n}$, efetuada através do algoritmo de Euclides estendido. Em particular, a divisão por algum ${\displaystyle v{\bmod {n}}}$ inclui o cálculo do ${\displaystyle \mathrm {mdc} (v,n)}$. Supondo que calculamos um coeficiente angular da forma ${\displaystyle u/v}$ com ${\displaystyle \mathrm {mdc} (u,v)=1}$, se ${\displaystyle v=0{\bmod {n}}}$, o resultado da adição do ponto será ${\displaystyle \infty }$, o ponto "no infinito" correspondente à intersecção da linha "vertical" que une ${\displaystyle P(x,y),P'(x,-y)}$ com a curva. No entanto, se ${\displaystyle \mathrm {mdc} (v,n)\neq 1,n}$, a adição do ponto não produzirá um ponto significativo na curva; mas, mais importante ainda, ${\displaystyle \mathrm {mdc} (v,n)}$ é um fator não trivial de ${\displaystyle n}$: 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.

O método de fatoração de curva elíptica de Lenstra para encontrar um fator de um dado número natural ${\displaystyle n}$ funciona da seguinte forma:

1. Escolha uma curva elíptica aleatória sobre ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ (os inteiros módulo ${\displaystyle n}$), com uma equação da forma ${\displaystyle y^{2}=x^{3}+ax+b{\pmod {n}}}$ juntamente com um ponto não trivial ${\displaystyle P(x_{0},y_{0})}$ nela contido.

   Isto pode ser feito escolhendo primeiro valores aleatórios para ${\displaystyle x_{0},y_{0},a\in \mathbb {Z} /n\mathbb {Z} }$, e em seguida definindo ${\displaystyle b=y_{0}^{2}-x_{0}^{3}-ax_{0}{\pmod {n}}}$ para garantir que o ponto se encontra na curva.

2. 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 ${\displaystyle [k]P}$ na curva elíptica (${\displaystyle {\bmod {n}}}$), onde ${\displaystyle k}$ é 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 ${\displaystyle B!}$ para algum ${\displaystyle B}$ não muito grande. Isto pode ser efetuado de forma eficiente, processando um fator pequeno de cada vez. Digamos, para obter ${\displaystyle [B!]P}$, primeiro calcula-se ${\displaystyle [2]P}$, depois ${\displaystyle [3]([2]P)}$, de seguida ${\displaystyle [4]([3!]P)}$, e assim sucessivamente. ${\displaystyle B}$ é escolhido para ser pequeno o suficiente para que a adição pontual ${\displaystyle B}$ vezes possa ser executada num tempo razoável.
3. Verifique o resultado da adição.
   • Se concluirmos todos os cálculos acima sem encontrar elementos não invertíveis (${\displaystyle {\bmod {n}}}$), 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 ${\displaystyle p=\mathrm {mdc} (v,n)\neq 1}$, concluímos o processo: este é um fator não trivial de ${\displaystyle n}$.

A complexidade de tempo depende do tamanho do menor fator primo do número e pode ser representada por exp[(√2 + o(1)) √ln p ln ln p], onde p é o menor fator de n, ou ${\displaystyle L_{p}\left[{\frac {1}{2}},{\sqrt {2}}\right]}$, na Notação L.

Se p e q forem dois divisores primos de n, então y² = x³ + ax + b (mod n) implica que a mesma equação também é válida módulo p e módulo q. Estas duas curvas elípticas mais pequenas com a adição ${\displaystyle \boxplus }$ são agora grupos genuínos. Se estes grupos tiverem N_p e N_q elementos, respetivamente, então para qualquer ponto P na curva original, pelo teorema de Lagrange, k > 0 ser o menor valor tal que ${\displaystyle kP=\infty }$ na curva módulo p implica que k divide N_p; além disso, ${\displaystyle N_{p}P=\infty }$. 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 N_p e N_q são números aleatórios próximos de p + 1 e q + 1, respetivamente (ver abaixo). Logo, é improvável que a maioria dos fatores primos de N_p e N_q sejam os mesmos, e é bastante provável que, ao calcular eP, encontremos algum kP que seja ∞ módulo p mas não módulo q, ou vice-versa. Quando isto acontece, kP não existe na curva original e, nos cálculos, descobrimos algum v cujo mdc(v,p) = p ou mdc(v, q) = q, mas não ambos. Isto é, o mdc(v, n) forneceu um fator não trivial de n.

O ECM é, na sua essência, uma melhoria do mais antigo algoritmo p − 1. O algoritmo p − 1 encontra fatores primos p tais que p − 1 é suave em potências b (b-powersmooth) para pequenos valores de b. Para qualquer e, que seja múltiplo de p − 1, e qualquer a relativamente primo a p, pelo Pequeno teorema de Fermat temos a^e ≡ 1 (mod p). Em seguida, o mdc(a^e − 1, n) tem grande probabilidade de produzir um fator de n. Contudo, o algoritmo falha quando p − 1 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 Z_p, em vez de considerar o grupo multiplicativo de Z_p, o qual tem sempre ordem p − 1.

A ordem do grupo de uma curva elíptica sobre Z_p varia (bastante aleatoriamente) entre p + 1 − 2√p e p + 1 + 2√p 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 L[√2/2, √2] curvas antes de obtermos uma ordem de grupo suave. Esta estimativa heurística é muito fiável na prática.

O exemplo que se segue provém de Trappe & Washington (2006), com alguns detalhes acrescentados.

Queremos fatorar ${\displaystyle n=455839}$. Vamos escolher a curva elíptica ${\displaystyle y^{2}=x^{3}+5x-5}$, com o ponto ${\displaystyle P=(1,1)}$ pertencente a ela, e vamos tentar calcular o ponto ${\displaystyle (10!)P}$.

O coeficiente angular da linha tangente em algum ponto ${\displaystyle A=(x,y)}$ na curva é ${\displaystyle \lambda ={\frac {3x^{2}+5}{2y}}\ (\mathrm {mod} \ n)}$. Utilizando ${\displaystyle \lambda }$, podemos calcular o ponto ${\displaystyle 2A}$. Se o valor de ${\displaystyle \lambda }$ não existir, como consequência de ${\displaystyle y}$ não possuir um inverso modular, então ${\displaystyle \mathrm {mdc} (n,y)}$ constitui um fator não trivial de ${\displaystyle n}$.

Primeiro, calculamos ${\displaystyle 2!P}$. Utilizando a duplicação de ponto, temos ${\displaystyle \lambda (P)=\lambda (1,1)=4}$, logo as coordenadas do ponto ${\displaystyle 2P=(x',y')}$ são

${\displaystyle x'=4^{2}-2(1)=14}$

${\displaystyle y'=4(1-14)-1=-53}$

obtendo-se o ponto ${\displaystyle 2P=(14,-53)}$.

A seguir, calculamos ${\displaystyle 3!P}$. Temos ${\displaystyle \lambda (2P)=\lambda (14,-53)=-593/106\ (\mathrm {mod} \ n)}$. Como ${\displaystyle \mathrm {mdc} (106,455839)=1}$, o inverso modular de 106 existe. Utilizando o algoritmo de Euclides estendido, podemos obter que ${\displaystyle \lambda =-593/106=322522\ (\mathrm {mod} \ 455839)}$.

Sendo assim, podemos calcular as coordenadas de ${\displaystyle 2(2P)}$, tal como fizemos acima. As coordenadas do ponto ${\displaystyle 4P=(x',y')}$ são

${\displaystyle x'=322522^{2}-2(14)=259851{\pmod {455839}}}$

${\displaystyle y'=322522(14-259851)-(-53)=116255{\pmod {455839}}}$

Isto gera ${\displaystyle 4P=(259851,116255)}$.

Depois disto, podemos calcular ${\displaystyle 3(2P)=4P+2P}$ através da adição de ponto. A linha que une ${\displaystyle 4P}$ e ${\displaystyle 2P}$ tem o coeficiente angular ${\displaystyle \lambda =116308/259837=206097\ (\mathrm {mod} \ n)}$, portanto as coordenadas de ${\displaystyle 6P=(x',y')}$ são

${\displaystyle x'=206097^{2}-14-259851=179685{\pmod {455839}}}$

${\displaystyle y'=206097(14-179685)-(-53)=427131{\pmod {455839}}}$

resultando no ponto ${\displaystyle 6P=(179685,427131)}$.

Podemos, da mesma forma, calcular os pontos ${\displaystyle 4!P}$, ${\displaystyle 5!P}$, e assim por diante, mas calcular ${\displaystyle 8!P}$ requer inverter 599 (mod 455839), o que não é possível, visto que ${\displaystyle \mathrm {mdc} (599,455839)=599\neq 1}$. Sendo assim, 599 é um divisor de 455839. Após uma rápida divisão, temos 455839 = 599×761.

A razão pela qual isto funciona é que a curva (mod 599) tem 640 = 2⁷·5 pontos, ao passo que a (mod 761) tem 777 = 3·7·37 pontos. Ademais, 640 e 777 são os menores inteiros positivos k tais que kP = ∞ na curva (mod 599) e (mod 761), respetivamente. Visto que 8! é um múltiplo de 640 mas não é um múltiplo de 777, temos 8!P = ∞ na curva (mod 599), mas não na curva (mod 761), daí a adição repetida ter falhado aqui, providenciando a fatoração.

Antes de considerar o plano projetivo sobre ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )/\sim }$, considere primeiro um espaço projetivo 'normal' sobre ${\displaystyle \mathbb {R} }$: Em vez de pontos, estudam-se as linhas que passam pela origem. Uma linha pode ser representada como um ponto não nulo ${\displaystyle (x,y,z)}$, sob uma relação de equivalência ~ dada por: ${\displaystyle (x,y,z)\sim (x',y',z')}$ ⇔ ∃ 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 ${\displaystyle \mathbb {P} ^{2}}$; os pontos, representados por ${\displaystyle (x:y:z)}$, correspondem a linhas num espaço tridimensional que passam pela origem. Note-se que o ponto ${\displaystyle (0:0:0)}$ 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 ${\displaystyle (x:y:z)}$ corresponde a ${\displaystyle (x/z:y/z)}$ no espaço afim.^[2]

No algoritmo, apenas é utilizada a estrutura de grupo de uma curva elíptica sobre o corpo ${\displaystyle \mathbb {R} }$. Dado que não precisamos necessariamente do corpo ${\displaystyle \mathbb {R} }$, um corpo finito também proporcionará uma estrutura de grupo numa curva elíptica. Contudo, considerar a mesma curva e operação sobre ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )/\sim }$ com n 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 ${\displaystyle (0:1:0)}$. Seja n um inteiro (positivo) a fatorar e considere-se a curva elíptica (um conjunto de pontos com alguma estrutura) ${\displaystyle E(\mathbb {Z} /n\mathbb {Z} )=\{(x:y:z)\in \mathbb {P} ^{2}\ |\ y^{2}z=x^{3}+axz^{2}+bz^{3}\}}$.

1. Escolha ${\displaystyle x_{P},y_{P},a\in \mathbb {Z} /n\mathbb {Z} }$ com a ≠ 0.
2. Calcule ${\displaystyle b=y_{P}^{2}-x_{P}^{3}-ax_{P}}$. A curva elíptica E fica, portanto, na forma de Weierstrass, dada por ${\displaystyle y^{2}=x^{3}+ax+b}$ e, ao recorrer a coordenadas projetivas, a curva elíptica é dada pela equação homogênea ${\displaystyle ZY^{2}=X^{3}+aZ^{2}X+bZ^{3}}$. Possui o ponto ${\displaystyle P=(x_{P}:y_{P}:1)}$.
3. Selecione um limite superior ${\displaystyle B\in \mathbb {Z} }$ para esta curva elíptica.
   • Observação: Apenas se encontrarão fatores p se a ordem do grupo g da curva elíptica E sobre ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ (denotada por ${\displaystyle \#E(\mathbb {Z} /p\mathbb {Z} )}$) for B-suave, o que significa que todos os fatores primos de ${\displaystyle n}$ têm de ser menores ou iguais a B.
4. Calcule ${\displaystyle k=\mathrm {mmc} (1,\dots ,B)}$.
5. Calcule ${\displaystyle kP:=P+P+\cdots +P}$ (a multiplicação é uma adição repetida) no anel ${\displaystyle E(\mathbb {Z} /n\mathbb {Z} )}$.
   • Se o cálculo retornar com sucesso ${\displaystyle kP=(0:1:0)}$, tal significa que g não é B-suave ou que n é 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 não seja primo, mas isso apenas ocorre quando se tenta inverter um resíduo particular v. Neste cenário, o fator é encontrado como ${\displaystyle \mathrm {mdc} (v,n)}$ 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 ${\displaystyle \mathrm {mdc} (x_{1}-x_{2},n)=1}$. Se ${\displaystyle P,Q}$ não forem ${\displaystyle (0:1:0)}$ 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: ${\displaystyle R=P+Q;}$ ${\displaystyle P=(x_{1}:y_{1}:1),Q=(x_{2}:y_{2}:1)}$,
• ${\displaystyle \lambda =(y_{1}-y_{2})(x_{1}-x_{2})^{-1}}$,
• ${\displaystyle x_{3}=\lambda ^{2}-x_{1}-x_{2}}$,
• ${\displaystyle y_{3}=\lambda (x_{1}-x_{3})-y_{1}}$,
• ${\displaystyle R=P+Q=(x_{3}:y_{3}:1)}$.

Se a adição falhar, tal dever-se-á a uma falha no cálculo de ${\displaystyle \lambda .}$ Especificamente, porque ${\displaystyle (x_{1}-x_{2})^{-1}}$ nem sempre pode ser calculado se n não for primo (e, por isso, ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ não é um corpo). Sem assumir que ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ é um corpo, poderia calcular-se:

• ${\displaystyle \lambda '=y_{1}-y_{2}}$,
• ${\displaystyle x_{3}'={\lambda '}^{2}-x_{1}(x_{1}-x_{2})^{2}-x_{2}(x_{1}-x_{2})^{2}}$,
• ${\displaystyle y_{3}'=\lambda '(x_{1}(x_{1}-x_{2})^{2}-x_{3}')-y_{1}(x_{1}-x_{2})^{3}}$,
• ${\displaystyle R=P+Q=(x_{3}'(x_{1}-x_{2}):y_{3}':(x_{1}-x_{2})^{3})}$, e simplificar se possível.

Este cálculo é sempre admissível e, caso o mdc da coordenada Z com n ≠ (1 ou n), a simplificação falha, encontrando-se um divisor não trivial de n.

De forma análoga à variante de duas fases do algoritmo p − 1 de Pollard, o ECM de Lenstra também pode ser efetuado em duas fases. Isto permite poupar um fator temporal de O(log p).^[2]

Algoritmo ECM de Duas Fases.^[2]

• Entrada: número a ser fatorado n, limites inteiros ${\displaystyle B_{1}\leq B_{2}}$.
• Saída: um fator de n ou falha.

Preparação.

1. Escolha uma curva elíptica aleatória E mod n.
2. Escolha um ponto ${\displaystyle P=(x_{0}:y_{0}:z_{0})}$ na curva.

(Uma escolha conveniente é a parametrização ${\displaystyle \sigma }$ de Suyama, que requer o sorteio de apenas um número aleatório).

Fases.

1. Calcule um ponto ${\textstyle Q:=\prod _{p\leq B_{1}}p^{\left\lfloor \log B_{1}/\log p\right\rfloor }P}$ sobre E. O produto indica que se itera sobre cada número primo ${\displaystyle p\leq B_{1}}$; este desempenha o mesmo papel que o grande ${\displaystyle k}$ observado nos algoritmos acima.
   • Utilizar o produto de todas as potências de números primos menores que ${\displaystyle B_{1}}$ em vez de ${\displaystyle B_{1}!}$ diminui a complexidade assintótica em ${\displaystyle O(\log B_{1})}$.^[3]
2. Para cada número primo p, ${\displaystyle B_{1}\leq p\leq B_{2}}$,
   • Calcule um ponto ${\displaystyle (x_{p}:y_{p}:z_{p})=pQ}$ sobre E.
   • Calcule ${\displaystyle g:=\mathrm {mdc} \left(n,z_{p}\right)}$. Se ${\displaystyle g\neq 1}$, imprima ${\displaystyle g}$ e saia.
3. Se todos os números primos no intervalo forem testados sem produzir um fator, relate falha.

É possível que a fase 1 produza um fator como discutido anteriormente: um denominador não invertível implica um fator. ${\displaystyle B_{1}}$ é, na sua função, igual a ${\displaystyle B}$ da versão normal, portanto, isto também sucede quando a ordem de grupo g é B-suave. Dito de outra forma, procura-se na fase 1 um divisor primo p tal que ${\displaystyle sP}$ seja o elemento neutro de ${\displaystyle E(\mathbb {Z} /p\mathbb {Z} )}$.

A segunda fase é muito idêntica à segunda fase do p-1 e p+1. Corresponde a uma continuação do trabalho da fase 1 e pode ser descrita com termos matemáticos bastante similares. Ela suaviza a condição para que um fator possa ser encontrado quando g é ${\displaystyle (B_{1},B_{2})}$-suave, ou, por outras palavras, quando o maior fator primo de g for no máximo ${\displaystyle B_{2}}$ e o segundo maior for no máximo ${\displaystyle B_{1}}$.

Para atingir a fase 2, espera-se que haja um primo p entre ${\displaystyle B_{1}}$ e ${\displaystyle B_{2}}$ tal que ${\displaystyle pQ=(0:1:0){\pmod {p}}}$; assim, buscar uma inversão falhada produzi-lo-ia através de um mdc. De forma equivalente, busca-se um divisor primo q tal que ${\displaystyle sP}$ tenha uma ordem prima pequena em ${\displaystyle E(\mathbb {Z} /q\mathbb {Z} )}$. A verificação de uma ordem pequena de ${\displaystyle sP}$ é realizada na fase 2 pelo cálculo de ${\displaystyle (ls)P}$ módulo n para cada número primo l.^[2]

O texto acima reflete a abordagem "ingênua", que permite a adoção da otimização de emparelhamento de primos e da extensão de Brent-Suyama. Existe, contudo, uma fase 2 muito mais rápida que assenta na multiplicação polinomial, oriunda da tese de 1992 de Peter Montgomery.^[2] Esta nova técnica pode ser encontrada no GMP-ECM e no Prime95.^[4] A mesma técnica foi depois estendida ao p-1 e p+1 (Montgomery e Kruppa 2008).^[5]

O uso de curvas de Edwards exige menos multiplicações modulares e menos tempo do que o uso de curvas de Montgomery ou curvas de Weierstrass (outros métodos utilizados). Recorrendo a curvas de Edwards, também é possível detetar um número superior de números primos.

Definição. Seja ${\displaystyle k}$ um corpo em que ${\displaystyle 2\neq 0}$, e sejam ${\displaystyle a,d\in k\setminus \{0\}}$ com ${\displaystyle a\neq d}$. Então a curva de Edwards torcida ${\displaystyle E_{E,a,d}}$ é dada por ${\displaystyle ax^{2}+y^{2}=1+dx^{2}y^{2}.}$ Uma curva de Edwards consiste numa curva de Edwards torcida em que ${\displaystyle a=1}$.

São conhecidas cinco formas de construir um conjunto de pontos numa curva de Edwards: o conjunto de pontos afins, o conjunto de pontos projetivos, o conjunto de pontos invertidos, o conjunto de pontos estendidos e o conjunto de pontos completados.

O conjunto dos pontos afins é dado por:

${\displaystyle \{(x,y)\in \mathbb {A} ^{2}:ax^{2}+y^{2}=1+dx^{2}y^{2}\}}$.

A lei de adição é dada por

${\displaystyle (e,f),(g,h)\mapsto \left({\frac {eh+fg}{1+degfh}},{\frac {fh-aeg}{1-degfh}}\right).}$

O ponto (0,1) é o seu elemento neutro e o inverso de ${\displaystyle (e,f)}$ é ${\displaystyle (-e,f)}$.

As restantes representações são definidas de forma semelhante à forma como a curva projetiva de Weierstrass deriva da afim.

Qualquer curva elíptica na forma de Edwards tem um ponto de ordem 4. Portanto, o grupo de torção de uma curva de Edwards sobre ${\displaystyle \mathbb {Q} }$ é isomorfo a ${\displaystyle \mathbb {Z} /4\mathbb {Z} ,\mathbb {Z} /8\mathbb {Z} ,\mathbb {Z} /12\mathbb {Z} ,\mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /4\mathbb {Z} }$ ou ${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /8\mathbb {Z} }$.

Os casos mais interessantes para o ECM são ${\displaystyle \mathbb {Z} /12\mathbb {Z} }$ e ${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /8\mathbb {Z} }$, dado que estes forçam as ordens de grupo da curva módulo primos a serem divisíveis por 12 e 16 respetivamente. As curvas enumeradas a seguir têm um grupo de torção isomorfo a ${\displaystyle \mathbb {Z} /12\mathbb {Z} }$:

• ${\displaystyle x^{2}+y^{2}=1+dx^{2}y^{2}}$ com ponto ${\displaystyle (a,b)}$ onde ${\displaystyle b\notin \{-2,-1/2,0,\pm 1\},a^{2}=-(b^{2}+2b)}$ e ${\displaystyle d=-(2b+1)/(a^{2}b^{2})}$
• ${\displaystyle x^{2}+y^{2}=1+dx^{2}y^{2}}$ com ponto ${\displaystyle (a,b)}$ onde ${\displaystyle a={\frac {u^{2}-1}{u^{2}+1}},b=-{\frac {(u-1)^{2}}{u^{2}+1}}}$ e ${\displaystyle d={\frac {(u^{2}+1)^{3}(u^{2}-4u+1)}{(u-1)^{6}(u+1)^{2}}},u\notin \{0,\pm 1\}.}$

Todas as curvas de Edwards com um ponto de ordem 3 podem ser inscritas das formas mostradas acima. Curvas com grupo de torção isomorfo a ${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /8\mathbb {Z} }$ e ${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /4\mathbb {Z} }$ podem revelar-se mais eficientes a descobrir primos.^[6]

O GMP-ECM de Paul Zimmerman é uma implementação de propósito geral do algoritmo de Lenstra baseada na GNU Multiple Precision Arithmetic Library. Tem sido continuamente atualizada, e a sua mais recente versão até setembro de 2025 é a 7.0.6 de julho de 2024. Permite a utilização de curvas de Montgomery, Weierstrass e de curvas (torcidas) Hessianas. Pode executar a fase 1 para um subconjunto de curvas de Montgomery numa GPU CUDA, tendo a implementação mais antiga de Cyril Bouvier de 2012 sido substituída pela nova implementação de Seth Troisi em 2021. A versão 7.0.6 também contempla uma implementação do método HECM (descrito mais abaixo), dos métodos p-1 e p+1 e da verificação de primalidade com recurso ao APRCL.^[7] O GMP-ECM é utilizado no SageMath.

Entre 2008 e 2010, Daniel J. Bernstein e os seus colaboradores publicaram uma sequência de implementações assentes nas curvas elípticas de Edwards Torcidas. Todas elas reclamam superar a performance da versão coeva do GMP-ECM, sendo o EECM-MPFQ de 2008 a sua mais avançada manifestação na época. Bernstein lançou também duas implementações concebidas para GPUs, sendo o CUDA-EECM de 2009 a versão mais contemporânea e veloz de ambas.^[6][8]

O Prime95 contém uma implementação do Lenstra ECM orientada para as curvas de Montgomery e Edwards. O seu uso é empregue no âmbito do subprojeto ECM do GIMPS, o qual tenta fatorar números de Mersenne compostos que não sejam menores que 2¹²¹³.^[9] Pode originar resultados da fase 1 harmonizados e compatíveis com o GMP-ECM, bem como processar os dados da fase 1 do GMP-ECM.^[10] Consegue ser mais rápido que o GMP-ECM na fase 1.^[11]

John Wloka e colaboradores divulgaram em 2020 o ecmongpu, uma materialização quer da fase 1 quer da fase 2 do Lenstra ECM suportada nas curvas elípticas de Edwards Torcidas. A sua tese foca-se na aferição de desempenho focada na fatoração de módulos até aos 448 bits de dimensão (ou seja, compreendidos entre 2⁴⁴⁷ e 2⁴⁴⁸-1).^[12]

Todo o software supramencionado é de código aberto. Além destes, de acordo com as referências de Paul Zimmerman, também o software de código aberto PARI/GP bem como o sistema privativo Magma compreendem nas suas soluções "boas implementações de ECM".^[11] Uma implementação anterior construída em software de 16 bits^[13] assenta no giantint delineado por Richard Crandall.^[11]

Existem desenvolvimentos recentes na utilização de curvas hiperelípticas para fatorar inteiros. Cosset demonstra no seu artigo (de 2010) que se pode construir uma curva hiperelíptica de género dois (portanto uma curva ${\displaystyle y^{2}=f(x)}$ com f de grau 5), o que fornece o mesmo resultado do que utilizar duas curvas elípticas "normais" em simultâneo. Ao utilizar a superfície de Kummer, o cálculo é mais eficiente. As desvantagens da curva hiperelíptica (em comparação com uma curva elíptica) são compensadas por esta forma alternativa de cálculo. Por conseguinte, Cosset defende, grosso modo, que o uso de curvas hiperelípticas para fatoração não é pior do que o uso de curvas elípticas.

Bernstein, Heninger, Lou e Valenta propõem o GEECM, uma versão quântica do ECM com curvas de Edwards.^[14] Ele utiliza o Algoritmo de Grover para duplicar, aproximadamente, o comprimento dos números primos encontrados quando comparado com o EECM normal, assumindo um computador quântico com qubits suficientes e de velocidade comparável ao do computador clássico a executar o EECM.

• Bernstein, Daniel J.; Birkner, Peter; Lange, Tanja; Peters, Christiane (2013). «ECM using Edwards curves». Mathematics of Computation. 82 (282): 1139–1179. MR 3008853. doi:10.1090/S0025-5718-2012-02633-0 
• Bosma, W.; Hulst, M. P. M. van der (1990). Primality proving with cyclotomy. [S.l.]: Ph.D. Thesis, Universiteit van Amsterdam. OCLC 256778332 
• Brent, Richard P. (1999). «Factorization of the tenth Fermat number». Mathematics of Computation. 68 (225): 429–451. Bibcode:1999MaCom..68..429B. MR 1489968. doi:10.1090/S0025-5718-99-00992-8 
• Cohen, Henri (1993). A Course in Computational Algebraic Number Theory. Col: Graduate Texts in Mathematics. 138. Berlin: Springer-Verlag. ISBN 978-0-387-55640-6. MR 1228206. doi:10.1007/978-3-662-02945-9 
• Cosset, R. (2010). «Factorization with genus 2 curves». Mathematics of Computation. 79 (270): 1191–1208. Bibcode:2010MaCom..79.1191C. MR 2600562. arXiv:0905.2325. doi:10.1090/S0025-5718-09-02295-9 
• Lenstra, A. K.; Lenstra Jr., H. W., eds. (1993). The development of the number field sieve. Col: Lecture Notes in Mathematics. 1554. Berlin: Springer-Verlag. pp. 11–42. ISBN 978-3-540-57013-4. MR 1321216. doi:10.1007/BFb0091534. Cópia arquivada em 12 de agosto de 2023 
• Lenstra Jr., H. W. (1987). «Factoring integers with elliptic curves» (PDF). Annals of Mathematics. 126 (3): 649–673. JSTOR 1971363. MR 0916721. doi:10.2307/1971363. hdl:1887/2140 
• Pomerance, Carl; Crandall, Richard (2005). Prime Numbers: A Computational Perspective Second ed. New York: Springer. ISBN 978-0-387-25282-7. MR 2156291 
• Pomerance, Carl (1985). «The quadratic sieve factoring algorithm». Advances in Cryptology, Proc. Eurocrypt '84. Col: Lecture Notes in Computer Science. 209. Berlin: Springer-Verlag. pp. 169–182. ISBN 978-3-540-16076-2. MR 0825590. doi:10.1007/3-540-39757-4_17 
• Pomerance, Carl (1996). «A Tale of Two Sieves» (PDF). Notices of the American Mathematical Society. 43 (12): 1473–1485. MR 1416721. Cópia arquivada (PDF) em 23 de novembro de 2025 
• Silverman, Robert D. (1987). «The Multiple Polynomial Quadratic Sieve». Mathematics of Computation. 48 (177): 329–339. MR 0866119. doi:10.1090/S0025-5718-1987-0866119-8 
• Trappe, W.; Washington, L. C. (2006). Introduction to Cryptography with Coding Theory Second ed. Saddle River, NJ: Pearson Prentice Hall. ISBN 978-0-13-186239-5. MR 2372272 
• Samuel S. Wagstaff, Jr. (2013). The Joy of Factoring. Providence, RI: American Mathematical Society. pp. 173–190. ISBN 978-1-4704-1048-3 
• Watras, Marcin (2008). Cryptography, Number Analysis, and Very Large Numbers. Bydgoszcz: Wojciechowski-Steinhagen. PL:5324564 

• Factorization using the Elliptic Curve Method, uma aplicação WebAssembly que utiliza ECM e muda para o Self-Initializing Quadratic Sieve quando este for mais veloz.
• GMP-ECM Arquivado em 2009-09-12 no Wayback Machine, uma implementação eficiente em ECM.
• ECMNet, uma implementação em matriz com facilidade assente em modelo cliente-servidor premente a funcionar com diversos e inerentes do aspeto da base associados de projetos atinentes do escopo pontual da fatoração.
• pyecm, uma implementação em python do ECM.
• Distributed computing project yoyo@Home Subprojeto ECM é focado atinente na dotação ao preceito com matriz no programa afeto fidedignamente associada perante Fatoração a Curvas Elípticas a estipulante base associado de vertente que providencia da premissa a focar a descobrir fatores adstritos com preceito em base na dimensão pautada a um reduto do cariz de naturezas diversas na dimensão associada afeta de moldura aos números.
• Lenstra Elliptic Curve Factorization algorithm source code Código-fonte simples do Algoritmo da Fatoração de Curva Elíptica baseada no GMP e no C.
• EECM-MPFQ Uma estipulação na sua afetação de moldura a focar de uma implementação consubstanciando e balizado inerente afeto a recurso de providenciar do ECM socorrendo-se de curvas com matriz em pendor associado a Edwards escritas estipulando ao preceito ditado com a biblioteca de corpo finito e base premente em referencial MPFQ.