Primalidade da curva elíptica - Elliptic curve primality

Em matemática , as técnicas de teste de primalidade de curva elíptica ou teste de primalidade de curva elíptica (ECPP), estão entre os métodos mais rápidos e mais amplamente usados ​​em teste de primalidade. É uma ideia apresentada por Shafi Goldwasser e Joe Kilian em 1986 e transformada em um algoritmo pela AOL Atkin no mesmo ano. O algoritmo foi alterado e melhorado por vários colaboradores posteriormente, e notadamente por Atkin e François Morain  [ de ] , em 1993. O conceito de usar curvas elípticas na fatoração foi desenvolvido por HW Lenstra em 1985, e as implicações para seu uso na primalidade testes (e provas) seguiram rapidamente.

O teste de primazia é um campo que existe desde a época de Fermat , em cuja época a maioria dos algoritmos eram baseados em fatoração, que se tornava difícil de manejar com grandes entradas ; algoritmos modernos tratam dos problemas de determinar se um número é primo e quais são seus fatores separadamente. Tornou-se de importância prática com o advento da criptografia moderna. Embora muitos testes atuais resultem em uma saída probabilística ( N é mostrado composto, ou provavelmente primo, como com o teste de primalidade Baillie – PSW ou o teste de Miller – Rabin ), o teste de curva elíptica prova primalidade (ou composição) com uma certificado verificável.

Métodos de comprovação de primários previamente conhecidos, como o teste de primalidade de Pocklington, exigiam pelo menos fatoração parcial de para provar que é primo. Como resultado, esses métodos exigiram um pouco de sorte e geralmente são lentos na prática. ${\ displaystyle N \ pm 1}$${\ displaystyle N}$

Prova de primalidade de curva elíptica

É um algoritmo de propósito geral , o que significa que não depende do número ter uma forma especial. O ECPP é atualmente, na prática, o algoritmo conhecido mais rápido para testar a primalidade de números gerais, mas o tempo de execução do pior caso não é conhecido. ECPP é executado heuristicamente no tempo:

${\ displaystyle O ((\ log n) ^ {5+ \ varepsilon}) \,}$

para alguns . Este expoente pode ser reduzido para algumas versões por argumentos heurísticos. ECPP funciona da mesma maneira que a maioria dos outros testes de primalidade , encontrar um grupo e mostrar seu tamanho é o que é principal. Para ECPP, o grupo é uma curva elíptica sobre um conjunto finito de formas quadráticas, sendo trivial fatorar sobre o grupo. ${\ displaystyle \ varepsilon> 0}$${\ displaystyle 4+ \ varepsilon}$${\ displaystyle p}$${\ displaystyle p-1}$

O ECPP gera um certificado Atkin - Goldwasser –Kilian – Morain de primalidade por recursão e, em seguida, tenta verificar o certificado. A etapa que consome mais tempo de CPU é a geração do certificado, porque a fatoração sobre um campo de classe deve ser executada. O certificado pode ser verificado rapidamente, permitindo que uma verificação da operação demore muito pouco tempo.

Em fevereiro de 2020, o maior número primo comprovado com o método ECPP tinha 40.000 dígitos. A certificação por Paul Underwood levou 21,5 meses usando o software Primo de Marcel Martin.

Proposição

Os testes de primalidade da curva elíptica são baseados em critérios análogos ao critério de Pocklington, no qual esse teste é baseado, onde o grupo é substituído por e E é uma curva elíptica escolhida apropriadamente. Vamos agora apresentar uma proposição na qual basear nosso teste, que é análogo ao critério de Pocklington, e dá origem à forma Goldwasser-Kilian-Atkin do teste de primalidade da curva elíptica. ${\ displaystyle (\ mathbb {Z} / n \ mathbb {Z}) ^ {*}}$${\ displaystyle E (\ mathbb {Z} / n \ mathbb {Z}),}$

Deixe- N ser um inteiro positivo, e E ser o conjunto que é definido pela equação Considere E sobre usar a lei além de costume em E , e write 0 para o elemento neutro em E . ${\ displaystyle y ^ {2} = x ^ {3} + ax + b {\ bmod {N}}.}$${\ displaystyle \ mathbb {Z} / N \ mathbb {Z},}$

Seja m um número inteiro. Se houver um primo q que divide m , e é maior que e existe um ponto P em E tal que ${\ displaystyle \ left ({\ sqrt [{4}] {N}} + 1 \ right) ^ {2}}$

(1) mP = 0

(2) ( m / q ) P é definido e não igual a 0

Então N é primo.

Prova

Se N é composto, então existe um número primo que divide N . Definir como a curva elíptica definida pela mesma equação como E mas avaliada módulo  p em vez de módulo  N . Defina como a ordem do grupo . Pelo teorema de Hasse sobre curvas elípticas , sabemos ${\ displaystyle p \ leq {\ sqrt {N}}}$${\ displaystyle E_ {p}}$${\ displaystyle m_ {p}}$${\ displaystyle E_ {p}}$

${\ displaystyle m_ {p} \ leq p + 1 + 2 {\ sqrt {p}} = \ left ({\ sqrt {p}} + 1 \ right) ^ {2} \ leq \ left ({\ sqrt [ {4}] {N}} + 1 \ direita) ^ {2} <q}$

e, portanto , existe um inteiro u com a propriedade que ${\ displaystyle \ gcd (q, m_ {p}) = 1}$

${\ displaystyle uq \ equiv 1 {\ bmod {m_ {p}}}}$

Seja o ponto P avaliado módulo p . Assim, em nós temos ${\ displaystyle P_ {p}}$${\ displaystyle E_ {p}}$

${\ displaystyle (m / q) P_ {p} = uq (m / q) P_ {p} = umP_ {p} = 0,}$

por (1), como é calculado usando o mesmo método que mP , exceto módulo  p em vez de módulo  N (e ). ${\ displaystyle mP_ {p}}$${\ displaystyle p \ mid N}$

Isso contradiz (2), porque se ( m / q ) P for definido e não for igual a 0 (mod  N ), então o mesmo método calculado módulo  p em vez de módulo  N resultará em:

${\ displaystyle (m / q) P_ {p} \ neq 0.}$

Algoritmo Goldwasser-Kilian

A partir dessa proposição, um algoritmo pode ser construído para provar que um inteiro, N , é primo. Isto se faz do seguinte modo:

Escolha três inteiros aleatoriamente, a, x, y e defina

${\ displaystyle b \ equiv y ^ {2} -x ^ {3} -ax {\ pmod {N}}}$

Agora P = ( x , y ) é um ponto em E , onde temos que E é definido por . Em seguida temos um algoritmo para contar o número de pontos de E . Aplicado a E , este algoritmo (Koblitz e outros sugerem o algoritmo de Schoof ) produz um número m que é o número de pontos na curva E sobre F _N , desde que N seja primo. Se o algoritmo de contagem de pontos pára em uma expressão indefinido isto permite determinar um factor não-trivial de N . Se for bem-sucedido, aplicamos um critério para decidir se nossa curva E é aceitável. ${\ displaystyle y ^ {2} = x ^ {3} + ax + b}$

Se podemos escrever m na forma em que é um número inteiro pequeno e q um grande privilegiada provável (um número que passa um probabilística teste primality , por exemplo), então não fazer descarte E . Caso contrário, descartamos nossa curva e selecionamos aleatoriamente outro triplo (a, x, y) para recomeçar. A ideia aqui é encontrar um m que seja divisível por um grande número primo q . Isto é primordial alguns dígitos mais pequeno do que m (ou N ), de modo q será mais fácil para provar privilegiada do que N . ${\ displaystyle m = kq}$${\ displaystyle k \ geq 2}$

Assumindo que encontramos uma curva que passa no critério, prossiga para calcular mP e kP . Se qualquer um dos dois cálculos produzem uma expressão indefinida, podemos obter um fator não-trivial de N . Se ambos os cálculos forem bem-sucedidos, examinamos os resultados.

Se for claro que N não é primo, porque se N fosse primo então E teria ordem m , e qualquer elemento de E se tornaria 0 na multiplicação por m . Se kP = 0, então o algoritmo descarta E e começa com um triplo a, x, y diferente . ${\ displaystyle mP \ neq 0}$

Agora, se e então nossa proposição anterior nos diz que N é primo. No entanto, existe um problema possível, que é a primalidade de q . Isso é verificado usando o mesmo algoritmo. Portanto, descrevemos um algoritmo recursivo , em que a primalidade de N depende da primalidade de q e, de fato, de 'primos prováveis' menores até que algum limite seja alcançado onde q é considerado pequeno o suficiente para aplicar um algoritmo determinístico não recursivo. ${\ displaystyle mP = 0}$${\ displaystyle kP \ neq 0}$

Problemas com o algoritmo

Atkin e Morain afirmam "o problema com GK é que o algoritmo de Schoof parece quase impossível de implementar." É muito lento e complicado contar todos os pontos em E usando o algoritmo de Schoof, que é o algoritmo preferido para o algoritmo Goldwasser-Kilian. Porém, o algoritmo original de Schoof não é eficiente o suficiente para fornecer o número de pontos em um curto espaço de tempo. Esses comentários devem ser vistos no contexto histórico, antes dos aprimoramentos de Elkies e Atkin ao método de Schoof.

Um segundo problema que Koblitz observa é a dificuldade de encontrar a curva E cujo número de pontos é da forma kq , como acima. Não há nenhum teorema conhecido que garanta que podemos encontrar um E adequado em muitas tentativas polinomialmente. A distribuição dos primos no intervalo de Hasse , que contém m , não é a mesma que a distribuição dos primos nas ordens de grupo, contando curvas com multiplicidade. No entanto, este não é um problema significativo na prática. ${\ displaystyle [p + 1-2 {\ sqrt {p}}, p + 1 + 2 {\ sqrt {p}}]}$

Teste de primalidade da curva elíptica de Atkin-Morain (ECPP)

Em um artigo de 1993, Atkin e Morain descreveram um algoritmo ECPP que evitou o problema de depender de um algoritmo de contagem de pontos incômodo (Schoof's). O algoritmo ainda depende da proposição declarada acima, mas ao invés de gerar curvas elípticas aleatoriamente e buscar um m adequado , sua ideia era construir uma curva E onde o número de pontos fosse fácil de calcular. A multiplicação complexa é a chave na construção da curva.

Agora, dado um N para o qual as necessidades de primalidade de ser provado que precisamos encontrar um adequado m e q , assim como no teste de Goldwasser-Kilian, que vai cumprir a proposição e provar a primality de N . (Claro, um ponto P e a própria curva, E , também devem ser encontrados.)

ECPP usa multiplicação complexa para construir a curva E , fazendo isso de uma forma que permite que m (o número de pontos em E ) seja facilmente calculado. Vamos agora descrever este método:

A utilização da multiplicação complexa requer um discriminante negativo , D , de modo que D pode ser escrito como o produto de dois elementos , ou de forma totalmente equivalente, podemos escrever a equação: ${\ displaystyle D = \ pi {\ bar {\ pi}}}$

${\ displaystyle a ^ {2} + | D | b ^ {2} = 4N \,}$

Para alguns a, b . Se pudermos descrever N em termos de qualquer uma destas formas, que pode criar uma curva elíptica E sobre a multiplicação complexa (descrito em detalhe abaixo), e o número de pontos é dada por: ${\ displaystyle \ mathbb {Z} / N \ mathbb {Z}}$

${\ displaystyle | E (\ mathbb {Z} / N \ mathbb {Z}) | = N + 1- \ pi - {\ bar {\ pi}} = N + 1-a. \,}$

Para N se dividir em dois elementos, precisamos disso (onde denota o símbolo de Legendre ). Esta é uma condição necessária, e alcançamos suficiência se o número de classe h ( D ) da ordem em for 1. Isso acontece para apenas 13 valores de D , que são os elementos de {−3, −4, −7, - 8, −11, −12, −16, −19, −27, −28, −43, −67, −163} ${\ displaystyle \ left ({\ frac {D} {N}} \ right) = 1}$${\ displaystyle \ left ({\ frac {D} {N}} \ right)}$ ${\ displaystyle \ mathbb {Q} ({\ sqrt {D}})}$

O teste

Escolha discriminantes D em sequência de aumento de h ( D ). Para cada D, verifique se e se 4 N pode ser escrito como: ${\ displaystyle \ left ({\ frac {D} {N}} \ right) = 1}$

${\ displaystyle a ^ {2} + | D | b ^ {2} = 4N \,}$

Esta parte pode ser verificada usando o algoritmo de Cornacchia . Uma vez que D e a aceitáveis tenham sido descobertos, calcule . Agora, se m tem um fator primo q de tamanho ${\ displaystyle m = N + 1-a}$

${\ displaystyle q> (N ^ {1/4} +1) ^ {2}}$

use o método de multiplicação complexa para construir a curva E e um ponto P sobre ela. Então, podemos usar nossa proposta para verificar a primality de N . Observe que se m não tem um grande fator primo ou não pode ser fatorado com rapidez suficiente, outra escolha de D pode ser feita.

Método de multiplicação complexo

Para completar, forneceremos uma visão geral da multiplicação complexa , a maneira pela qual uma curva elíptica pode ser criada, dado nosso D (que pode ser escrito como um produto de dois elementos).

Suponha primeiro que e (esses casos são muito mais fáceis de fazer). É necessário calcular os j-invariantes elípticos das classes h ( D ) da ordem do discriminante D como números complexos. Existem várias fórmulas para calculá-los. ${\ displaystyle D \ neq -3}$${\ displaystyle D \ neq -4}$

Em seguida, crie o polinômio mônico , que tem raízes correspondentes aos valores h ( D ). Observe, esse é o polinômio da classe . Da teoria da multiplicação complexa, sabemos que tem coeficientes inteiros, o que nos permite estimar esses coeficientes com precisão suficiente para descobrir seus valores verdadeiros. ${\ displaystyle H_ {D} (X)}$${\ displaystyle H_ {D} (X)}$${\ displaystyle H_ {D} (X)}$

Agora, se N é primo, CM nos diz que divide o módulo  N em um produto de h ( D ) fatores lineares, com base no fato de que D foi escolhido de forma que N se divide como o produto de dois elementos. Agora, se j é uma das raízes h ( D ) do módulo N , podemos definir E como: ${\ displaystyle H_ {D} (X)}$

${\ displaystyle y ^ {2} = x ^ {3} -3kc ^ {2r} x + 2kc ^ {3r}, {\ text {onde}} k = {\ frac {j} {j-1728}}, }$

c é qualquer mod N não residual quadrático e r é 0 ou 1.

Dada uma raiz j, existem apenas duas escolhas não isomórficas possíveis de E , uma para cada escolha de r . Temos a cardinalidade dessas curvas como

${\ displaystyle | E (\ mathbb {Z} / N \ mathbb {Z}) | = N + 1-a}$ ou ${\ displaystyle | E (\ mathbb {Z} / N \ mathbb {Z}) | = N + 1 + a}$

Discussão

Assim como com o teste Goldwasser-Killian, este leva a um procedimento de down-run. Novamente, o culpado é q . Assim que encontrarmos um q que funcione, devemos verificar se ele é primo, então, na verdade, estamos fazendo todo o teste agora para q . Então, novamente, podemos ter que realizar o teste para fatores de q . Isso leva a um certificado aninhado em que em cada nível temos uma curva elíptica E , an meo primo em dúvida,  q .

Exemplo de Atkin-Morain ECPP

Construímos um exemplo para provar que é primordial usando o teste Atkin-Morain ECPP. Primeiro, prossiga com o conjunto de 13 discriminantes possíveis, testando se o símbolo de Legendre e se 4 N podem ser escritos como . ${\ displaystyle N = 167}$${\ displaystyle (D / N) = 1}$${\ displaystyle 4N = a ^ {2} + | D | b ^ {2}}$

Para nosso exemplo é escolhido. Isso ocorre porque e também, usando o algoritmo de Cornacchia , sabemos que e, portanto, a = 25 eb = 1. ${\ displaystyle D = -43}$${\ displaystyle (D / N) = (- 43/167) = 1}$${\ displaystyle 4 \ cdot (167) = 25 ^ {2} + (43) (1 ^ {2})}$

A próxima etapa é calcular m . Isso é feito facilmente, o que resulta em Em seguida, precisamos encontrar um provável divisor primo de m , que foi referido como q . Deve satisfazer a condição de que${\ displaystyle m = N + 1-a}$${\ displaystyle m = 167 + 1-25 = 143.}$${\ displaystyle q> (N ^ {1/4} +1) ^ {2}.}$

Nesse caso, m = 143 = 11 × 13. Portanto, infelizmente, não podemos escolher 11 ou 13 como nosso q , pois isso não satisfaz a desigualdade necessária. Somos salvos, no entanto, por uma proposição análoga àquela que afirmamos antes do algoritmo Goldwasser-Kilian, que vem de um artigo de Morain. Ele afirma que, dada a nossa m , nós olhamos para um s que divide m , mas não é necessariamente nobre, e verificar se, para cada qual divide s${\ displaystyle s> (N ^ {1/4} +1) ^ {2}}$${\ displaystyle p_ {i}}$

${\ displaystyle (m / p_ {i}) P \ neq P _ {\ infty}}$

para algum ponto P em nossa curva ainda a ser construída.

Se s satisfaz a desigualdade e seus fatores primos satisfazem o acima, então N é primo.

Portanto, em nosso caso, escolhemos s = m = 143. Assim, nossos possíveis são 11 e 13. Primeiro, é claro que , e por isso precisamos apenas verificar os valores de ${\ displaystyle p_ {i}}$${\ displaystyle 143> (167 ^ {1/4} +1) ^ {2}}$

${\ displaystyle (143/11) P = 13P \ qquad {\ text {and}} \ qquad (143/13) P = 11P.}$

Mas antes que possamos fazer isso, devemos construir nossa curva, e escolher um ponto P . Para construir a curva, fazemos uso de multiplicação complexa. Em nosso caso, calculamos o invariante J

${\ displaystyle j \ equiv -960 ^ {3} {\ pmod {167}} \ equiv 107 {\ pmod {167}}.}$

Em seguida, calculamos

${\ displaystyle k = {\ frac {j} {1728-j}} {\ pmod {167}} \ equiv 158 {\ pmod {167}}}$

e sabemos que nossa curva elíptica tem a forma:

${\ displaystyle y ^ {2} = x ^ {3} + 3kc ^ {2} x + 2kc ^ {3}}$,

onde k é como descrito anteriormente e c um não quadrado em . Então podemos começar com ${\ displaystyle \ mathbb {F} _ {167}}$

${\ displaystyle {\ begin {alinhado} r & = 0 \\ 3k & \ equiv 140 {\ pmod {167}} \\ 2k & \ equiv 149 {\ pmod {167}} \ end {alinhado}}}$

que produz

${\ displaystyle E: y ^ {2} = x ^ {3} + 140x + 149 {\ pmod {167}}}$

Agora, utilizando o ponto P = (6,6) em E pode-se verificar que${\ displaystyle 143P = P _ {\ infty}.}$

É simples verificar que 13 (6, 6) = (12, 65) e 11 P = (140, 147), e assim, pela proposição de Morain, N é primo.

Complexidade e tempos de execução

O algoritmo de prova de primalidade da curva elíptica de Goldwasser e Kilian termina no tempo polinomial esperado por pelo menos

${\ displaystyle 1-O \ left (2 ^ {- N {\ frac {1} {\ log \ log n}}} \ right)}$

de entradas principais.

Conjetura

Seja o número de primos menores que x${\ displaystyle \ pi (x)}$

${\ displaystyle \ exists c_ {1}, c_ {2}> 0: \ pi (x + {\ sqrt {x}}) - \ pi (x) \ geq {\ frac {c_ {2} {\ sqrt {x }}} {\ log ^ {c_ {1}} x}}}$

para x suficientemente grande .

Se aceitarmos essa conjectura, o algoritmo Goldwasser-Kilian termina no tempo polinomial esperado para cada entrada. Além disso, se nosso N tiver comprimento k , o algoritmo criará um certificado de tamanho que pode ser verificado em . ${\ displaystyle O (k ^ {2})}$${\ displaystyle O (k ^ {4})}$

Agora considere outra conjectura, que nos dará um limite no tempo total do algoritmo.

Conjectura 2

Suponha que existam constantes positivas e tal que a quantidade de primos no intervalo ${\ displaystyle c_ {1}}$${\ displaystyle c_ {2}}$

${\ displaystyle [x, x + {\ sqrt {2x}}], x \ geq 2}$ é maior que ${\ displaystyle c_ {1} {\ sqrt {x}} (\ log x) ^ {- c_ {2}}}$

Em seguida, o algoritmo Goldwasser Kilian prova a primalidade de N em um tempo esperado de

${\ displaystyle O (\ log ^ {10 + c_ {2}} n)}$

Para o algoritmo Atkin-Morain, o tempo de execução declarado é

${\ displaystyle O ((\ log N) ^ {6+ \ epsilon})}$ para alguns ${\ displaystyle \ epsilon> 0}$

Primos de forma especial

Para algumas formas de números, é possível encontrar 'atalhos' para uma prova de primalidade. Esse é o caso dos números de Mersenne . Na verdade, devido à sua estrutura especial, que permite uma verificação mais fácil da primalidade, os seis maiores números primos conhecidos são todos números de Mersenne. Existe um método em uso há algum tempo para verificar a primalidade dos números de Mersenne, conhecido como teste de Lucas-Lehmer . Este teste não depende de curvas elípticas. No entanto, apresentamos um resultado onde os números da forma onde , n ímpar podem ser provados primos (ou compostos) usando curvas elípticas. Claro, isso também fornecerá um método para provar a primalidade dos números de Mersenne, que correspondem ao caso em que n = 1. Existe um método para testar esta forma de número sem curvas elípticas (com uma limitação no tamanho de k) conhecido como teste Lucas – Lehmer – Riesel . O método a seguir foi extraído do Teste de Primalidade em papel para usar curvas elípticas , de Yu Tsumura. ${\ displaystyle N = 2 ^ {k} n-1}$${\ displaystyle k, n \ in \ mathbb {Z}, k \ geq 2}$${\ displaystyle 2 ^ {k} n-1}$

Estrutura de grupo de ${\ displaystyle E (\ mathbb {F} _ {N})}$

Tomamos E como nossa curva elíptica, onde E tem a forma de onde é primo e com ímpar. ${\ displaystyle y ^ {2} = x ^ {3} -mx}$${\ displaystyle m \ in \ mathbb {Z}, m \ not \ equiv 0 {\ bmod {p}},}$${\ displaystyle p \ equiv 3 {\ bmod {4}}}$${\ displaystyle p + 1 = 2 ^ {k} n,}$${\ displaystyle k \ in \ mathbb {Z}, k \ geq 2, n}$

Teorema 1. ${\ displaystyle E (\ mathbb {F} _ {p}) = p + 1.}$

Teorema 2. ou dependendo se m é ou não um resíduo quadrático módulo p .${\ displaystyle E (\ mathbb {F} _ {p}) \ cong \ mathbb {Z} _ {2 ^ {k} n}}$${\ displaystyle E (\ mathbb {F} _ {p}) \ cong \ mathbb {Z} _ {2} \ oplus \ mathbb {Z} _ {2 ^ {k-1} n}}$

Teorema 3. Seja Q = ( x , y ) em E tal que x um módulo não residual quadrático p . Então, a ordem de Q é divisível por no grupo cíclico${\ displaystyle 2 ^ {k}}$${\ displaystyle E (\ mathbb {F} _ {p}) \ cong \ mathbb {Z} _ {2 ^ {k} n}.}$

Primeiro, apresentaremos o caso em que n é relativamente pequeno em relação a , e isso exigirá mais um teorema: ${\ displaystyle 2 ^ {k}}$

Teorema 4. Escolha um e suponha ${\ displaystyle \ lambda> 1}$

${\ displaystyle n \ leq {\ frac {\ sqrt {p}} {\ lambda}} \ qquad {\ text {and}} \ qquad \ lambda {\ sqrt {p}}> \ left ({\ sqrt [{ 4}] {p}} + 1 \ direita) ^ {2}.}$

Então p é primo se e somente se existe um Q = ( x , y ) em E , tal que para i = 1, 2, ..., k  - 1 e onde é uma sequência com valor inicial${\ displaystyle \ gcd {(S_ {i}, p)} = 1}$${\ displaystyle S_ {k} \ equiv 0 {\ pmod {p}},}$${\ displaystyle S_ {i}}$${\ displaystyle S_ {0} = x}$

O algoritmo

Fornecemos o seguinte algoritmo, que se baseia principalmente nos Teoremas 3 e 4. Para verificar a primalidade de um determinado número , execute as seguintes etapas: ${\ displaystyle N}$

(1) Escolha tal e encontre tal coisa . ${\ displaystyle x \ in \ mathbb {Z}}$${\ displaystyle \ left ({\ frac {x} {N}} \ right) = - 1}$${\ displaystyle y \ in \ mathbb {Z}, y \ not \ equiv 0 {\ pmod {2}}}$${\ displaystyle \ left ({\ frac {x ^ {3} -y ^ {2}} {N}} \ right) = 1}$

Pegue e . ${\ displaystyle m = {\ frac {x ^ {3} -y ^ {2}} {x}} \ mod N}$${\ displaystyle m \ not \ equiv 0 {\ pmod {N}}}$

Então está ligado . ${\ displaystyle Q '= (x, y)}$${\ displaystyle E: y ^ {2} = x ^ {3} -mx}$

Calcule . Se então for composto, caso contrário, prossiga para (2). ${\ displaystyle Q = nQ '}$${\ displaystyle Q \ in E}$${\ displaystyle N}$

(2) Defina como a sequência com o valor inicial . Calcule para . ${\ displaystyle S_ {i}}$${\ displaystyle Q}$${\ displaystyle S_ {i}}$${\ displaystyle i =}$${\ displaystyle 1,2,3, ..., k-1}$

Se for um , onde então é composto. Caso contrário, vá para (3). ${\ displaystyle \ gcd ({S_ {i}, N})> 1}$${\ displaystyle i}$${\ displaystyle 1 \ leq i \ leq k-1}$${\ displaystyle N}$

(3) Se então for primo. Caso contrário, é composto. Isso completa o teste. ${\ displaystyle S_ {k} \ equiv 0 {\ pmod {N}}}$${\ displaystyle N}$${\ displaystyle N}$

Justificativa do algoritmo

Em (1), uma curva elíptica, E é escolhida, junto com um ponto Q em E , de modo que a coordenada x de Q é um não residual quadrático. Nós podemos dizer

${\ displaystyle \ left ({\ frac {m} {N}} \ right) = \ left ({\ frac {\ frac {x ^ {3} -y ^ {2}} {x}} {N}} \ right) = \ left ({\ frac {x} {N}} \ right) \ left ({\ frac {x ^ {3} -y ^ {2}} {N}} \ right) = - 1 \ cdot 1 = -1.}$

Assim, se N é primo, Q ' tem ordem divisível por , pelo Teorema 3 e, portanto, a ordem de Q' é d | n . ${\ displaystyle 2 ^ {k}}$${\ displaystyle 2 ^ {k} d}$

Isso significa que Q = nQ ' tem ordem . Portanto, se (1) concluir que N é composto, ele realmente é composto. (2) e (3) verifique se Q tem ordem . Assim, se (2) ou (3) concluem que N é composto, ele é composto. ${\ displaystyle 2 ^ {k}}$${\ displaystyle 2 ^ {k}}$

Agora, se o algoritmo conclui que N é primo, isso significa que satisfaz a condição do Teorema 4 e, portanto, N é verdadeiramente primo. ${\ displaystyle S_ {1}}$

Também existe um algoritmo para quando n é grande, porém para isso nos referimos ao artigo mencionado.

Referências

links externos

• Curvas elípticas e prova de primazia por Atkin e Morain.
• Weisstein, Eric W. "Elliptic Curve Primality Proving" . MathWorld .
• Chris Caldwell, "Primality Proving 4.2: Elliptic curves and the ECPP test" at the Prime Pages .
• François Morain, "A página inicial do ECPP" (inclui software ECPP antigo para algumas arquiteturas).
• Marcel Martin, "Primo" (binário para Linux de 64 bits)
• PARI / GP , um sistema de álgebra computacional com funções para criar certificados de primalidade Atkin-Morain e Primo
• GMP-ECPP , uma implementação gratuita de ECPP
• LiDIA , uma biblioteca C ++ gratuita para Linux com suporte ECPP