Fatoração de curva elíptica Lenstra - Lenstra elliptic-curve factorization

A fatoração de curva elíptica de Lenstra ou o método de fatoração de curva elíptica ( ECM ) é um algoritmo de tempo de execução subexponencial rápido para fatoração de inteiros , que emprega curvas elípticas . Para fatoração de uso geral , ECM é o terceiro método de fatoração conhecido mais rápido. A segunda mais rápida é a peneira quadrática polinomial múltipla e a mais rápida é a peneira de campo de número geral . A fatoração da curva elíptica Lenstra recebeu o nome de Hendrik Lenstra .

Na prática, o ECM é considerado um algoritmo de fatoração de propósito especial, pois é mais adequado para encontrar pequenos fatores. Atualmente, ainda é o melhor algoritmo para divisores que não excedam 50 a 60 dígitos , já que seu tempo de execução é dominado pelo tamanho do menor fator p em vez do tamanho do número n a ser fatorado. Freqüentemente, o ECM é usado para remover pequenos fatores de um número inteiro muito grande com muitos fatores; se o inteiro restante ainda for composto, ele terá apenas grandes fatores e será fatorado usando técnicas de uso geral. O maior fator encontrado usando ECM até agora tem 83 dígitos decimais e foi descoberto em 7 de setembro de 2013 por R. Propper. Aumentar o número de curvas testadas aumenta as chances de encontrar um fator, mas não são lineares com o aumento do número de dígitos.

Algoritmo

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

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

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

2. Pode-se definir adição de dois pontos na curva, para definir um Grupo . As leis de adição são fornecidas no artigo sobre curvas elípticas .

   Podemos formar múltiplos repetidas de um ponto : . As fórmulas de adição envolvem tomar a inclinação modular da junção e , portanto, a divisão entre as classes de resíduos do módulo , realizada usando o algoritmo Euclidiano estendido . Em particular, a divisão por alguns inclui o cálculo do .${\ displaystyle P}$${\ displaystyle [k] P = P + \ ldots + P {\ text {(k vezes)}}}$${\ displaystyle P}$${\ displaystyle Q}$${\ displaystyle n}$${\ displaystyle v {\ bmod {n}}}$${\ displaystyle \ gcd (v, n)}$

   Assumindo que calculamos uma inclinação da forma com , então se , o resultado da adição do ponto será , o ponto "no infinito" correspondendo à interseção da linha "vertical" que une a curva. No entanto, se , então, a adição do ponto não produzirá um ponto significativo na curva; mas, mais importante, é um fator não trivial de .${\ displaystyle u / v}$${\ displaystyle \ gcd (u, v) = 1}$${\ displaystyle v = 0 {\ bmod {n}}}$${\ displaystyle \ infty}$${\ displaystyle P (x, y), P '(x, -y)}$${\ displaystyle \ gcd (v, n) \ neq 1, n}$${\ displaystyle \ gcd (v, n)}$${\ displaystyle n}$

3. Calcule na curva elíptica ( ), onde é um produto de muitos números pequenos: digamos, um produto de pequenos primos elevados a pequenas potências, como no algoritmo p-1 , ou o fatorial para alguns não muito grandes . Isso pode ser feito de forma eficiente, um pequeno fator de cada vez. Diga, para obter , primeiro calcule , depois , então , e assim por diante. é escolhido para ser pequeno o suficiente para que a adição do ponto -wise possa ser realizada em um tempo razoável. ${\ displaystyle [k] P}$${\ displaystyle {\ bmod {n}}}$${\ displaystyle k}$ ${\ displaystyle B!}$${\ displaystyle B}$${\ displaystyle [B!] P}$${\ displaystyle [2] P}$${\ displaystyle [3] ([2] P)}$${\ displaystyle [4] ([3!] P)}$${\ displaystyle B}$${\ displaystyle B}$
   • Se terminarmos todos os cálculos acima sem encontrar elementos não invertíveis ( ), isso significa que a ordem das curvas elípticas (módulo primos) não é
   suave o suficiente, então precisamos tentar novamente com uma curva diferente e um ponto de partida.${\ displaystyle {\ bmod {n}}}$
4. Se encontrarmos um , terminaremos: é um fator não trivial de .${\ displaystyle \ gcd (v, n) \ neq 1, m}$${\ displaystyle n}$

A complexidade do 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 , em L -notação . ${\ displaystyle L_ {p} \ left [{\ frac {1} {2}}, {\ sqrt {2}} \ right]}$

Por que o algoritmo funciona?

Se p e q são dois divisores primos de n , então y ²  =  x ³  + ax  +  b  (mod  n ) implica a mesma equação também módulo  p e módulo  q . Essas duas curvas elípticas menores com a adição agora são grupos genuínos . Se esses grupos têm N _p e N _q elementos, respectivamente, então para qualquer ponto P na curva original, pelo teorema de Lagrange , k  > 0 é mínimo, de modo que no módulo da curva p implica que k divide N _p ; além disso ,. A declaração análoga vale para o módulo de curva q . Quando a curva elíptica é escolhida aleatoriamente, então N _p e N _q são números aleatórios próximos de p  + 1 e q  + 1, respectivamente (veja abaixo). Portanto, é improvável que a maioria dos fatores primos de N _p e N _q sejam os mesmos, e é bem provável que, ao calcular eP , encontraremos algum kP que é ∞ módulo  p, mas não módulo  q , ou vice-versa. Quando este for o caso, kP não existe na curva original e nos cálculos encontramos algum v com mdc ( v , p ) =  p ou mdc ( v ,  q ) =  q , mas não ambos. Ou seja, mdc ( v ,  n ) deu um fator não trivial de  n .${\ displaystyle \ boxplus}$${\ displaystyle kP = \ infty}$${\ displaystyle N_ {p} P = \ infty}$

O ECM é, em sua essência, uma melhoria do algoritmo p  -1 mais antigo . O algoritmo p  - 1 encontra fatores primos p tais que p  - 1 é b-potências suave para pequenos valores de b . Para qualquer e , um múltiplo de p  - 1, e qualquer um relativamente primo a p , pelo pequeno teorema de Fermat temos a ^e  ≡ 1 ( mod p ) . Então mdc ( a ^e  - 1,  n ) provavelmente produzirá um fator de n . No entanto, o algoritmo falha quando p  - 1 tem grandes fatores primos, como é o caso de números contendo 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 , ao invés de considerar o grupo multiplicativo de Z _p que sempre tem ordem  p  - 1.

A fim 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. Embora não haja prova de que uma ordem de grupo suave será encontrada no intervalo de Hasse, usando métodos probabilísticos heurísticos , o teorema de Canfield-Erdős-Pomerance com opções de parâmetros adequadamente otimizados e a notação L , podemos esperar tentar L [ √ 2 /2, √ 2 ] curvas antes de começar um grupo fim lisa. Esta estimativa heurística é muito confiável na prática.

Um exemplo

O exemplo a seguir é de Trappe & Washington (2006) , com alguns detalhes adicionados.

Queremos fator n = 455839. Vamos escolher a curva elíptica y ² = x ³ + 5 x - 5, com o ponto P = (1, 1) sobre ele, e vamos tentar de computação (10!) P .

A inclinação da linha tangente em algum ponto A = ( x , y ) é s = (3 x ² + 5) / (2 y ) (mod n) . Usando s podemos calcular 2 A . Se o valor de s está na forma a / b onde b > 1 e mdc ( a , b ) = 1, temos que encontrar o inverso modular de b . Se não existir, mdc ( n , b ) é um fator não trivial de n .

Primeiro vamos calcular 2 P . Dispomos de ( P ) = s (1,1) = 4, então as coordenadas de 2 P = ( x ' , y' ) são x ' = s ² - 2 x = 14 e y' = S ( x - x ′ ) - y = 4 (1 - 14) - 1 = –53, todos os números compreendidos (mod n ). Apenas para verificar se este 2 P está de fato na curva: (–53) ² = 2809 = 14 ³ + 5 · 14 - 5.

Então calculamos 3 (2 P ). Temos s (2 P ) = s (14, -53) = –593/106 (mod n ). Usando o algoritmo euclidiano : 455839 = 4300 · 106 + 39, então 106 = 2 · 39 + 28, então 39 = 28 + 11, então 28 = 2 · 11 + 6, então 11 = 6 + 5, então 6 = 5 + 1. Portanto, mdc (455839, 106) = 1, e retrocedendo (uma versão do algoritmo euclidiano estendido ): 1 = 6 - 5 = 2 · 6 - 11 = 2 · 28 - 5 · 11 = 7 · 28 - 5 · 39 = 7 · 106 - 19 · 39 = 81707 · 106 - 19 · 455839. Portanto, 106 ⁻¹ = 81707 (mod 455839) e –593/106 = –133317 (mod 455839). Dado este s , podemos calcular as coordenadas de 2 (2 P ), assim como fizemos acima: 4 P = (259851, 116255). Apenas para verificar se este é realmente um ponto na curva: y ² = 54514 = x ³ + 5 x - 5 (mod 455839). Depois disso, podemos calcular . ${\ displaystyle 3 (2P) = 4P \ boxplus 2P}$

Podemos calcular 4 de forma semelhante! P e assim por diante, mas 8! P requer a inversão de 599 (mod 455839). O algoritmo Euclidiano dá que 455839 é divisível por 599, e encontramos uma fatoração 455839 = 599 · 761.

O motivo pelo qual isso funcionou é que a curva (mod 599) tem 640 = 2 ⁷ · 5 pontos, enquanto (mod 761) tem 777 = 3 · 7 · 37 pontos. Além disso, 640 e 777 são os menores inteiros positivos k tais que kP = ∞ na curva (mod 599) e (mod 761), respectivamente. Desde 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), portanto , a adição repetida quebrou aqui, produzindo a fatoração.

O algoritmo com coordenadas projetivas

Antes de considerar o plano projetivo sobre primeiro, considere um espaço projetivo 'normal' sobre ℝ: Em vez de pontos, as linhas através da origem são estudadas. Uma linha pode ser representada como um ponto diferente de zero , sob uma relação de equivalência ~ dada por: ⇔ ∃ c ≠ 0 tal que x '= c x , y' = c y e z '= c z . Nessa relação de equivalência, o espaço é denominado plano projetivo ; os pontos, denotados por , correspondem a linhas em um espaço tridimensional que passam pela origem. Observe que o ponto não existe neste espaço, pois para desenhar uma linha em qualquer direção possível requer pelo menos um de x ', y' ou z '≠ 0. Agora observe que quase todas as linhas passam por qualquer plano de referência - como o plano ( X , Y , 1), enquanto as linhas precisamente paralelas a este plano, tendo coordenadas ( X, Y , 0), especificam direções exclusivamente, como 'pontos no infinito' que são usados ​​no afim ( X, Y ) -avião que se encontra acima. ${\ displaystyle (\ mathbb {Z} / n \ mathbb {Z}) / \ sim,}$${\ displaystyle (x, y, z)}$${\ displaystyle (x, y, z) \ sim (x ', y', z ')}$ ${\ displaystyle \ mathbb {P} ^ {2}}$${\ displaystyle (x: y: z)}$${\ displaystyle (0: 0: 0)}$

No algoritmo, apenas a estrutura de grupo de uma curva elíptica sobre o campo ℝ é usada. Visto que não precisamos necessariamente do campo ℝ, um corpo finito também fornecerá uma estrutura de grupo em uma curva elíptica. No entanto, considerando a mesma curva e operação com n não primo, não dá um grupo. O Método da Curva Elíptica faz uso dos casos de falha da lei da adição. ${\ displaystyle (\ mathbb {Z} / n \ mathbb {Z}) / \ sim}$

Agora declaramos o algoritmo em coordenadas projetivas. O elemento neutro é então dado pelo ponto no infinito . Seja n um inteiro (positivo) e considere a curva elíptica (um conjunto de pontos com alguma estrutura) . ${\ displaystyle (0: 1: 0)}$${\ 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 com um ≠ 0.${\ displaystyle x_ {P}, y_ {P}, a \ in \ mathbb {Z} / n \ mathbb {Z}}$
2. Calcule . A curva elíptica E está então na forma Weierstrass dada por e usando coordenadas projetivas, a curva elíptica é dada pela equação homogênea . Ele tem o objetivo .${\ displaystyle b = y_ {P} ^ {2} -x_ {P} ^ {3} -ax_ {P}}$${\ displaystyle y ^ {2} = x ^ {3} + ax + b}$${\ displaystyle ZY ^ {2} = X ^ {3} + aZ ^ {2} X + bZ ^ {3}}$${\ displaystyle P = (x_ {P}: y_ {P}: 1)}$
3. Escolha um limite superior para esta curva elíptica. Observação: Você só vai encontrar fatores p se a ordem de grupos da curva elíptica E sobre (indicado por ) é B-liso , o que significa que todos os fatores primos de tem que ser menor ou igual a B .${\ displaystyle B \ in \ mathbb {Z}}$${\ displaystyle \ mathbb {Z} / p \ mathbb {Z}}$${\ displaystyle \ #E (\ mathbb {Z} / p \ mathbb {Z})}$${\ displaystyle \ #E (\ mathbb {Z} / p \ mathbb {Z})}$
4. Calcule .${\ displaystyle k = {\ rm {lcm}} (1, \ pontos, B)}$
5. Calcule ( k vezes) no ringue . Note-se que, se é B -Smooth e n é primordial (e, portanto, é um campo) que . No entanto, se apenas for B-smooth para algum divisor p de n , o produto pode não ser (0: 1: 0) porque adição e multiplicação não são bem definidas se n não for primo. Nesse caso, um divisor não trivial pode ser encontrado.${\ displaystyle kP: = P + P + \ cdots + P}$${\ displaystyle E (\ mathbb {Z} / n \ mathbb {Z})}$${\ displaystyle \ #E (\ mathbb {Z} / n \ mathbb {Z})}$${\ displaystyle \ mathbb {Z} / n \ mathbb {Z}}$${\ displaystyle kP = (0: 1: 0)}$${\ displaystyle \ #E (\ mathbb {Z} / p \ mathbb {Z})}$
6. Caso contrário, volte para a etapa 2. Se isso ocorrer, você notará isso ao simplificar o produto ${\ displaystyle kP.}$

No ponto 5, é dito que, nas circunstâncias certas, um divisor não trivial pode ser encontrado. Conforme apontado no artigo de Lenstra (Fatoração de inteiros com curvas elípticas), a adição precisa da suposição . Se não forem e distintos (caso contrário, a adição funciona de forma semelhante, mas é um pouco diferente), então a adição funciona da seguinte maneira: ${\ displaystyle \ gcd (x_ {1} -x_ {2}, n) = 1}$${\ displaystyle P, Q}$${\ displaystyle (0: 1: 0)}$

• 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, isso será devido a uma falha no cálculo Em particular, porque nem sempre pode ser calculado se n não for primo (e, portanto, não for um campo). Sem querer ser um campo, pode-se calcular: ${\ displaystyle \ lambda.}$${\ displaystyle (x_ {1} -x_ {2}) ^ {- 1}}$${\ displaystyle \ mathbb {Z} / n \ mathbb {Z}}$${\ displaystyle \ mathbb {Z} / n \ mathbb {Z}}$

• ${\ 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 simplifique se possível.

Este cálculo é sempre legal e se o mdc do Z -coordenar com n ≠ (1 ou n ), então quando a simplificação falha, um divisor não trivial de n é encontrado.

Curvas torcidas de Edwards

O uso de curvas de Edwards requer menos multiplicações modulares e menos tempo do que o uso de curvas de Montgomery ou curvas de Weierstrass (outros métodos usados). Usando as curvas de Edwards, você também pode encontrar mais primos.

Definição. Deixe ser um campo em que , e deixe com . Então a curva de Edwards torcida é dada por Uma curva de Edwards é uma curva de Edwards torcida na qual . ${\ displaystyle k}$${\ displaystyle 2 \ neq 0}$${\ displaystyle a, d \ in k \ setminus \ {0 \}}$${\ displaystyle a \ neq d}$${\ displaystyle E_ {E, a, d}}$${\ displaystyle ax ^ {2} + y ^ {2} = 1 + dx ^ {2} y ^ {2}.}$${\ displaystyle a = 1}$

Existem cinco maneiras conhecidas de construir um conjunto de pontos em uma 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 de pontos afins é dado por:

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

A lei da 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) é seu elemento neutro e o inverso de é . ${\ displaystyle (e, f)}$${\ displaystyle (-e, f)}$

As outras representações são definidas de forma semelhante à forma como a curva Weierstrass projetiva segue 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 é isomórfico para ou . ${\ displaystyle \ mathbb {Q}}$${\ 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}}$${\ displaystyle \ mathbb {Z} / 2 \ mathbb {Z} \ times \ mathbb {Z} / 8 \ mathbb {Z}}$

Os casos mais interessantes para ECM são e , uma vez que eles forçam as ordens de grupo dos primos do módulo da curva a serem divisíveis por 12 e 16, respectivamente. As seguintes curvas têm um grupo de torção isomórfico a : ${\ displaystyle \ mathbb {Z} / 12 \ mathbb {Z}}$${\ displaystyle \ mathbb {Z} / 2 \ mathbb {Z} \ times \ mathbb {Z} / 8 \ mathbb {Z}}$${\ displaystyle \ mathbb {Z} / 12 \ mathbb {Z}}$

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

Cada curva de Edwards com um ponto de ordem 3 pode ser escrita das maneiras mostradas acima. Curvas com grupo de torção isomórfico a e podem ser mais eficientes na localização de primos. ${\ displaystyle \ mathbb {Z} / 2 \ mathbb {Z} \ times \ mathbb {Z} / 8 \ mathbb {Z}}$${\ displaystyle \ mathbb {Z} / 2 \ mathbb {Z} \ times \ mathbb {Z} / 4 \ mathbb {Z}}$

Estágio 2

O texto acima é sobre o primeiro estágio da fatoração da curva elíptica. Espera-se encontrar um divisor primo p tal que seja o elemento neutro de . No segundo estágio, espera-se encontrar um divisor primo q tal que tenha ordem primo pequena em . ${\ displaystyle sP}$${\ displaystyle E (\ mathbb {Z} / p \ mathbb {Z})}$${\ displaystyle sP}$${\ displaystyle E (\ mathbb {Z} / q \ mathbb {Z})}$

Esperamos que a ordem esteja entre e , onde é determinado no estágio 1 e é o novo parâmetro do estágio 2. A verificação de uma pequena ordem de , pode ser feita calculando o módulo n para cada primo l . ${\ displaystyle B_ {1}}$${\ displaystyle B_ {2}}$${\ displaystyle B_ {1}}$${\ displaystyle B_ {2}}$${\ displaystyle sP}$${\ displaystyle (ls) P}$

GMP-ECM e EECM-MPFQ

O uso de curvas elípticas Twisted Edwards, bem como outras técnicas foram utilizadas por Bernstein et al para fornecer uma implementação otimizada de ECM. Sua única desvantagem é que ele funciona em números compostos menores do que a implementação de propósito mais geral, GMP-ECM de Zimmerman.

Método da curva hiperelíptica (HECM)

Existem desenvolvimentos recentes no uso de curvas hiperelípticas para fatorar inteiros. Cosset mostra em seu artigo (de 2010) que se pode construir uma curva hiperelíptica com gênero dois (portanto, uma curva com f de grau 5), o que dá o mesmo resultado que usar duas curvas elípticas "normais" ao mesmo tempo. Fazendo uso da superfície Kummer, o cálculo é mais eficiente. As desvantagens da curva hiperelíptica (versus uma curva elíptica) são compensadas por esta forma alternativa de cálculo. Portanto, Cosset afirma aproximadamente que usar curvas hiperelípticas para fatoração não é pior do que usar curvas elípticas. ${\ displaystyle y ^ {2} = f (x)}$

Versão quântica (GEECM)

Bernstein , Heninger , Lou e Valenta sugerem GEECM, uma versão quântica de ECM com curvas de Edwards. Ele usa o algoritmo de Grover para quase dobrar o comprimento dos primos encontrados em comparação com o EECM padrão, assumindo um computador quântico com qubits suficientes e de velocidade comparável ao computador clássico executando o EECM.

Veja também

• UBASIC para programa prático (ECMX).

Referências

• Bernstein, Daniel J .; Birkner, Peter; Lange, Tanja; Peters, Christiane (2013). "ECM usando curvas de Edwards". Matemática da Computação . 82 (282): 1139–1179. doi : 10.1090 / S0025-5718-2012-02633-0 . MR  3008853 .
• Bosma, W .; Hulst, MPM van der (1990). Primalidade comprovada com ciclotomia . Ph.D. Tese, Universiteit van Amsterdam. OCLC  256778332 .
• Brent, Richard P. (1999). "Fatoração do décimo número de Fermat" . Matemática da Computação . 68 (225): 429–451. Bibcode : 1999MaCom..68..429B . doi : 10.1090 / S0025-5718-99-00992-8 . MR  1489968 .
• Cohen, Henri (1993). Um Curso de Teoria Algébrica dos Números Computacional . Textos de Pós-Graduação em Matemática. 138 . Berlim: Springer-Verlag. doi : 10.1007 / 978-3-662-02945-9 . ISBN 978-0-387-55640-6. MR  1228206 .
• Cosset, R. (2010). "Fatoração com curvas de gênero 2". Matemática da Computação . 79 (270): 1191–1208. arXiv : 0905.2325 . Bibcode : 2010MaCom..79.1191C . doi : 10.1090 / S0025-5718-09-02295-9 . MR  2600562 .
• Lenstra, AK ; Lenstra Jr., HW, eds. (1993). O desenvolvimento da peneira de campo numérico . Notas de aula em matemática. 1554 . Berlim: Springer-Verlag. doi : 10.1007 / BFb0091534 . ISBN 978-3-540-57013-4. MR  1321216 .
• Lenstra Jr., HW (1987). "Fatoração de inteiros com curvas elípticas" (PDF) . Annals of Mathematics . 126 (3): 649–673. doi : 10.2307 / 1971363 . hdl : 1887/2140 . JSTOR  1971363 . MR  0916721 .
• Pomerance, Carl ; Crandall, Richard (2005). Prime Numbers: A Computational Perspective (Segunda ed.). Nova York: Springer. ISBN 978-0-387-25282-7. MR  2156291 .
• Pomerance, Carl (1985). "O algoritmo de fatoração de peneira quadrática". Advances in Cryptology, Proc. Eurocrypt '84 . Notas de aula em Ciência da Computação. 209 . Berlim: Springer-Verlag. pp. 169–182. doi : 10.1007 / 3-540-39757-4_17 . ISBN 978-3-540-16076-2. MR  0825590 .
• Pomerance, Carl (1996). "A Tale of Two Sieves" (PDF) . Avisos da American Mathematical Society . 43 (12): 1473–1485. MR  1416721 .
• Silverman, Robert D. (1987). "The Multiple Polynomial Quadratic Sieve" . Matemática da Computação . 48 (177): 329–339. doi : 10.1090 / S0025-5718-1987-0866119-8 . MR  0866119 .
• Trappe, W .; Washington, LC (2006). Introduction to Cryptography with Coding Theory (Segunda ed.). Saddle River, NJ: Pearson Prentice Hall. ISBN 978-0-13-186239-5. MR  2372272 .
• Samuel S. Wagstaff, Jr. (2013). A alegria de fatorar . Providence, RI: American Mathematical Society. pp. 173–190. ISBN 978-1-4704-1048-3.
• Watras, Marcin (2008). Criptografia, análise de números e números muito grandes . Bydgoszcz: Wojciechowski-Steinhagen. PL: 5324564.

links externos

• Fatoração usando o método da curva elíptica , um miniaplicativo Java que usa ECM e alterna para a peneira quadrática de auto-inicialização quando é mais rápida.
• GMP-ECM , uma implementação eficiente de ECM.
• ECMNet , uma implementação cliente-servidor fácil que funciona com vários projetos de fatoração.
• pyecm , uma implementação python do ECM. Muito mais rápido com psyco e / ou gmpy.
• Projeto de computação distribuída yoyo @ Home Subproject ECM é um programa para Fatoração de Curva Elíptica que é usado por alguns projetos para encontrar fatores para diferentes tipos de números.
• Código-fonte do algoritmo de Fatorização de Curva Elíptica Lenstra Código-fonte do Algoritmo de Fatorização de Curva Elíptica C simples e GMP
• EECM-MPFQ Uma implementação de ECM usando curvas de Edwards escritas com a biblioteca de campos finitos MPFQ.