Universidade Estadual de Londrina

Centro de Tecnologia e Urbanismo

Departamento de Engenharia Eletrica

Decio Luiz Gazzoni Filho

Demonstracoes Distribuıdas de

Carater Primo em Larga Escala

Londrina

2004

Decio Luiz Gazzoni Filho

Demonstracoes Distribuıdas de Carater

Primo em Larga Escala

Monografia apresentada ao curso de Enge-nharia Eletrica da Universidade Estadual deLondrina, como parte dos requisitos obri-gatorios a obtencao do tıtulo de EngenheiroEletricista com enfase em Eletronica.

Orientador:

Prof. Dr. Taufik Abrao

Universidade Estadual de LondrinaCentro de Tecnologia e Urbanismo

Departamento de Engenharia Eletrica

Londrina

2004

Trabalho de Conclusao de Curso sob o tıtulo “Demonstracoes Distribuıdas de Carater

Primo em Larga Escala”, defendida por Decio Luiz Gazzoni Filho e aprovada em 6 de

dezembro de 2004, em Londrina, Parana, pela banca examinada constituıda por:

Prof. Dr. Taufik AbraoDepartamento de Engenharia EletricaUniversidade Estadual de Londrina

Prof. Dr. Marcelo C. TosinDepartamento de Engenharia EletricaUniversidade Estadual de Londrina

Prof. Dr. Ulysses SodreDepartamento de Matematica

Universidade Estadual de Londrina

Dedicatoria

Aos meus pais, pelo apoio, ofereco as curvas elıpticas y2 = x3 +13054261938312812691x+

963383165173305403 e y2 = x3+735926429366195334x+3969032983146139007 e seus res-

pectivos twists quadraticos, que possuem multiplicacao complexa por√−10000129528 e

√−20029259608 e ordens de grupo p + 1± 5476899334 e p + 1± 8134258586, respectiva-

mente, onde p = 264 − 232 + 1.

Agradecimentos

Seja p = 264 − 232 + 1. Todas as curvas elıpticas nesta pagina sao consideradas sobre

Z/pZ.

Aos professores Alfred J. Menezes e Darrel Hankerson, por suas palestras no WCAP’03,

ofereco a curva elıptica y2 = x3 + 8790001982112083917x + 8349894620916661678 e seu

twist quadratico, que possuem multiplicacao complexa por√−1000147768 e ordens de

grupo p + 1± 5376889346.

A Henri Cohen, por seu livro “A Course in Computational Algebraic Number Theory”

e o software PARI/GP, ofereco a curva elıptica y2 = x3 + 10924466306691629096x +

3175821044523403166 e seu twist quadratico, que possuem multiplicacao complexa por√−2001806020 e ordens de grupo p + 1± 1530275008.

A Richard Crandall e Carl Pomerance, pela obra-prima “Prime Numbers: A Computa-

tional Perspective”, fonte de incontaveis horas de estudo, diversao e inspiracao, ofereco

a curva elıptica y2 = x3 + 11517119120719506208x + 13728644060085970144 e seu twist

quadratico, que possuem multiplicacao complexa por√−3006633688 e ordens de grupo

p + 1± 4299605922.

A Donald E. Knuth, por compartilhar seu imenso conhecimento de matematica e ciencia

da computacao atraves da magnıfica obra “The Art Of Computer Programming”, e por

seu sistema TEX de editoracao, ofereco a curva elıptica y2 = x3+10137799566473223720x+

4563733166242538527 e seu twist quadratico, que possuem multiplicacao complexa por√−4004850712 e ordens de grupo p + 1± 7985664922.

Aos ex-colegas da distributed.net, em especial Jeff ‘Bovine’ Lawson, Michael Feiri e Didier

Levet, ofereco a curva elıptica y2 = x3 +8299992258113520866x+17162086221645221008

e seu twist quadratico, que possuem multiplicacao complexa por√−5022511288 e ordens

de grupo p + 1± 4727927074.

A Olivier Atkin e Francois Morain, pelo seminal trabalho “Elliptic Curves and Primality

Proving”, ofereco a curva elıptica y2 = x3+12761264237209647336x+1180621101119968192

e seu twist quadratico, que possuem multiplicacao complexa por√−6005976568 e ordens

de grupo p + 1± 2409633978.

Ao professor Paulo Barreto, pelas vıvidas discussoes sobre o assunto, ofereco a curva

elıptica y2 = x3 +9797964907012185754x+17653939341500267007 e seu twist quadratico,

ii

que possuem multiplicacao complexa por√−7005075940 e ordens de grupo p + 1 ±

912834688.

Aos meus amigos, particularmente Marco Casaroli, Eder Ignatowicz, Leonardo Pinheiro,

Rodrigo Fanucchi e Fernando Ciriaco, assim como outros tantos cujo espaco deste trabalho

e curto demais para conter, ofereco a curva elıptica y2 = x3 + 7384699780321468803x +

3973314206836214173 e seu twist quadratico, que possuem multiplicacao complexa por√−8011737892 e ordens de grupo p + 1± 6252669216.

Ao professor Taufik Abrao, pelas incontaveis horas de orientacao e estimulantes disci-

plinas ministradas no curso, ofereco a curva elıptica y2 = x3 + 4101448666275287283 +

14115872962552252516 e seu twist quadratico, que possuem multiplicacao complexa por√−9003700612 e ordens de grupo p + 1± 3505275976.

A Isis Duarte, pela amizade, ofereco a curva elıptica y2 = x3 + 2610280995158029297x +

5003345793225103561 e seu twist quadratico, que possuem multiplicacao complexa por√−50051763448 e ordens de grupo p + 1± 8523556574.

Prefacio

Este Trabalho de Conclusao de Curso foi elaborado, durante a 5a serie do curso de

Engenharia Eletrica, para satisfazer os requisitos obrigatorios a obtencao do tıtulo de

Engenheiro Eletricista com enfase em Eletronica.

A proposta inicial do trabalho era o desenvolvimento de um software que contem-

plasse todas as etapas necessarias para a realizacao de demonstracoes de carater primo

em sistemas distribuıdos de larga escala (por exemplo, computadores conectados atraves

da Internet). Infelizmente, nao foi possıvel atingir a meta proposta, apesar que grande

parte do codigo cientıfico necessario ao funcionamento rudimentar do sistema foi escrito.

Embora o software necessite de otimizacao, a princıpio e possıvel obter demonstracoes de

carater primo atraves do mesmo, e considera-se que pelo menos parte da meta foi atingida.

O plano inicial para esta monografia e que fosse mais abrangente, cobrindo topicos

como fatoracao de inteiros, aritmetica eficiente de polinomios, sistemas de coordenadas

eficientes para aritmetica elıptica e outros, necessarios a compreensao das tecnicas de oti-

mizacao empregadas no codigo do software. Infelizmente, as normas para elaboracao do

Trabalho de Conclusao de Curso especificam um limite de 40 paginas para os elementos

textuais do trabalho, e este limite comecou a ser observado a partir da posse da nova

coordenacao de Trabalho de Conclusao de Curso em 2004. Apesar de concessoes por

parte da coordenacao, que permitiu a escrita de ate 100 paginas no total (incluindo os

elementos pre- e pos-textuais do trabalho), esse limite se mostrou insuficiente para a es-

crita do trabalho conforme originalmente planejado. Alem dos topicos ja citados no inıcio

do paragrafo, alguns pequenos detalhes tiveram de ser removidos para garantir que o tra-

balho permanecesse dentro do limite: por exemplo, referencias para as demonstracoes dos

teoremas, representando uma economia de 5 paginas, e alguns algoritmos nao considera-

dos absolutamente essenciais para o entendimento do trabalho, mesmo sendo considerados

importantes.

Vale mencionar que a mesma coordenacao do Trabalho de Conclusao de Curso inicial-

mente ofereceu oposicao a escolha do topico deste trabalho, novamente citando uma regra

que estabelece as linhas de pesquisa permitidas. A escrita do trabalho foi possıvel somente

pela persistencia do professor Taufik Abrao, orientador deste trabalho, em lutar pelo meu

direito de tentar contribuir para o conhecimento neste campo, ao inves de escolher um

topico que nao seja de meu interesse e escrever um trabalho medıocre e redundante, um

ii

fenomeno que claramente ocorre com outros alunos do curso. Vale dizer que a publicacao

de um artigo no XXI Simposio Brasileiro de Telecomunicacoes demonstra que o traba-

lho possui contribuicoes e que encaixa-se numa das linhas de pesquisa (telecomunicacoes)

permitidas para o Trabalho de Conclusao de Curso.

Fica registrada nossa discordancia com estas regras arbitrarias impostas pela coor-

denacao do Trabalho de Conclusao de Curso, cujo unico objetivo parece ser o de aleijar

trabalhos como o nosso e garantir a manutencao do status quo de mediocridade do De-

partamento de Engenharia Eletrica.

i

Resumo

O trabalho estuda a viabilidade da computacao de demonstracoes de carater primo emsistemas distribuıdos de larga escala, e descreve uma implementacao parcial do sistemaproposto. Optou-se pelo algoritmo ECPP devido a Atkin e Morain, com otimizacoesdevidas a Shallit, Morain e outros. Entre as contribuicoes do trabalho, estao a propostade uma arquitetura de rede adequada a implementacoes distribuıdas do algoritmo emquestao, alem de melhorias em uma etapa-chave do algoritmo. Resultados obtidos coma implementacao das melhorias sugeridas estabeleceram novos recordes na geracao decurvas elıpticas com multiplicacao complexa.

ii

Abstract

This work analyzes the feasibility of computing primality proofs in large-scale dis-tributed systems, and describes a partial implementation of the proposed system. TheECPP algorithm due to Atkin and Morain, with optimizations due to Shallit, Morainand others, was chosen for the system. Among the contributions of this work, we men-tion a network architecture better suited to distributed implementation of ECPP, andimprovements to a key step of the algorithm. Results obtained with an implementationof the proposed improvements have set new records in the generation of elliptic curveswith complex multiplication.

iii

Sumario

Lista de Sımbolos e Abreviaturas p. xii

1 Introducao p. 1

1.1 Divisao do trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 2

2 Algebra Abstrata e Teoria dos Numeros p. 4

2.1 Teoria de grupos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 4

2.1.1 Definicao e propriedades basicas . . . . . . . . . . . . . . . . . . p. 5

2.1.2 Aplicacoes entre grupos . . . . . . . . . . . . . . . . . . . . . . p. 6

2.1.3 Subgrupos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 7

2.1.4 Grupos e subgrupos cıclicos . . . . . . . . . . . . . . . . . . . . p. 8

2.2 Introducao aos corpos . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 9

2.2.1 Implementacao da aritmetica de corpos finitos . . . . . . . . . . p. 10

2.3 Teoria dos numeros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 11

2.3.1 Divisibilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 11

2.3.2 Numeros primos . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 14

2.3.3 Congruencias e aritmetica modular . . . . . . . . . . . . . . . . p. 15

2.3.4 Polinomios com coeficientes em Z/nZ . . . . . . . . . . . . . . . p. 19

2.3.5 A funcao φ de Euler . . . . . . . . . . . . . . . . . . . . . . . . p. 19

2.3.6 O grupo multiplicativo (Z/nZ)∗ . . . . . . . . . . . . . . . . . . p. 20

2.3.7 Resıduos quadraticos e raızes quadradas modulares . . . . . . . p. 21

3 Curvas Elıpticas p. 26

iv

3.1 Aspectos geometricos . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 26

3.2 O grupo de pontos de uma curva elıptica . . . . . . . . . . . . . . . . . p. 28

3.3 Algoritmos para aritmetica elıptica . . . . . . . . . . . . . . . . . . . . p. 31

3.3.1 Coordenadas afins . . . . . . . . . . . . . . . . . . . . . . . . . p. 32

3.3.2 Coordenadas projetivas . . . . . . . . . . . . . . . . . . . . . . . p. 33

4 O Algoritmo ECPP p. 37

4.1 Testes de carater pseudoprimo . . . . . . . . . . . . . . . . . . . . . . . p. 37

4.1.1 O teste de Fermat e o teste forte . . . . . . . . . . . . . . . . . p. 38

4.1.2 O teste de Frobenius . . . . . . . . . . . . . . . . . . . . . . . . p. 41

4.2 Testes de carater primo eficientes . . . . . . . . . . . . . . . . . . . . . p. 45

4.2.1 O teste n− 1 e variantes . . . . . . . . . . . . . . . . . . . . . . p. 45

4.2.2 O teste ECPP . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 46

4.2.3 Os testes APR-CL e AKS . . . . . . . . . . . . . . . . . . . . . p. 47

4.3 O algoritmo ECPP de Goldwasser e Kilian . . . . . . . . . . . . . . . . p. 48

4.4 Curvas elıpticas com multiplicacao complexa . . . . . . . . . . . . . . . p. 51

4.5 O algoritmo ECPP de Atkin e Morain . . . . . . . . . . . . . . . . . . p. 57

4.6 A variante fastECPP do algoritmo ECPP . . . . . . . . . . . . . . . . . p. 57

5 Sistemas Distribuıdos p. 59

5.1 Distribuindo o algoritmo ECPP . . . . . . . . . . . . . . . . . . . . . . p. 59

5.2 Algoritmos para distribuicao de dados . . . . . . . . . . . . . . . . . . p. 62

5.3 Computacao em ambientes nao-confiaveis . . . . . . . . . . . . . . . . . p. 63

6 Projeto e Implementacao do Sistema p. 67

6.1 Licenciamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 67

6.2 Projeto do sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 68

6.3 Implementacao do sistema . . . . . . . . . . . . . . . . . . . . . . . . . p. 70

v

6.3.1 Aritmetica de inteiros e de ponto flutuante . . . . . . . . . . . . p. 71

6.3.2 Algoritmos para teoria dos numeros . . . . . . . . . . . . . . . . p. 71

6.3.3 Aritmetica de polinomios . . . . . . . . . . . . . . . . . . . . . . p. 73

6.3.3.1 Coeficientes complexos em ponto flutuante . . . . . . . p. 73

6.3.3.2 Coeficientes modulares . . . . . . . . . . . . . . . . . . p. 74

6.3.4 Construcao dos polinomios de classe . . . . . . . . . . . . . . . p. 75

6.3.4.1 Funcoes transcendentais . . . . . . . . . . . . . . . . . p. 77

6.3.5 Aritmetica elıptica . . . . . . . . . . . . . . . . . . . . . . . . . p. 78

7 Resultados p. 79

8 Conclusao p. 82

Anexo A -- Artigo Publicado no XXI Simposio Brasileiro de Telecomu-

nicacoes p. 84

Referencias p. 90

Indice Remissivo p. 93

vi

Lista de Definicoes

1.0.1 Numeros primos e compostos . . . . . . . . . . . . . . . . . . . p. 1

2.1.1 Definicao de grupo . . . . . . . . . . . . . . . . . . . . . . . . . p. 5

2.1.2 Ordem de elementos de um grupo . . . . . . . . . . . . . . . . . p. 6

2.1.3 Ordem de um grupo . . . . . . . . . . . . . . . . . . . . . . . . p. 6

2.1.4 Homomorfismo . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 7

2.1.5 Isomorfismo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 7

2.1.6 Definicao de subgrupo . . . . . . . . . . . . . . . . . . . . . . . p. 7

2.1.7 Definicao de grupo cıclico . . . . . . . . . . . . . . . . . . . . . p. 8

2.2.1 Definicao de corpo . . . . . . . . . . . . . . . . . . . . . . . . . p. 9

2.2.2 Caracterıstica de um corpo . . . . . . . . . . . . . . . . . . . . . p. 10

2.3.1 Definicao de divisibilidade . . . . . . . . . . . . . . . . . . . . . p. 11

2.3.2 Divisor comum e maximo divisor comum . . . . . . . . . . . . . p. 12

2.3.3 Inteiros coprimos ou relativamente primos . . . . . . . . . . . . p. 13

2.3.4 Funcao π(x) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 14

2.3.5 Definicao de congruencia . . . . . . . . . . . . . . . . . . . . . . p. 15

2.3.6 Inverso de uma classe de congruencia . . . . . . . . . . . . . . . p. 17

2.3.7 Funcao φ de Euler . . . . . . . . . . . . . . . . . . . . . . . . . p. 19

2.3.8 Resıduo quadratico . . . . . . . . . . . . . . . . . . . . . . . . . p. 21

2.3.9 Sımbolo de Legendre . . . . . . . . . . . . . . . . . . . . . . . . p. 22

2.3.10 Sımbolo de Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . p. 22

3.1.1 Curva elıptica . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 28

4.1.1 Teste de carater pseudoprimo de Frobenius . . . . . . . . . . . . p. 41

vii

4.4.1 Discriminante fundamental . . . . . . . . . . . . . . . . . . . . . p. 52

4.4.2 Matriz simetrica reduzida . . . . . . . . . . . . . . . . . . . . . p. 53

4.4.3 Grupo de classe . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 53

viii

Lista de Teoremas, Corolarios e

Lemas

1.0.1 Teorema Fundamental da Aritmetica . . . . . . . . . . . . . . . p. 1

2.1.1 Propriedades de grupos . . . . . . . . . . . . . . . . . . . . . . . p. 5

2.1.2 Lei de cancelamento para grupos . . . . . . . . . . . . . . . . . p. 6

2.1.3 Criterio para isomorfismos . . . . . . . . . . . . . . . . . . . . . p. 7

2.1.4 Propriedades de grupos cıclicos . . . . . . . . . . . . . . . . . . p. 8

2.1.5 Isomorfismos de grupos cıclicos . . . . . . . . . . . . . . . . . . p. 8

2.1.6 Propriedades de grupos cıclicos . . . . . . . . . . . . . . . . . . p. 9

2.1.7 Estrutura de subgrupos de um grupo cıclico . . . . . . . . . . . p. 9

2.2.1 Resultados basicos sobre corpos finitos . . . . . . . . . . . . . . p. 10

2.2.2 Teste para raiz primitiva em F∗pk . . . . . . . . . . . . . . . . . . p. 10

2.2.3 Criterio de irredutibilidade de polinomios . . . . . . . . . . . . . p. 11

2.3.1 Algoritmo de divisao . . . . . . . . . . . . . . . . . . . . . . . . p. 11

2.3.2 Propriedades de divisibilidade . . . . . . . . . . . . . . . . . . . p. 12

2.3.3 Lema de Euclides . . . . . . . . . . . . . . . . . . . . . . . . . . p. 12

2.3.4 Solucoes de equacoes diofantinas lineares. . . . . . . . . . . . . . p. 13

2.3.5 Infinitude dos primos . . . . . . . . . . . . . . . . . . . . . . . . p. 14

2.3.6 Teorema dos Numeros Primos . . . . . . . . . . . . . . . . . . . p. 14

2.3.7 Limite superior de fatores primos de um inteiro composto . . . . p. 14

2.3.8 Relacao entre congruencia e divisibilidade . . . . . . . . . . . . p. 15

2.3.9 Axiomas de relacoes de equivalencia para congruencias . . . . . p. 15

ix

2.3.10 Validade da definicao da aritmetica de congruencias . . . . . . . p. 16

2.3.11 Solucoes da congruencia bx ≡ a (mod n) com mdc(b, n) = 1 . . p. 17

2.3.12 Congruencias modulo fatores primos de um inteiro . . . . . . . . p. 18

2.3.13 Teorema Chines do Resto . . . . . . . . . . . . . . . . . . . . . p. 18

2.3.14 Congruencias entre polinomios em Z/nZ . . . . . . . . . . . . . p. 19

2.3.15 Numero de raızes de polinomios sobre Z/nZ . . . . . . . . . . . p. 19

2.3.16 Calculo de φ(n) para n = pe . . . . . . . . . . . . . . . . . . . . p. 19

2.3.17 φ(n) e multiplicativa . . . . . . . . . . . . . . . . . . . . . . . . p. 19

2.3.18 Calculo de φ(n) para n composto . . . . . . . . . . . . . . . . . p. 19

2.3.19 Teorema de Fermat-Euler . . . . . . . . . . . . . . . . . . . . . p. 20

2.3.20 Pequeno Teorema de Fermat . . . . . . . . . . . . . . . . . . . . p. 20

2.3.21 Versao do Teorema de Fermat-Euler sem restricoes sobre mdc(a, n) p. 20

2.3.22 Definicao, comutatividade e ordem de (Z/nZ)∗ . . . . . . . . . . p. 20

2.3.23 Condicao para que (Z/nZ)∗ seja cıclico . . . . . . . . . . . . . . p. 20

2.3.24 Teste para raiz primitiva em (Z/nZ)∗ . . . . . . . . . . . . . . . p. 21

2.3.25 Numero de raızes primitivas de (Z/nZ)∗ . . . . . . . . . . . . . p. 21

2.3.26 Numero de raızes quadradas modulares de Qn ⊆ (Z/nZ)∗ . . . . p. 21

2.3.27 Qn e subgrupo de (Z/nZ)∗ . . . . . . . . . . . . . . . . . . . . . p. 21

2.3.28 Descricao de Qn quando (Z/nZ)∗ e cıclico . . . . . . . . . . . . p. 21

2.3.29 Criterio de Euler para resıduos quadraticos . . . . . . . . . . . . p. 22

2.3.30 Propriedades dos sımbolos de Legendre e Jacobi . . . . . . . . . p. 22

2.3.31 Lei de reciprocidade quadratica . . . . . . . . . . . . . . . . . . p. 23

3.2.1 Grupo de pontos de uma curva elıptica . . . . . . . . . . . . . . p. 29

3.2.2 Estrutura algebrica de E(Fpk) . . . . . . . . . . . . . . . . . . . p. 30

3.2.3 Desigualdade de Hasse para |E(Fpk)| . . . . . . . . . . . . . . . p. 31

4.1.1 Distribuicao dos numeros de Carmichael . . . . . . . . . . . . . p. 39

x

4.1.2 Criterio forte de carater pseudoprimo . . . . . . . . . . . . . . . p. 39

4.1.3 Distribuicao de pseudoprimos fortes . . . . . . . . . . . . . . . . p. 40

4.1.4 Teste de carater pseudoprimo de Lucas . . . . . . . . . . . . . . p. 41

4.1.5 Implementacao do teste de Frobenius usando sequencias de Lucas p. 42

4.1.6 Identidades para implementacao do teste de Frobenius . . . . . p. 43

4.2.1 Teorema de Lucas para demonstracao de carater primo . . . . . p. 45

4.2.2 Teorema de Pocklington sobre fatorizacoes parciais no teste n− 1 p. 45

4.3.1 Teorema de Goldwasser-Kilian . . . . . . . . . . . . . . . . . . . p. 48

4.3.2 Escolha de m no Teorema de Goldwasser-Kilian . . . . . . . . . p. 49

xi

Lista de Algoritmos

2.3.1 Algoritmo de Euclides para calculo do MDC . . . . . . . . . . . p. 12

2.3.2 Algoritmo estendido de Euclides . . . . . . . . . . . . . . . . . . p. 13

2.3.3 Crivo de Eratostenes . . . . . . . . . . . . . . . . . . . . . . . . p. 14

2.3.4 Exponenciacao esquerda-direita . . . . . . . . . . . . . . . . . . p. 16

2.3.5 Sımbolo de Jacobi usando reciprocidade quadratica . . . . . . . p. 23

2.3.6 Raızes quadradas modulares . . . . . . . . . . . . . . . . . . . . p. 24

3.3.1 Determinacao de um ponto sobre uma curva elıptica . . . . . . p. 31

3.3.2 Aritmetica elıptica em coordenadas afins . . . . . . . . . . . . . p. 32

3.3.3 Aritmetica elıptica em coordenadas projetivas . . . . . . . . . . p. 34

4.1.1 Teste de carater pseudoprimo de Fermat . . . . . . . . . . . . . p. 38

4.3.1 ECPP de Goldwasser-Kilian . . . . . . . . . . . . . . . . . . . . p. 49

4.4.1 Determinacao do grupo de classe H(D) . . . . . . . . . . . . . . p. 53

4.4.2 Algoritmo de Cornacchia . . . . . . . . . . . . . . . . . . . . . . p. 55

xii

Lista de Sımbolos e Abreviaturas

AKS Agrawal-Kayal-Saxena (teste de carater primo)

APR-CL Adleman-Pomerance-Rumely Cohen-Lenstra (teste de carater primo)

BSD Berkeley Software Distribution (licenca)

ECDH Elliptic Curve Diffie-Hellman (criptossistema)

ECDSA Elliptic Curve Digital Signature Algorithm

ECM Elliptic Curve Method (algoritmo de fatoracao)

ECPP Elliptic Curve Primality Proving

FFT Fast Fourier Transform (algoritmo)

IEEE Institute of Electrical and Electronics Engineers

GMP GNU Multi-Precision Library

GPL GNU General Public License

RSA Rivest-Shamir-Adleman (criptossistema)

mdc Maximo divisor comum

bxc Piso de x (maior inteiro ≤ x)

dxe Teto de x (menor inteiro ≥ x)

a ≡ b (mod n) a e congruente a b modulo n

G ∼= H G e isomorfo a H

a Classe de congruencia de a

(ap) Sımbolo de Jacobi ou Legendre de a modulo p

[x, y, z] Classe de equivalencia de solucoes projetivas de uma curva elıptica

D Discriminante (teoria de multiplicacao complexa)

n Inteiro

p Primo

pe Potencia de primo

O Ponto no infinito de uma curva elıptica

O(x) Da ordem de x (notacao assintotica)

φ(n) Funcao de Euler

π(x) Funcao de contagem de primos (numero de primos ≤ x)

xiii

(Z/nZ)∗ Grupo multiplicativo dos inteiros modulo n

Z/nZ Grupo aditivo ou corpo/anel dos inteiros modulo n

F Corpo

Fpk Corpo de pk elementos

F∗pk Grupo multiplicativo do corpo de pk elementos

F(ω) Extensao de F por ω

Qn Conjunto dos resıduos quadraticos modulo n

E(F) Curva elıptica sobre FH(D) Grupo de classe do discriminante D

h(D) Numero de classe do discriminante D

a | b a divide b

|x| Ordem de um elemento x de um grupo

|G| Ordem de um grupo G

1

1 Introducao

O problema de distinguir numeros primos de compostos, e de separarnumeros compostos em seus fatores primos, e um dos mais importantese mais uteis problemas de toda a aritmetica . . . A dignidade da cienciaparece exigir que qualquer contribuicao a solucao de um problema taoelegante e celebrado seja ferrenhamente cultivada.

C. F. Gauss, Disquisitiones Arithmeticae (1801), in (1)

Definicao 1.0.1. Um numero primo e um inteiro p > 1 que possui exatamente dois

divisores, 1 e p. Um inteiro positivo que nao seja primo e dito composto, a excecao do

inteiro 1, que e considerado simplesmente uma unidade.

A importancia dos numeros primos para a matematica (e por extensao, para a enge-

nharia e a computacao) pode ser quantificada por um simples teorema:

Teorema 1.0.1 (Teorema Fundamental da Aritmetica). Para cada numero natural

n existe uma fatoracao unica

n = pa11 pa2

2 · · · pakk ,

onde os expoentes ai sao inteiros positivos e p1 < p2 < · · · < pk sao numeros primos.

Crandall e Pomerance (2) reafirmam a importancia dos primos ao interpretarem o

Teorema Fundamental da Aritmetica da seguinte maneira: ‘os primos sao os blocos de

construcao multiplicativos dos numeros naturais’.

Sob o ponto de vista matematico, ambos os problemas citados por Gauss no comeco

do capıtulo ja estao resolvidos desde a Grecia antiga, atraves do procedimento conhe-

cido como Crivo de Eratostenes (2, 3). A teoria da computacao considera o problema

das demonstracoes de carater primo essencialmente resolvido, por conta do algoritmo de

Agrawal, Kayal e Saxena (4), que no jargao da teoria, e dito de complexidade polino-

mial. Para a fatoracao de inteiros, sao conhecidos apenas algoritmos com complexidade

exponencial ou subexponencial, que sao considerados ineficientes – inclusive, esta suposta

2

ineficiencia e a premissa de seguranca de diversos sistemas criptograficos (2, 5), em par-

ticular o sistema RSA.

Na pratica, os algoritmos conhecidos para demonstracao de carater primo deixam a

desejar. Como exemplo, considerando um tempo fixo para cada uma das tarefas a seguir,

e possıvel multiplicar inteiros de bilhoes de dıgitos, verificar o carater pseudoprimo1 de

um inteiro de centenas de milhares de dıgitos, e demonstrar o carater primo de um inteiro

de apenas alguns milhares de dıgitos.

E possıvel argumentar que desvantagens algorıtmicas podem ser compensadas por

avancos de hardware. Embora o orcamento de hardware disponıvel para microprocessa-

dores siga um crescimento exponencial (a chamada Lei de Moore) (6), o crescimento do

poder computacional e limitado por fatores fısicos, economicos e tecnicos, e nao e tao acen-

tuado a ponto de menosprezar os avancos algorıtmicos. A interconexao de computadores,

atraves de barramentos dedicados ou conexoes de rede, surgiu como uma solucao para

as limitacoes inerentes aos sistemas monoprocessados (7). Mais recentemente, diversos

grupos demonstraram ser possıvel aproveitar os recursos computacionais desperdicados

pelos milhoes de computadores conectados a Internet, a rede mundial de computadores,

para realizar computacoes de magnitudes ate entao inimaginaveis (8–10). A proposta

deste trabalho e a construcao de uma rede semelhante, voltada para a demonstracao de

carater primo de inteiros de forma geral.

1.1 Divisao do trabalho

Este capıtulo introdutorio explicou, em termos bastante gerais, a proposta do traba-

lho, incluindo os conceitos basicos necessarios ao entendimento desta proposta.

O Capıtulo 2 expoe alguns resultados da teoria de grupos, teoria de corpos e teoria dos

numeros, necessarios aos desenvolvimentos posteriores. Embora o material seja bastante

elementar, foi incluıdo no trabalho com o objetivo de torna-lo auto-contido.

O Capıtulo 3 e uma introducao as curvas elıpticas, do ponto de vista da teoria com-

putacional dos numeros. Em particular, conceitos topologicos e analıticos relacionados as

curvas elıpticas nao sao abordados.

O Capıtulo 4 introduz o algoritmo ECPP, comparando-o com outros algoritmos para

certificacao de carater primo e pseudoprimo, e justificando sua escolha para uso no traba-

1A definicao de carater pseudoprimo sera dada no Capıtulo 4.

3

lho. E feita tambem uma revisao da principal melhoria ao algoritmo descrita na literatura,

a variante fastECPP.

O Capıtulo 5 discute as modificacoes ao ECPP para torna-lo um algoritmo distribuıdo,

o uso de estruturas hierarquicas de rede para distribuicao de dados de maneira eficiente

em sistemas distribuıdos, e os desafios de realizar computacoes validas em uma rede de

computadores cuja confiabilidade nao pode ser garantida.

O Capıtulo 6 discute a implementacao do sistema. Inicialmente justifica-se a decisao

de tornar o sistema um software livre sob licenca GPL, e o impacto desta decisao sobre

a infraestrutura utilizada, em particular as bibliotecas empregadas na construcao do sis-

tema. A seguir, sao descritas as metas de projeto do sistema, e o restante do capıtulo

e dedicado a descricao da implementacao, no estagio em que se encontrava quando da

publicacao deste trabalho.

O Capıtulo 7 relata alguns resultados obtidos ate o momento da escrita do trabalho,

que estabeleceram novos recordes em uma das etapas mais complexas do algoritmo ECPP.

O Capıtulo 8 conclui o trabalho e indica direcoes futuras de pesquisa.

O anexo A e uma reproducao do artigo ‘Demonstracoes Distribuıdas de Carater

Primo’, publicado pelo autor e seu orientador, Prof. Dr. Taufik Abrao, no XXI Simposio

Brasileiro de Telecomunicacoes, realizado em Belem – PA no perıodo de 6 a 9 de setembro

de 2004.

4

2 Algebra Abstrata e Teoria dosNumeros

Esta dissertacao trata do algoritmo ECPP, que envolve conceitos de curvas elıpticas.

A teoria destas curvas, pelo menos no contexto da teoria computacional dos numeros,

exige familiaridade com certos conceitos da algebra abstrata, em particular grupos e cor-

pos. Estes assuntos compreendem a primeira e segunda parte deste capıtulo. A terceira

parte trata da teoria dos numeros, que e fundamental tanto para o problema abordado

por este trabalho (demonstracoes de carater primo), quanto na implementacao dos al-

goritmos utilizados. Os assuntos sao abordados superficialmente, omitindo resultados

desnecessarios ao desenvolvimento do trabalho.

A primeira secao trata da teoria de grupos. Partem-se de definicoes e proprieda-

des basicas, para entao introduzir mapeamentos entre grupos, seguido pela nocao de

subgrupo, concluindo com a importante classe de grupos e subgrupos cıclicos. A segunda

secao aborda resultados simples sobre corpos finitos, e a implementacao de sua aritmetica.

A ultima secao do capıtulo e uma compilacao de resultados da teoria dos numeros. O pri-

meiro assunto tratado e a divisibilidade. Em seguida, ha alguns resultados sobre numeros

primos e sua distribuicao entre os inteiros. O proximo topico e um tratamento breve de

aritmetica modular e congruencias. A seguir, sao expostos alguns resultados simples sobre

a aritmetica de polinomios com coeficientes modulares. A funcao φ de Euler e introdu-

zida, e alguns teoremas relacionados a esta funcao sao fornecidos. E feito um estudo do

grupo multiplicativo dos inteiros modulo n, e conclui-se o capıtulo com os conceitos de

residuosidade quadratica e raızes quadradas modulares.

2.1 Teoria de grupos

Os resultados da teoria de grupos sao extremamente importantes para a aborda-

gem das curvas elıpticas no contexto da teoria dos numeros. Ademais, interpretacoes

5

de resultados da teoria dos numeros (como o Pequeno Teorema de Fermat 2.3.20 e sua

generalizacao, o Teorema de Fermat-Euler 2.3.19) em termos da teoria de grupos, e um

caminho produtivo para a criacao de algoritmos mais eficientes; em certos algoritmos, e

possıvel substituir o grupo multiplicativo (Z/pZ)∗ por outros grupos mais vantajosos, dos

quais o grupo de pontos de uma curva elıptica esta mais em voga atualmente.

Muitos resultados acerca de grupos infinitos serao omitidos, mesmo havendo analogia

direta com os resultados para grupos finitos, por serem irrelevantes ao trabalho.

2.1.1 Definicao e propriedades basicas

A definicao de um grupo e simples (11):

Definicao 2.1.1. Um grupo e um conjunto G e uma operacao binaria × : G → G, que

satisfazem os seguintes axiomas:

1. Fechamento: para todo a, b ∈ G, ab ∈ G;

2. Associatividade: (ab)c = a(bc) para todo a, b, c ∈ G;

3. Existencia de identidade: existe um elemento 1 ∈ G, dito a identidade de G, tal

que para todo a ∈ G vale que a1 = 1a = a;

4. Existencia de inversos: para cada a ∈ G, existe um elemento a−1 ∈ G, dito o

inverso de a, tal que aa−1 = a−1a = 1.

Adicionalmente, o grupo pode satisfazer o seguinte axioma:

5. Comutatividade: ab = ba para todo a, b ∈ G.

Nesse caso, o grupo e dito abeliano.

Na definicao, foi empregada uma notacao multiplicativa para o grupo. Tambem e

possıvel utilizar uma notacao aditiva, em que a operacao × e substituıda por +, a iden-

tidade 1 por 0 e os inversos a−1 pelos opostos −a. De fato, e possıvel empregar qualquer

notacao desejada, principalmente se corresponder a notacao tradicional para aquele grupo.

Algumas propriedades dos grupos podem ser obtidas diretamente da definicao acima:

Teorema 2.1.1. Se G e um grupo com operacao ×, entao

1. a identidade de G e unica;

6

2. para todo a ∈ G, o elemento inverso a−1 e unico;

3. (a−1)−1 = a para todo a ∈ G;

4. (ab)−1 = (b−1)(a−1);

5. dados a1, a2, . . . , an ∈ G, o valor de a1a2 · · · an e independente da forma como sao

colocados parenteses na expressao (a chamada lei de associatividade generalizada).

Devido a lei de associatividade generalizada, o valor do produto xx · · ·x︸ ︷︷ ︸n vezes

nao depende

da ordem de avaliacao, e sera denotado simplesmente por xn. De forma semelhante,

x−1x−1 · · ·x−1︸ ︷︷ ︸n vezes

e escrito como x−n, e x0 = 1.

O seguinte teorema estabelece a existencia de cancelamento em grupos:

Teorema 2.1.2. Seja G um grupo com a, b ∈ G. As equacoes ax = b e ya = b apresentam

solucoes unicas x, y ∈ G. Em particular, as leis de cancelamento pela esquerda e pela

direita sao validas em G, ou seja,

1. se au = av, entao u = v;

2. se ub = vb, entao u = v.

O seguinte conceito e importantıssimo no estudo da teoria de grupos.

Definicao 2.1.2. Seja G um grupo e x ∈ G. Define-se a ordem de x como o menor inteiro

positivo tal que xn = 1, e denota-se este inteiro por |x|, e diz-se que x possui ordem n. Se

nenhuma potencia positiva de x corresponde a identidade, define-se a ordem de x como

infinito.

E possıvel falar tambem na ordem do grupo como um todo.

Definicao 2.1.3. Seja G um grupo. A ordem do grupo e a cardinalidade do conjunto

associado ao grupo, e e denotada por |G|.

2.1.2 Aplicacoes entre grupos

As aplicacoes entre grupos possuem uma notacao propria.

7

Definicao 2.1.4. Sejam G e H dois grupos. Uma aplicacao ϕ : G → H tal que

ϕ(xy) = ϕ(x)ϕ(y), para todo x, y ∈ G

e dita um homomorfismo.

Observa-se que na equacao da Definicao 2.1.4, a operacao no lado esquerdo e realizada

em G, enquanto a operacao no lado direito e realizada em H. Intuitivamente falando, um

homomorfismo respeita as estruturas de grupo entre o domınio e o contradomınio.

Definicao 2.1.5. Uma aplicacao ϕ : G → H e dita um isomorfismo, e G e H sao ditos

isomorfos, se

1. ϕ e um homomorfismo;

2. ϕ e uma bijecao.

Se G e H sao isomorfos, escreve-se G ∼= H.

Um isomorfismo entre dois grupos e uma bijecao que preserva as operacoes de grupo.

Intuitivamente falando, G e H sao o mesmo grupo, exceto que a representacao dos ele-

mentos e da operacao de cada grupo pode ser diferente.

E possıvel demonstrar que dois grupos nao sao isomorfos se o seguinte criterio nao for

satisfeito (11):

Teorema 2.1.3. Um mapeamento ϕ : G → H e um isomorfismo se

1. |G| = |H|

2. G e abeliano se e somente se H e abeliano

3. para todo x ∈ G, |x| = |ϕ(x)|

2.1.3 Subgrupos

Alguns grupos possuem subconjuntos que, por si so, satisfazem os axiomas de grupo.

Tais subconjuntos sao ditos subgrupos do grupo original.

Definicao 2.1.6. Seja G um grupo. Um subconjunto H de G e um subgrupo de G se H

possuir pelo menos um elemento, e se dados dois elementos x, y ∈ H,

8

1. xy ∈ H;

2. x−1 ∈ H.

Se H e um subgrupo de G, emprega-se a notacao H ≤ G, ou H < G caso H 6= G.

2.1.4 Grupos e subgrupos cıclicos

Uma classe muito importante de grupos sao os chamados grupos cıclicos.

Definicao 2.1.7. Um grupo G e cıclico se G pode ser gerado pelas potencias de um

unico elemento, ou seja, existe x ∈ G tal que G = {xn | n ∈ Z}. A notacao G = 〈x〉 e

empregada para indicar que G e gerado por x.

Em geral, um grupo cıclico possui mais de um gerador. Por exemplo, se x e um gerador

de G, entao x−1 tambem e (11). Usando propriedades de expoentes e a comutatividade

dos inteiros, e possıvel mostrar que grupos cıclicos devem ser abelianos.

O seguinte teorema fornece algumas propriedades importantes de grupos cıclicos.

Teorema 2.1.4. Seja G um grupo cıclico finito gerado por x. Sao validas as seguintes

propriedades:

1. |G| = |x|;

2. se |G| = n, entao xn = 1 e 1, x, x2, . . . , xn−1 sao elementos distintos de G.

Em grupos cıclicos finitos, e possıvel utilizar a relacao xn = 1, onde n = |G|, para

reduzir expoentes k ≥ n para a faixa 0 ≤ x < n por divisao Euclidiana, onde o divisor e a

ordem do grupo n. Este procedimento sugere que e possıvel utilizar as leis de expoentes e a

aritmetica do grupo aditivo Z/nZ para realizar aritmetica em G. Isto nao e coincidencia;

o teorema a seguir estabelece isomorfismos entre grupos cıclicos, dos quais Z/nZ sob

adicao e um exemplo.

Teorema 2.1.5. Dois grupos cıclicos quaisquer de mesma ordem sao isomorfos. Especi-

ficamente, se n ∈ Z+, e 〈x〉, 〈y〉 sao dois grupos cıclicos de ordem n, entao o mapeamento

ϕ : 〈x〉 →〈y〉

xk 7→yk

e bem definido e e um isomorfismo.

9

O seguinte teorema estabelece propriedades adicionais de grupos cıclicos e seus gera-

dores.

Teorema 2.1.6. Seja G um grupo cıclico finito, x ∈ G e a 6= 0 um inteiro.

1. Se |x| = n, entao |xa| = n/ mdc(n, a);

2. Em particular, se a divide n, entao |xa| = n/a;

3. Se G = 〈x〉, entao G = 〈xa〉 se e somente se mdc(n, a) = 1, o que tambem implica

que o numero de geradores de G e φ(n), onde φ(n) e a funcao de Euler da Definicao

2.3.7.

E possıvel desvendar a estrutura completa dos subgrupos de um grupo cıclico atraves

do seguinte teorema.

Teorema 2.1.7. Seja G = 〈x〉 um grupo cıclico.

1. Todo subgrupo de G e cıclico. Mais especificamente, se K ≤ H, entao K = {1} ou

K = 〈xd〉, onde d e o menor inteiro positivo tal que xd ∈ K.

2. Se |G| = n, os divisores d de n estao em correspondencia bijetiva com os subgrupos

de G: para cada d | n existe um unico subgrupo de G de ordem d, gerado por xn/d.

2.2 Introducao aos corpos

Definicao 2.2.1. Um corpo F e um conjunto e duas operacoes binarias associadas,

+ : F → F e × : F → F (ditas adicao e multiplicacao), que satisfazem os seguintes

axiomas, onde a e b denotam dois elementos quaisquer do grupo em questao:

1. Comutatividade: a + b = b + a e ab = ba;

2. Associatividade: (a + b) + c = a + (b + c) e (ab)c = a(bc);

3. Distributividade: a(b + c) = ab + ac e (a + b)c = ac + bc;

4. Existencia de identidades, onde 0 denota a identidade aditiva e 1 a identidade

multiplicativa: a + 0 = 0 + a = a e a1 = 1a = a;

5. Existencia de inversos, onde −a indica o inverso sob adicao e a−1 o inverso sob

multiplicacao: a + (−a) = (−a) + a = 0 e aa−1 = a−1a = 1 se a 6= 0.

10

Alguns sistemas numericos tradicionais sao corpos: o conjunto dos numeros racionais

Q, dos numeros reais R e dos numeros complexos C. Ja o conjunto dos numeros inteiros

Z nao forma um corpo, por nao atender ao item 5 da definicao.

Definicao 2.2.2. Seja um corpo F com identidade multiplicativa 1 e identidade aditiva

0. Se existe n tal que n · 1 = 0, e este e o menor valor que satisfaz esta propriedade,

entao o corpo e dito de caracterıstica n. Caso nao exista n que satisfaca a propriedade, a

caracterıstica do corpo e 0.

Corpos de caracterıstica n 6= 0 sao ditos corpos finitos, e sao os corpos mais interessan-

tes do ponto de vista computacional. Algumas propriedades dos corpos finitos, retiradas

de (2), sao dadas a seguir.

Teorema 2.2.1 (Resultados basicos sobre corpos finitos).

1. A caracterıstica de um corpo finito F, ch(F), e um numero primo;

2. Todos os corpos finitos possuem pk elementos, onde k e um inteiro positivo e p e a

caracterıstica do corpo;

3. Para um dado primo p e inteiro positivo k, existe exatamente um corpo com pk

elementos (a menos de isomorfismo1), que sera denotado por Fpk ;

4. O grupo multiplicativo F∗pk de elementos nao-nulos de Fpk e cıclico.

Pelo Teorema 2.1.6, o grupo F∗pk apresenta φ(pk − 1) geradores, que no contexto deste

grupo, tambem recebem o nome de raızes primitivas.

Raızes primitivas podem ser obtidas atraves do seguinte criterio (2):

Teorema 2.2.2 (Teste para raiz primitiva em F∗pk). Um elemento g de F∗

pk e uma

raiz primitiva se e somente se

gpk−1

q 6= 1

para todo primo q | pk − 1.

2.2.1 Implementacao da aritmetica de corpos finitos

A maneira classica de realizar aritmetica de corpos finitos e atraves de aritmetica

modular de inteiros e polinomios.

1Dois corpos sao ditos isomorfos quando ha uma bijecao entre eles, de modo que ambos possuem amesma estrutura algebrica.

11

Inicialmente observa-se que um corpo de caracterıstica p e que possui p elementos e

isomorfo ao corpo dos inteiros modulo p, Z/pZ (2). Desse modo, a aritmetica de Fp pode

ser realizada atraves da aritmetica modulo p.

Ja corpos de caracterıstica p e que possuem pk elementos correspondem a extensoes

de Fp. Nesse caso, em uma transposicao direta da teoria (11), os elementos de Fpk sao

polinomios com coeficientes provindos de Fp, e a aritmetica desses polinomios e realizada

modulo um polinomio irredutıvel qualquer de grau k (2, 3). Polinomios irredutıveis podem

ser obtidos a partir do criterio a seguir.

Teorema 2.2.3 (Criterio de irredutibilidade de polinomios). Um polinomio f(x)

em Fp[x] de grau k e irredutıvel se e somente se mdc(f(x), xpj − x) = 1, para j =

1, 2, . . . , bk/2c.

Observa-se que a escolha do polinomio irredutıvel de grau k no paragrafo acima e

imaterial, visto que todos os corpos de pk elementos sao isomorficos entre si; a escolha do

polinomio afeta apenas a representacao dos elementos.

Em princıpio, a aritmetica modular, tanto de inteiros como de polinomios, pode ser

realizada atraves das operacoes inteiras e polinomiais comuns, seguidas de uma divisao

pelo modulo, em que o resto da divisao caracteriza o resultado da operacao modular (3).

Divisoes sao realizadas na forma de multiplicacao pelo inverso modular, que pode ser

computado pelo algoritmo estendido de Euclides (Algoritmo 2.3.2). Vale observar que

existem diversos algoritmos mais eficientes para estas tarefas, particularmente quando o

tamanho dos operandos e suficientemente grande (2).

2.3 Teoria dos numeros

2.3.1 Divisibilidade

O ponto de partida da teoria dos numeros e o chamado algoritmo de divisao, ou

divisao Euclidiana.

Teorema 2.3.1. Se a e b sao inteiros e b > 0, entao existem, e sao unicos, inteiros q e

r tais que

a = qb + r e 0 ≤ r < b.

Definicao 2.3.1. Se a e b sao inteiros quaisquer, e a = qb para algum inteiro q, entao

diz-se que b divide a, ou reciprocamente, que a e multiplo de b. Emprega-se a notacao

b | a para indicar que b divide a, e b - a para indicar que b nao divide a.

12

Como consequencia da definicao, observa-se que qualquer inteiro divide 0 (uma vez

que 0 = 0b para qualquer valor de b), que 1 divide qualquer inteiro, e que todo inteiro

divide a si mesmo.

Alguns resultados sobre divisibilidade sao dados a seguir.

Teorema 2.3.2.

1. se a | b e b | c, entao a | c;

2. se a | b e c | d, entao ac | bd;

3. se m 6= 0, entao a | b se e somente se ma | mb;

4. se d | a e a 6= 0, entao |d| ≤ |a|;

5. se c divide a1, . . . , ak, entao c divide a1u1 + . . . + akuk para quaisquer inteiros

u1, . . . , uk.

6. a | b e b | a se e somente se a = ±b.

Definicao 2.3.2. Se d | a e d | b, diz-se que d e um divisor comum de a e b. Dentre os

divisores comuns de dois (ou mais) inteiros, ha um de maior valor; este e dito o maximo

divisor comum (MDC).

O calculo do MDC de dois inteiros pode ser feito, de maneira ingenua, pela listagem

dos divisores dos inteiros em questao, seguido da busca pelo maior elemento em comum

entre as duas listas. Infelizmente, este algoritmo e extremamente ineficiente, pois exige a

fatoracao de seus argumentos. Um algoritmo mais eficiente e conhecido desde a Grecia

antiga, o chamado algoritmo de Euclides, considerado o primeiro algoritmo da historia,

e possivelmente o mais importante algoritmo da teoria dos numeros. Seu princıpio de

funcionamento e baseado no lema a seguir.

Lema 2.3.3. Se a = qb + r, entao mdc(a, b) = mdc(b, r).

De posse desse lema, a obtencao do algoritmo e trivial.

Algoritmo 2.3.1 (Algoritmo de Euclides). Dados dois inteiros nao-negativos a e b,

o algoritmo calcula o maximo divisor comum dos dois.

1. [Laco de Euclides]

while (b 6= 0) {

13

r = a mod b;

a = b;

b = r;

}return r;

O tempo de execucao deste algoritmo, se programado com cuidado, e O(log2 n

),

onde n = max(a, b) (1). Existem tambem variantes do algoritmo, cuja implementacao em

computadores binarios e mais eficiente (1).

Definicao 2.3.3. Dois inteiros a e b sao ditos coprimos (ou relativamente primos) se

mdc(a, b) = 1.

O teorema a seguir sera utilizado na secao sobre aritmetica modular.

Teorema 2.3.4. Sejam a, b, c inteiros, onde a, b nao sao simultaneamente nulos, e seja

d = mdc(a, b). Entao a equacao

ax + by = c

possui solucao inteira para x, y se e somente se d | c, e nesse caso existem infinitas

solucoes, dadas pelos pares

x = x0 +bn

d, y = y0 −

an

d,

onde x0, y0 e uma solucao particular qualquer e n ∈ Z.

Solucoes particulares desta equacao podem ser encontradas pelo chamado algoritmo

estendido de Euclides (1, 2).

Algoritmo 2.3.2 (Algoritmo estendido de Euclides). Dados inteiros a e b tais que

a ≥ b ≥ 0 e a > 0, o algoritmo retorna a tripla de inteiros (x, y, c) tais que ax + by = c =

mdc(a, b).

1. [Inicializacao]

(x,y,c,u,v,w) = (1,0,a,0,1,b);

2. [Laco de Euclides]

while (w > 0) {q = dc/we;

14

(x, y, c, u, v, w) = (u, v, w, x− qu, y − qv, c− qw);

}return (x, y, c);

Assintoticamente, o tempo de execucao deste algoritmo e o mesmo do algoritmo de

Euclides para MDC.

2.3.2 Numeros primos

A definicao de numero primo e o importante resultado acerca dos mesmos, denominado

Teorema Fundamental da Aritmetica, ja foi abordado no Capıtulo 1. Esta secao preocupa-

se apenas com a distribuicao dos primos entre os inteiros, e com algoritmos rudimentares

para determinacao de carater primo e composto.

Teorema 2.3.5. Existem infinitos numeros primos.

Definicao 2.3.4. A funcao π(x) denota o numero de primos p ≤ x.

Teorema 2.3.6. Para x →∞,

π(x) ∼ x

log x

O seguinte criterio permite determinar o carater primo de inteiros pequenos.

Lema 2.3.7. Um inteiro n > 1 e composto se e somente se n e divisıvel por algum primo

p ≤√

n.

Em determinadas situacoes, e preciso compilar uma lista de primos entre 1 e n, para

algum valor de n. Embora seja possıvel aplicar o lema acima de maneira independente a

cada inteiro de 1 a n, existe um algoritmo para compilacao desta lista que e mais eficiente,

o Crivo de Eratostenes.

Algoritmo 2.3.3 (Crivo de Eratostenes). Dado um inteiro n > 1, este algoritmo

retorna um vetor binario p[2..n], tal que se k e composto, p[k] = 0, e se k e primo,

p[k] = 1.

1. [Inicializacao]

// Pelo Lema 2.3.7, os elementos de 1 a n nao

// possuem fatores primos maiores que d√

nel = d

√ne;

p[2..n] = 1;

i = 2;

15

2. [Laco principal]

while (i ≤ l) {// Multiplos de i sao compostos por definicao

for (j = 2i; j < n; j = j + i)

p[j] = 0;

// Procura proximo primo no vetor

for (i + +; p[i] = 1; i + +)

;

}return p;

Pode-se mostrar (2) que o tempo de execucao desse algoritmo e O(n log log n); visto

de outra maneira, o custo amortizado do algoritmo para cada inteiro na faixa de 1 a n

e O(log log n). Ainda assim, esse custo e muito alto, exceto para pequenos valores de n

(ate 10 ou 11 dıgitos).

2.3.3 Congruencias e aritmetica modular

Definicao 2.3.5. Seja n um inteiro positivo, e a, b dois inteiros quaisquer. Diz-se que a e

congruente a b modulo n, e escreve-se a ≡ b (mod n), se a e b apresentam o mesmo resto

apos divisao por n.

Teorema 2.3.8. Para um dado n ≥ 1, temos que a ≡ b (mod n) se e somente se n |(a− b).

Lema 2.3.9. Para um dado n ≥ 1, temos que

1. a ≡ a (mod n) para todos os inteiros a;

2. se a ≡ b (mod n), entao b ≡ a (mod n);

3. se a ≡ b (mod n) e b ≡ c (mod n), entao a ≡ c (mod n).

Este lema estabelece que a congruencia e uma relacao de equivalencia, por satisfazer

os axiomas de reflexividade, simetria e transitividade. Assim, Z e particionado em classes

de equivalencia disjuntas, representadas pelas classes de congruencia

a = {b ∈ Z | a ≡ b (mod n)}.

16

Cada classe corresponde aos possıveis restos r = 0, 1, . . . , n − 1 da divisao de um

inteiro por n, de modo que ha n classes de congruencia, mais especificamente

0 = {. . . ,−2n,−n, 0, n, 2n, . . .}.

1 = {. . . ,−2n + 1,−n + 1, 1, n + 1, 2n + 1, . . .},

. . .

n− 1 = {. . . ,−n− 1,−1, n− 1, 2n− 1, 3n− 1, . . .}.

O conjunto de classes de equivalencia modulo n e denotado por Z/nZ. E possıvel

definir uma aritmetica desse conjunto da seguinte forma:

a + b = a + b,

a− b = a− b,

ab = ab.

O lema a seguir afirma que essas operacoes sao bem-definidas.

Lema 2.3.10. Para um dado n ≥ 1, se a′ ≡ a (mod n) e b′ ≡ b (mod n), entao a′ + b′ ≡a + b (mod n), a′ − b′ ≡ a− b (mod n) e a′b′ ≡ ab (mod n).

O conjunto Z/nZ e as operacoes aritmeticas assim definidas formam um anel (quando

n nao e primo ou potencia de primo) ou um corpo.

Deve-se prestar atencao a definicao de exponenciacao. Aplicando a definicao de mul-

tiplicacao de classes de congruencia, obtem-se ak = ak. Deve-se observar que, em geral,

ak 6= ak; mas nem tudo esta perdido com relacao ao calculo eficiente de exponenciacoes.

Sera visto mais a frente que, de fato, e possıvel efetuar reducoes modulares neste expoente,

desde que se escolha o modulo correto pelo uso do Teorema 2.3.19.

Embora, a primeira vista, operacoes de exponenciacao ak (sejam exponenciacoes mo-

dulares ou nao) parecam exigir k−1 multiplicacoes, existem algoritmos que exigem apenas

O(log k) multiplicacoes. A literatura sobre estes algoritmos e rica (bons pontos de par-

tida sao (1, 5)), mas neste capıtulo mencionamos apenas um dos algoritmos mais simples,

conhecido como exponenciacao esquerda-direita. Decidiu-se abordar este algoritmo, ao

inves de sua versao simetrica direita-esquerda, por haver uma certa vantagem na situacao

em que a e um inteiro pequeno como 2 ou 3, em que e possıvel substituir a operacao de

multiplicacao por a por adicoes.

17

Algoritmo 2.3.4 (Exponenciacao esquerda-direita). Esse algoritmo calcula ak, k >

0, onde k e fornecido ao algoritmo na forma de um vetor de 0 a D − 1 contendo sua

expansao binaria, com k[D − 1] = 1 o bit mais significativo.

1. [Inicializacao]

z = a;

2. [Laco sobre os bits de k, a partir do segundo mais significativo]

for (D − 2 ≥ j ≥ 0) {z = z2;

if (k[j] == 1)

z = za;

}return z;

Para o calculo de exponenciacoes modulares, o algoritmo sera mais eficiente se as

operacoes de multiplicacao forem seguidas por reducoes modulares, mantendo os valores

das variaveis estritamente menores que o modulo.

A divisao de classes de congruencia nao pode ser definida como a/b = a/b, visto

que a/b nao necessariamente assume valor inteiro. Ao inves disso, serao consideradas

as solucoes da equacao bx ≡ a (mod n). Pelo Teorema 2.3.8, isso equivale a dizer que

n | (bx− a), ou seja, bx− a = ny. Equacoes deste tipo ja foram estudadas pelo Teorema

2.3.4, e suas solucoes podem ser obtidas de maneira eficiente pelo Algoritmo 2.3.2. Um

corolario do Teorema 2.3.4, empregando os conceitos de congruencia, e util nesta situacao:

Corolario 2.3.11. Se mdc(b, n) = 1, entao as solucoes da congruencia bx ≡ a (mod n)

para x formam uma unica classe de congruencia modulo n.

Esse corolario indica as situacoes em que faz sentido definir o quociente de classes de

congruencia; especificamente, quando o divisor b e coprimo ao modulo n. Quando esta

condicao nao e verdadeira, e d | a, ha mais de uma solucao para a congruencia, enquanto

se d - a, a congruencia nao possui solucao. Em ambos os casos, nao e possivel definir um

quociente a/b.

Uma definicao de amplo uso, e relacionada aos quocientes de classe de congruencia, e

a inversao de classes de congruencia.

Definicao 2.3.6. O inverso a−1 de uma classe de congruencia a modulo n e a solucao x

da equacao ax = 1, ou na notacao da aritmetica modular, ax ≡ 1 (mod n).

18

Apos este breve interludio ao topico de divisao de classes de congruencia, retornamos

ao estudo da aritmetica destas classes. O Lema 2.3.10 pode ser interpretado da seguinte

maneira: a aritmetica de classes de congruencia depende apenas das classes de congruencia

em questao, e nao do representante particular escolhido para aquela classe. Surge entao

a questao de como escolher os representantes mais adequados para maximizar a eficiencia

da implementacao da aritmetica modular. As duas possibilidades mais comuns sao o

conjunto de resıduos nao-negativos mınimos, dado por {0, 1, . . . , n − 1}, e o conjunto de

resıduos de menor valor absoluto, dado por {0,±1,±2, . . . ,±(n − 1)/2} para n ımpar e

{0,±1,±2, . . . ,±(n/2− 1), n/2} para n par (o ultimo elemento pode ser substituıdo por

−n/2 se desejado).

As definicoes e resultados obtidos ate agora sugerem a implementacao da aritmetica

modular atraves da aritmetica de inteiros e aplicacao do algoritmo de divisao. Existe um

sistema alternativo de aritmetica modular para o caso em que n e composto (1, 5). Para

introduzi-lo, e necessario o teorema a seguir.

Teorema 2.3.12. Seja n um inteiro com fatoracao em potencias de primos

n = pe11 · · · pek

k ,

onde p1, . . . , pk sao primos distintos. Dados inteiros a e b, temos que a ≡ b (mod n) se e

somente se a ≡ b (mod peii ) para i = 1, . . . , k.

Este resultado, em conjunto com o Lema 2.3.10, sugere a realizacao da aritmetica

modulo os diferentes fatores primos de n; esse procedimento pode ser vantajoso em al-

gumas situacoes. E necessario, no entanto, um metodo para obtencao da classe de con-

gruencia modulo n dadas as classes de congruencia modulo cada fator primo de n. O

seguinte teorema garante a existencia e unicidade da solucao para esse problema.

Teorema 2.3.13 (Teorema Chines do Resto). Sejam n1, . . . , nk inteiros positivos tais

que mdc(ni, nj) = 1 para i 6= j, e sejam a1, . . . , ak inteiros quaisquer. Entao a solucao

das congruencias simultaneas

x ≡ a1 (mod n1), . . . , x ≡ ak (mod nk)

forma uma unica classe de congruencia modulo n, onde n = n1 · · ·nk. Ademais, esta

solucao e dada por

x ≡k∑

i=1

aicidi (mod n)

19

onde ci = n/ni e di ≡ c−1i (mod ni). Z/nZ

2.3.4 Polinomios com coeficientes em Z/nZ

A definicao de uma aritmetica de Z/nZ permite a construcao de polinomios com

coeficientes provindos desse corpo. O lema a seguir afirma que, de certa forma, tais

polinomios se comportam como esperado.

Lema 2.3.14. Seja f = f(x) um polinomio com coeficientes inteiros, e n ≥ 1. Se

a ≡ b (mod n), entao f(a) ≡ f(b) (mod n).

O numero de raızes de polinomios sobre Z/nZ e fornecido pelo teorema a seguir, devido

a Lagrange, e corresponde ao resultado familiar conhecido como Teorema Fundamental

da Algebra.

Teorema 2.3.15. Seja p um primo, e f(x) = adxd + . . . + a1x + a0 um polinomio com

coeficientes inteiros, com ai 6≡ 0 (mod p) para pelo menos um valor de i. Entao a con-

gruencia f(x) ≡ 0 (mod p) e satisfeita por nao mais que d classes de congruencia de

Z/nZ.

2.3.5 A funcao φ de Euler

Definicao 2.3.7. A funcao φ = φ(n) indica o numero de inteiros 1 ≤ a < n coprimos a

n.

Lema 2.3.16. Se n = pe com p primo e e natural, entao

φ(n) = pe − pe−1 = pe−1(p− 1) = n

(1− 1

p

).

Teorema 2.3.17. Se m e n sao coprimos, entao φ(mn) = φ(m)φ(n).

Juntando o Lema 2.3.16 e o Teorema 2.3.17, e possıvel calcular φ(n) para qualquer

valor inteiro de n.

Corolario 2.3.18. Se a fatoracao de n em potencias de primos e n = pe11 · · · pek

k , entao

φ(n) =k∏

i=1

(peii − pei−1

i ) =k∏

i=1

pei−1i (pi − 1) = n

k∏i=1

(1− 1

pi

).

20

Este resultado pode ser escrito de forma mais concisa como

φ(n) = n∏p|n

(1− 1

p

).

O teorema a seguir e o resultado mais importante envolvendo a funcao de Euler.

Teorema 2.3.19 (Teorema de Fermat-Euler). Se mdc(a, n) = 1, entao

aφ(n) ≡ 1 (mod n).

Um corolario importante contempla o caso em que n e primo.

Teorema 2.3.20 (Pequeno Teorema de Fermat). Se p e primo e a 6≡ 0 (mod p),

entao

ap−1 ≡ 1 (mod p).

Se, no Teorema 2.3.19 a restricao mdc(a, n) = 1 nao puder ser garantida, entao e

necessario se contentar com o seguinte resultado.

Teorema 2.3.21. Para qualquer inteiro a, aφ(n)+1 ≡ a (mod n).

Esses resultados se tornam intuitivos quando interpretados sob a otica da teoria dos

grupos, considerando o grupo multiplicativo (Z/nZ)∗, como sera feito na secao seguinte.

2.3.6 O grupo multiplicativo (Z/nZ)∗

Nesta secao, sao dados alguns resultados a respeito do grupo mais importante no

estudo de teoria dos numeros, (Z/nZ)∗.

Teorema 2.3.22. Os inteiros 1 ≤ a < n tais que mdc(a, n) = 1, sob a operacao de

multiplicacao modular, formam o grupo (Z/nZ)∗. Este grupo e abeliano e de ordem φ(n).

A condicao para que (Z/nZ)∗ seja cıclico e dada pelo teorema a seguir.

Teorema 2.3.23. O grupo (Z/nZ)∗ e cıclico se e somente se n = 1, 2, 4, uma potencia

de um primo ımpar, ou duas vezes uma potencia de um primo ımpar.

Em particular, a existencia de raızes primitivas e condicionada ao fato de o grupo

ser cıclico. Alguns resultados sobre raızes primitivas ja foram dados na Secao 2.2, no

contexto do grupo multiplicativo de um corpo finito, mas deve-se observar que este nao

21

e o mesmo objeto algebrico que o grupo (Z/nZ)∗; por exemplo, a cardinalidade dos dois

nao e a mesma: |Fpk | = pk − 1, enquanto |(Z/pkZ)∗| = φ(pk) = pk−1(p− 1) 6= pk − 1. Por

conta disso, os resultados dados naquela secao sao adaptados aqui para o grupo (Z/nZ)∗,

no caso em que este grupo e cıclico.

Teorema 2.3.24. Um elemento a ∈ (Z/nZ)∗ e uma raiz primitiva se e somente se

aφ(n)/q = 1 para cada primo q que divide φ(n).

Teorema 2.3.25. Se (Z/nZ)∗ possui raızes primitivas, entao estas raızes primitivas sao

em numero de φ(φ(n)).

2.3.7 Resıduos quadraticos e raızes quadradas modulares

Esta secao contempla as solucoes para congruencias quadraticas do tipo x2 ≡ a

(mod n), no contexto do grupo (Z/nZ)∗.

Definicao 2.3.8. Um elemento a ∈ (Z/nZ)∗ e dito um resıduo quadratico se a ≡ s2

(mod n) para algum s ∈ (Z/nZ)∗. O conjunto dos resıduos quadraticos modulo n sera

denotado por Qn.

O resultado a seguir determina o numero de raızes quadradas de elementos de Qn

(lembrando que os elementos de (Z/nZ)∗\Qn nao possuem raızes quadradas por definicao).

Teorema 2.3.26. Seja k o numero de primos distintos que dividem n, e seja a ∈ Qn.

Entao numero de elementos t ∈ (Z/nZ)∗ tais que t2 ≡ a (mod n) e dado por

N =

2k+1 se n ≡ 0 (mod 8),

2k−1 se n ≡ 2 (mod 4),

2k caso contrario.

Teorema 2.3.27. Qn e subgrupo de (Z/nZ)∗.

A determinacao de Qn e particularmente simples quando (Z/nZ)∗ e cıclico.

Teorema 2.3.28. Seja n > 2, e suponha a existencia de uma raiz primitiva g (mod n).

Entao Qn e um grupo cıclico de ordem φ(n)/2 gerado por g2.

As notacoes a seguir simplificam o trabalho de lidar com resıduos quadraticos.

22

Definicao 2.3.9. Seja p ≥ 3 um primo. O sımbolo de Legendre de um inteiro a qualquer

e

(a

p

)=

0 se p | a,

1 se a ∈ Qp,

−1 se a ∈ (Z/nZ)∗ \Qp.

Definicao 2.3.10. Seja m um inteiro ımpar, e a um inteiro qualquer. O sımbolo de Jacobi

( am

) e definido em termos da fatoracao de m em potencias de primos,

m =∏

ptii ,

como ( a

m

)=∏(

a

pi

)t

i

.

Deve-se observar que, para m composto, o sımbolo de Jacobi ( am

) = 1 nao significa

que a congruencia x2 ≡ a (mod m) possui solucao, ao contrario do que se poderia esperar.

Para tanto, exige-se mais: o sımbolo de Legendre (ap) deve ser 0 ou 1 para cada um dos

fatores p de m. Porem, se ( am

) = −1, pode-se afirmar com certeza que a congruencia nao

possui solucao.

Sımbolos de Legendre podem ser calculados de maneira eficiente atraves do seguinte

resultado.

Teorema 2.3.29 (Criterio de Euler). Se p ≥ 3 e primo, entao para todos os inteiros

a, (a

p

)≡ a(p−1)/2 (mod p).

Algumas simplificacoes podem ser feitas em expressoes envolvendo sımbolos de Le-

gendre e Jacobi atraves dos resultados a seguir.

Teorema 2.3.30. Sejam m, n inteiros ımpares e a, b inteiros quaisquer. As seguintes

relacoes sao validas para os sımbolos de Legendre e Jacobi:(ab

m

)=( a

m

)( b

m

),

( a

mn

)=( a

m

)(a

n

).

As relacoes especiais a seguir sao de uso amplo:(−1

m

)= (−1)(m−1)/2,

23

(2

m

)= (−1)(m2−1)/8.

O grande valor das relacoes especiais incluıdas no teorema e que seu calculo nao exige

exponenciacoes modulares (12). O valor de (−1)(m−1)/2 e 1 se (m − 1)/2 e par e -1 se

(m − 1)/2 e ımpar; as duas condicoes podem ser simplificadas para m ≡ 1 (mod 4) e

m ≡ 3 (mod 4), respectivamente, e o calculo do resto da divisao de um inteiro por uma

potencia de 2 pode ser realizado sem envolver uma divisao explıcita, atraves da operacao

logica AND: se a = 1, 3, m ≡ a (mod 4) ⇐⇒ (m & 3) == a (na notacao das lingua-

gens C/C++). O calculo de (−1)(m2−1)/8 e ligeiramente mais complicado; inicialmente

observa-se que esse valor depende apenas da classe de congruencia de m modulo 8, e

constroi-se uma tabela tab[8] = { 0, 1, 0, -1, 0, -1, 0, 1 }, obtendo-se a relacao

(−1)(m2−1)/8 = tab[m & 7].

O resultado a seguir esta para o calculo de sımbolos de Jacobi como o Lema de

Euclides 2.3.3 esta para o calculo de maximos divisores comuns, eliminando a necessidade

de fatorar o modulo m.

Teorema 2.3.31 (Lei de reciprocidade quadratica). Se m, n sao inteiros ımpares

coprimos, entao (m

n

)( n

m

)= (−1)(m−1)(n−1)/4.

O calculo de a = (−1)(m−1)(n−1)/4 tambem pode ser realizado sem exponenciacoes

modulares: if (m & n & 2) a = 1; else a = -1;.

O algoritmo a seguir mostra como e possıvel usar a lei de reciprocidade quadratica

para computacao eficiente do sımbolo de Jacobi.

Algoritmo 2.3.5. Dado um inteiro positivo ımpar m e um inteiro qualquer a, o algoritmo

retorna o sımbolo de Jacobi ( am

). O vetor tab e o vetor descrito acima para calculo eficiente

de (−1)(m2−1)/8.

1. [Lacos de reducao]

a = a (mod m);

t = 1;

while (a 6= 0) {while (a e par) {

a = a/2;

t = t · tab[a&7];

24

}(a, m) = (m, a);

if (a & m & 2)

t = −t;

a = a (mod m);

}

2. [Conclusao]

if (m == 1)

return t;

else

return 0;

Pela similaridade com o Algoritmo de Euclides 2.3.1, e possıvel concluir que o tempo

de execucao do algoritmo e O(log2 m

), assumindo que a < m.

A discussao ate agora permite responder a questao da existencia de raızes quadradas

modulo primos, mas na pratica tambem e necessario calcula-las. O algoritmo a seguir,

devido a M. Cipolla, e simples de programar e razoavelmente eficiente.

Algoritmo 2.3.6. Dado um primo p e um inteiro a tal que (ap) = 1, este algoritmo

retorna uma solucao x de x2 ≡ a (mod p).

1. [Encontrar um certo resıduo nao-quadratico]

Encontrar um inteiro aleatorio t ∈ [0, p− 1] tal que ( t2−ap

) = −1;

2. [Encontrar uma raız quadrada em Fp2 = Fp(√

t2 − a)]

x = (t +√

t2 − a)(p+1)/2;

return x;

Seu tempo de execucao e O(log3 p

).

Embora o algoritmo retorne apenas uma raiz quadrada (de duas possıveis nesta si-

tuacao), a obtencao da outra e direta, uma vez que se x2 ≡ a (mod p), entao (−x)2 ≡ a

(mod p), e assim −x e a outra raiz quadrada de a modulo p.

Outro detalhe e que o algoritmo utiliza a aritmetica de Fp2 , de modo que um exemplo

do funcionamento desta aritmetica pode ser util. A aritmetica nesse corpo e semelhante a

aritmetica complexa; esta poderia ser interpretada como a aritmetica de Fp(√−1), quando

25

isto fizer sentido (ou seja, quando (−1p

) = −1). No caso do algoritmo, faz-se ω =√

t2 − a,

de modo que ω2 = t2− a e um elemento do corpo-base Fp. Mais explicitamente, define-se

o corpo Fp2 como

Fp2 = Fp(ω) = {x + ωy : x, y ∈ Fp},

e a aritmetica pode ser confinada a esse conjunto pela substituicao ω = t2 − a, como se

segue:

(x + ωy) + (u + ωv) = (x + u) + ω(y + v),

(x + ωy)(u + ωv) = xu + ω(xv + yu) + ω2yv

= (xu + yv(t2 − a)) + ω(xv + yu).

Uma interpretacao em termos da aritmetica de polinomios e mais util quando o grau de

extensao do corpo e superior a 2. No caso do algoritmo, o polinomio e f(ω) = ω2−(t2−a),

e e possıvel verificar a equivalencia da aritmetica de x + ωy e a relacao ω2 = t2 − a, com

a aritmetica de polinomios modulo f(ω).

Resta a questao de como calcular raızes quadradas modulo n, um inteiro composto.

Nesse caso, e possıvel observar que se n = pe11 · · · pek

k , entao as congruencias simultaneas

x2 ≡ a (mod pe11 ), . . . , x2 ≡ a (mod pek

k ) implicam x2 ≡ a (mod n) pelo Teorema Chines

do Resto 2.3.13. Supondo que todos os expoentes ei na fatoracao de n sejam 1, a solucao de

cada uma das congruencias pode ser feita pelo Algoritmo 2.3.6, obtendo duas solucoes x e

−x em cada caso, e depois e possıvel aplicar um algoritmo de reconstrucao de congruencias

simultaneas (por exemplo, utilizando a relacao dada no Teorema 2.3.13) e obter as 2k

solucoes possıveis modulo n.

26

3 Curvas Elıpticas

As curvas elıpticas vem se estabelecendo como ferramentas promissoras para a teo-

ria dos numeros e criptografia. Nas ultimas duas decadas, diversos algoritmos tem sido

propostos empregando a aritmetica de curvas elıpticas, geralmente apresentando diver-

sas vantagens sobre outros algoritmos conhecidos. Destacam-se o algoritmo ECPP para

demonstracoes de carater primo, o algoritmo ECM para fatoracao de inteiros, e criptos-

sistemas baseados em curvas elıpticas, como o ECDSA, ECDH e outros.

Este capıtulo consiste de uma introducao ao grupo de pontos de uma curva elıptica,

que representa o uso das curvas elıpticas no contexto da teoria computacional do numeros.

Inicialmente introduz-se as curvas elıpticas sob um ponto de vista geometrico. Em seguida,

discute-se o seu grupo de pontos e teoremas fundamentais a respeito do mesmo. Por fim,

alguns algoritmos simples para a aritmetica deste grupo sao expostos.

3.1 Aspectos geometricos

Uma curva elıptica e uma curva cubica sobre a qual exige-se a condicao extra de nao-

singularidade: as derivadas parciais da equacao da curva nao podem ser simultaneamente

nulas em nenhum ponto da curva. Se esta condicao for satisfeita, e ademais, a curva for

considerada sobre um corpo cuja caracterıstica nao seja 2 nem 3, e possıvel simplificar a

equacao geral de um polinomio de grau 3 para a forma

y2 = x3 + ax + b, (3.1)

a chamada parametrizacao de Weierstrass para uma curva elıptica (2). A curva satisfaz

a condicao de nao-singularidade se e somente se 4a3 +27b2 6= 0, onde este valor e o discri-

minante da curva (3.1). Esta parametrizacao nao e valida para corpos de caracterıstica

2 ou 3, devendo ser substituıda por uma parametrizacao mais complexa (com mais ter-

mos). Como o trabalho nao lida com a aritmetica de corpos com essas caracterısticas, as

27

Figura 3.1: A curva elıptica afim y2 = x3 − 3x + 3.

parametrizacoes para estes casos nao serao consideradas.

Um grafico da curva elıptica y2 = x3 − 3x + 3 sobre os numeros reais e mostrada na

Figura 3.1.

Diz-se que uma curva elıptica em 2 variaveis, como considerada ate agora, esta na

sua forma afim. Uma forma equivalente, porem mais util em certas situacoes, e a forma

projetiva, onde a curva e dada em funcao de 3 variaveis. A parametrizacao de Weierstrass

para a curva nesta forma e dada por

y2z = x3 + axz2 + bz3. (3.2)

Certas solucoes projetivas da curva estao relacionadas entre si. Se (x, y, z) e uma solucao

de (3.2), entao e facil ver que (tx, ty, tz) tambem sera uma solucao, caso t 6= 0. Faz sentido

entao falar da classe de equivalencia de solucoes [x, y, z], que representa todas as solucoes

em que as coordenadas sao multiplicadas por um escalar nao-nulo.

As solucoes afins e projetivas tambem estao relacionadas entre si. Se (x, y) e uma

solucao afim de (3.1), entao [x, y, 1] e uma solucao projetiva de (3.2); e de forma recıproca,

se [x, y, z] e uma solucao projetiva de (3.2), entao (x/z, y/z) e uma solucao afim de (3.1).

A forma projetiva (3.2) tambem permite a definicao de uma solucao especial da curva,

o ponto O = [0, 1, 0], que e chamado ponto no infinito. Esta solucao sera crucial nas

definicoes da Secao 3.2.

Embora as parametrizacoes de Weierstrass, para o caso afim e projetivo, sejam am-

28

plamente utilizadas na literatura da teoria de curvas elıpticas, as parametrizacoes a seguir

podem ser computacionalmente mais convenientes em certas situacoes. Na forma afim,

temos

y2 = x3 + Cx2 + Ax + B, (3.3)

e na forma projetiva,

y2z = x3 + Cx2z + Axz2 + Bz3. (3.4)

O discriminante da equacao nessa forma e 4A3 + 27B2 − 18ABC − A2C2 + 4BC3, e

como na parametrizacao de Weierstrass, deve ser diferente de zero para que a curva seja

nao-singular.

A definicao a seguir compila os resultados desta secao.

Definicao 3.1.1. Uma curva cubica nao-singular com coeficientes provindos de um corpo

F, e que possua pelo menos um ponto com coordenadas nao simultaneamente nulas em

F, e dita uma curva elıptica sobre F. Se a caracterıstica de F nao e 2 ou 3, a equacao

(3.1) define curvas elıpticas sobre F, contanto que 4a3 + 27b2 6= 0. Denota-se por E(F)

o conjunto de pontos com coordenadas em F que satisfazem a equacao da curva, mais o

ponto no infinito O. Temos entao

E(F) = {(x, y) ∈ F× F : y2 = x3 + ax + b} ∪ {O}.

3.2 O grupo de pontos de uma curva elıptica

Sejam dois pontos P1 = (x1, y1) e P2 = (x2, y2) de uma curva elıptica na forma afim,

dada pela equacao (3.1). E possıvel construir um terceiro ponto P3 = (x3, y3) da curva

em funcao desses dois pontos, atraves da seguinte regra: traca-se a reta que passa por P1

e P2, que intersecciona a curva em um terceiro ponto (exceto quando a reta e vertical).

Tomando-se a reflexao desse terceiro ponto em torno do eixo x, o que e possıvel uma

vez que a curva e simetrica em relacao a esse eixo, obtem-se o ponto P3. A justificativa

para essa reflexao aparentemente arbitraria e que de outra maneira, os tres pontos seriam

colineares por definicao, o que impossibilitaria a obtencao de novos pontos a partir de

combinacoes desses tres.

A Figura 3.2 ilustra o processo descrito.

Quando P1 = P2, essa construcao falha, uma vez que existem infinitas retas que

passam por um unico ponto. Neste caso, escolhe-se a reta tangente a curva no ponto, que

29

Figura 3.2: Soma de pontos em uma curva elıptica.

pode ser obtida por derivacao implıcita da equacao da curva (3.1).

Outro caso especial e aquele em que a reta resultante da construcao e vertical; o

terceiro ponto de interseccao dessa reta com a curva e definido como o ponto no infinito

O.

A regra geometrica aqui descrita pode ser interpretada como uma operacao binaria

entre dois pontos da curva, que resulta em um terceiro ponto da curva. Combinando

todas as solucoes da equacao da curva, dadas na Definicao 3.1.1, com a operacao descrita,

e possıvel mostrar que e obtido um grupo abeliano, o grupo de pontos de uma curva

elıptica. Este grupo, assim como o conjunto de pontos da curva elıptica, e denotado por

E(F)

Pelo uso de geometria analıtica, e possıvel obter expressoes para as regras geometricas

consideradas. Observa-se que essas operacoes sao validas nao somente para R, onde

foi feita a deducao, mas tambem para outros corpos. O teorema a seguir fornece essas

expressoes e afirma que E(F), em conjunto com estas expressoes, forma um grupo abeliano

(2), cuja notacao empregada ao longo desse trabalho sera aditiva.

Teorema 3.2.1. Seja E(F) uma curva elıptica definida por (3.1), sobre um corpo cuja

caracterıstica e diferente de 2 e 3, e sejam dois pontos P1 = (x1, y1) e P2 = (x2, y2)

(nao necessariamente distintos). Por fim, seja a operacao comutativa + com operacao

inversa − definida pelas seguintes propriedades:

30

1. P1 + P2 = (x1, y1) + (x2, y2) = (x3, y3) = P3, em que

x3 = m2 − x1 − x2,

−y3 = m(x3 − x1) + y1,

onde o coeficiente angular m e definido como

m =

y2 − y1

x2 − x1

se x2 6= x1,

3x21 + a

2y1

se x2 = x1;

2. −P1 = (x1,−y1).

Entao o grupo (E(F), +) e um grupo abeliano com identidade O.

A interpretacao geometrica da operacao se perde quando a curva e considerada sobre

um corpo finito Fp, como os inteiros modulo p. No entanto, as expressoes do Teorema 3.2.1

ainda sao validas nesta situacao, bastando substituir a aritmetica de R pela aritmetica de

Fp; em particular, as operacoes de divisao podem ser realizadas atraves de multiplicacao

pelo inverso do divisor.

A definicao de multiplicacao de pontos por inteiros, que corresponde a operacao de

exponenciacao em grupos multiplicativos, e direta:

nP = P + P + · · ·+ P︸ ︷︷ ︸n vezes

.

Define-se tambem 0P = O e (−n)P = −(nP ). Devido a similaridade com a exponen-

ciacao em grupos multiplicativos, os mesmos algoritmos podem ser empregados, embora

nao necessariamente os melhores algoritmos para exponenciacao em (Z/nZ)∗ sejam os

melhores para multiplicacao por inteiro em E(Fp), devido ao desempenho relativo das

operacoes de somar dois pontos distintos e de dobrar um ponto.

O seguinte teorema elucida a estrutura algebrica do grupo de pontos de uma curva

elıptica (2).

Teorema 3.2.2 (Cassels). O grupo E(Fpk) e cıclico ou isomorfico a um produto de dois

grupos cıclicos

E ∼= Z/d1Z× Z/d2Z,

em que d1 | d2 e d1 | pk − 1.

31

Grupos cıclicos ja foram estudados no Capıtulo 2. A segunda possibilidade do teorema,

que o grupo seja um produto de dois outros grupos cıclicos, indica que a estrutura desse

grupo e similar a do grupo (Z/nZ)∗, em que n = pq e produto de dois primos (11).

A respeito de |E(Fpk)|, a ordem do grupo de pontos de uma curva elıptica sobre um

corpo finito, e conhecido o seguinte resultado (2).

Teorema 3.2.3 (Hasse). A ordem do grupo E(Fpk) satisfaz a desigualdade

pk + 1− 2√

pk < |E(Fpk)| < pk + 1 + 2√

pk.

Uma interpretacao muito util do teorema e que log |E(Fpk)| ≈ log(pk), ou seja, a

ordem do grupo de pontos de uma curva pode ser representada por essencialmente o

mesmo numero de bits que o numero de elementos do corpo sobre o qual ela e definida.

Esse dado e bastante util na analise de algoritmos envolvendo curvas elıpticas. No entanto,

isso nao significa que os dois valores estejam muito proximos, a ponto de permitir que

todos os valores possıveis da ordem do grupo sejam testados: isso levaria a um algoritmo

exponencial.

3.3 Algoritmos para aritmetica elıptica

Nesta secao, serao considerados algoritmos basicos para aritmetica elıptica, sem gran-

des preocupacoes quanto a eficiencia dos mesmos; algoritmos eficientes sao abordados por

exemplo em (2).

O primeiro algoritmo soluciona o problema de encontrar um ponto na curva.

Algoritmo 3.3.1. Seja uma curva elıptica E(Fp) com p > 3 um primo e equacao

y2 = x3 + ax + b. Este algoritmo retorna um ponto (x, y) de E.

1. [Laco]

Sorteie um valor aleatorio 0 ≤ x < p;

t = x3 + ax + b mod p;

if (( tp) == −1)

goto [Laco];

return (x,±√

t mod p); // Raiz quadrada modular.

O funcionamento do algoritmo deve ser claro: para que x0 seja uma coordenada x

valida da curva y2 = x3+ax+b, e preciso que x30+ax0+b seja um resıduo quadratico, para

32

permitir a extracao da raiz quadrada desse valor. Quando um ponto (x, y) e encontrado,

sabe-se que, pela simetria da curva, (x,−y) tambem e um ponto valido, e por isso as duas

solucoes sao retornadas.

O numero de execucoes do laco no algoritmo deve ser pequeno: admitindo que x3 +

ax + b seja um valor aleatorio (dado que x e aleatorio), e como metade dos elementos

de (Z/pZ)∗ sao resıduos quadraticos, fica claro que em 50% dos casos um dado valor de

x3 + ax + b sera resıduo quadratico.

A seguir, e preciso realizar aritmetica com os pontos da curva elıptica. A escolha de

um sistema de coordenadas e crucial. Serao consideradas as duas opcoes ja discutidas

anteriormente, coordenadas afins e projetivas.

3.3.1 Coordenadas afins

Inicialmente e apresentado o algoritmo para aritmetica em coordenadas afins. Devido

a impossibilidade de representar o ponto no infinito O em coordenadas afins, ha duas

opcoes: e possıvel utilizar uma variavel booleana cujo valor indica se o ponto atual e O,

ou adicionar uma terceira coordenada z a representacao, como em coordenadas projetivas,

porem z so pode assumir os valores 0 (quando o ponto em questao e O) ou 1.

Algoritmo 3.3.2. Seja uma curva elıptica E(F), em que a caracterıstica do corpo Fe diferente de 2 e 3, e dada pela equacao afim y2 = x3 + ax + b. Pontos P da curva

sao representados como (x, y, z), onde z = 1 sempre, exceto quando P = O, o ponto

no infinito, e nesse caso P = (0, 1, 0) ou P = (0,−1, 0). A funcao a seguir computa a

operacao fundamental de adicao elıptica.

1. [Funcao de adicao elıptica]

soma(P1 = (x1, y1), P2 = (x2, y2))

{if (z1 == 0)

return P2; // P1 = O ⇒ O + P2 = P2

if (z2 == 0)

return P1; // P2 = O ⇒ P1 + O = P1

if (x1 == x2) // P1 = ±P2?

if (y1 + y2 == 0) // P1 = −P2

return (0, 1, 0);

else // P1 = P2

33

m = (3x21 + a)(2y1)

−1;

else // P1 6= ±P2

m = (y2 − y1)(x2 − x1)−1;

x3 = m2 − x1 − x2;

return (x3, m(x1 − x3)− y1, 1);

}

E desejavel fornecer tambem as seguintes operacoes extras:

2. [Funcao de negacao elıptica]

neg(P ) { return (x,−y, z); }

3. [Funcao de adicao elıptica de um ponto a si mesmo]

dobro(P ) { return soma(P ,P ); }

4. [Funcao de subtracao elıptica]

sub(P1, P2) { return soma(P1,neg(P2)); }

Deve-se observar que as multiplicacoes por constantes pequenas, como 2 e 3, devem

ser efetuadas por meio de somas e nao multiplicacoes.

Os dois primeiros testes do algoritmo verificam se um dos pontos nao e o ponto no

infinito, e retornam o outro ponto em caso afirmativo (uma vez que O e a identidade do

grupo, e portanto P + O = P ). O terceiro teste verifica se as coordenadas x dos pontos

sao distintas ou nao (geralmente indicando se os pontos em si sao distintos ou nao), e

calcula o coeficiente angular m de acordo com cada caso. Observe que se P2 = −P1, entao

a coordenada x destes dois pontos e a mesma, embora os pontos sejam distintos; o teste

aninhado dentro do terceiro teste reconhece esta condicao e retorna O como resultado,

uma vez que P − P = O.

A contagem de operacoes de corpo realizadas a cada adicao elıptica e crucial para

decidir qual sistema de coordenadas a implementar. Ha uma certa desvantagem para

as coordenadas afins, gracas as operacoes de inversao modular envolvidas no calculo do

coeficiente angular m, que sao consideravelmente mais custosas que as operacoes basicas

de adicao, subtracao e multiplicacao modular.

3.3.2 Coordenadas projetivas

As coordenadas projetivas eliminam a necessidade de inversoes modulares, as custas

de um maior numero de operacoes basicas. Mesmo assim, o desempenho das coordenadas

34

projetivas e melhor, em geral. As expressoes a seguir sao manipulacoes das expressoes para

aritmetica elıptica projetiva, em que o numero de operacoes de corpo (aritmetica modular)

e minimizado. Para a computacao de P3 = P1 + P2, em que P1 6= P2 e Pi = [xi, yi, zi],

temos

t1 = x2z1 − x1z2,

t2 = x2z1 + x1z2,

t3 = y2z1 − y1z2,

t4 = y2z1 + y1z2,

t5 = z1z2,

x3 = t1(t23t5 − t21t2

),

y3 =1

2

(t3(3t21t2 − t23t5

)− t31t4

),

z3 = t31t5.

A multiplicacao por 1/2 para o calculo de y3 deve ser realizada atraves de um des-

locamento dos bits do operando para a direita (quando o operando e par), ou soma do

operando a p seguida de deslocamento (quando o operando e ımpar), e nao multiplicacao

pelo inverso modular de 2.

Para a computacao de P ′ = 2P , em que P ′ = [x′, y′, z′] e P = [x, y, z], temos as

expressoes

t1 = 2xy,

t2 = 3x2 + az2,

t3 = 2yz,

x′ = t3(t22 − 2t1t2

),

y′ = t2(3t1t3 − t22

)− 2y2t23,

z′ = t33.

O algoritmo a seguir explicita o uso destas formulas, e evita mais algumas operacoes

pelo armazenamento de temporarios.

Algoritmo 3.3.3. Seja uma curva elıptica E(F), em que a caracterıstica do corpo F e

diferente de 2 e 3, e dada pela equacao projetiva y2z = x3 +axz2 +bz3. Pontos P da curva

sao representados como (x, y, z), onde [0, 1, 0] e [0,−1, 0] indicam o ponto no infinito O.

A funcao a seguir computa a operacao de adicao elıptica de um ponto a si mesmo.

35

1. [Funcao de adicao elıptica de um ponto a si mesmo]

dobro(P = (x, y, z))

{if (y == 0 ou z == 0)

return [0, 1, 0] // P = O ⇒ 2P = O

t1 = 2xy;

t2 = 3x2 + az2;

t2q = t22;

t3 = 2yz;

t3q = t23;

t1t3 = t1 · t3;dt1t3 = t1t3 + t1t3;

t2qmdt1t3 = t2q− dt1t3;

x′ = t3 · t2qmdt1t3;

y′ = t2(dt1t3− t2qmdt1t3)− 2y2 · t2q;

z′ = t3q · t3;return [x′, y′, z′];

}

A funcao a seguir computa a operacao de adicao elıptica de pontos distintos.

2. [Funcao de adicao elıptica]

soma(P1 = (x1, y1, z1), P2 = (x2, y2, z2))

{if (z1 == 0)

return P2; // P1 = O ⇒ O + P2 = P2

if (z2 == 0)

return P1; // P2 = O ⇒ P1 + O = P1

x2z1 = x2 · z1;

x1z2 = x1 · z2;

t1 = x2z1− x1z2;

if (t1 == 0) // x1/z1 = x2/z2 ⇒ x1z2 − x2z1 = 0

{y2z1 = y2 · z1;

y1z2 = y1 · z2;

t3 = y2z1− y1z2;

if (t3 == 0) // y1/z1 = y2/z2 ⇒ y1z2 − y2z1 = 0

36

return dobro(P1); // P1 = P2 ⇒ P3 = 2P1

else

return [0, 1, 0] ; // P1 = −P2 ⇒ P3 = P1 + P2 = O

}else

{y2z1 = y2z1;

y1z2 = y1z2;

t3 = y2z1 - y1z2;

t3q = t23;

}t1q = t21;

t1c = t1q · t1;t2 = x2z1 + x1z2;

t4 = y2z1 + y1z2;

t5 = z1z2;

t1qt2 = t1q · t2;t3qt5 = t3q · t5;x3 = α(t3qt5− t1qt2);

y3 = 12(t3(3t1qt2− t3qt5)− t1qt4);

z3 = t1q · t5;return [x3, y3, z3];

}

E desejavel fornecer tambem as seguintes operacoes extras:

3. [Funcao de negacao elıptica]

neg(P ) { return [x,−y, z]; }

4. [Funcao de subtracao elıptica]

sub(P1, P2) { return add(P1,neg(P2)); }

Levando em conta os comentarios no corpo do codigo e as observacoes sobre o algo-

ritmo anterior, a operacao deste algoritmo deve ser clara.

37

4 O Algoritmo ECPP

Neste capıtulo, serao estudados os algoritmos existentes relacionados ao problema

de demonstracao de carater primo de inteiros. Dentre estes, sera argumentado que o

algoritmo ECPP e o mais apropriado para uma implementacao distribuıda. Apesar disso,

uma classe de algoritmos, os testes de carater pseudoprimo, sao de grande importancia

como subrotinas do ECPP, e serao expostos em maiores detalhes.

Inicia-se o capıtulo com uma discussao dos principais testes de carater pseudoprimo,

continuando com uma comparacao entre os algoritmos mais importantes para demons-

tracao de carater primo. Em seguida, discute-se em mais detalhes a versao de Goldwasser

e Kilian do algoritmo ECPP (13), que foi a primeira versao deste algoritmo a ser introdu-

zida. O proximo topico e a teoria de multiplicacao complexa, que proporciona um metodo

para evitar o passo mais ineficiente do algoritmo de Goldwasser e Kilian, a determinacao

da ordem do grupo de pontos de uma curva elıptica. A secao seguinte mostra como Atkin

e Morain empregaram a teoria de multiplicacao complexa para forjar uma nova versao

do ECPP (14), muito mais eficiente que a versao de Goldwasser e Kilian. Finalmente,

conclui-se o capıtulo com uma exposicao da principal melhoria ao teste original de Atkin

e Morain, o chamado fastECPP de J. Shallit.

4.1 Testes de carater pseudoprimo

Certas aplicacoes de numeros primos podem tolerar o uso de numeros cujo carater

primo nao esteja demonstrado e certificado, bastando que algum metodo afirme que o

numero e primo com alta probabilidade (embora seja possıvel que um composto seja

declarado primo). Por exemplo, e possıvel que a aplicacao em questao retorne resultados

claramente errados e facilmente detectaveis quando um numero composto e empregado.

Outra situacao e quando os numeros primos exigidos sao de tamanho tao grande que e

inviavel obter uma demonstracao de carater primo dos mesmos.

38

Nestas situacoes, uma classe de algoritmos pode mostrar-se muito util, os testes de

carater pseudoprimo. Estes testes sao caracterizados por reconhecer (corretamente) todos

os primos, mas incorretamente reconhecer alguns compostos como primos. Isso significa

que um teste que declara um inteiro como composto pode ser usado como prova do carater

composto deste inteiro, mas caso o teste declare que o inteiro e primo, sabe-se apenas que

ha uma probabilidade 1 − ε deste inteiro ser primo, e ε do inteiro ser composto, com

0 < ε < 1. A eficiencia de um teste de carater primo e medida nao apenas pelo seu tempo

de execucao, mas pela probabilidade ε de um inteiro composto ser declarado primo: quanto

menor o valor de ε, mais util e o teste.

No contexto dos testes de carater pseudoprimo, um inteiro que apresente a propriedade

de ser composto, porem declarado primo por um dado teste, e dito um pseudoprimo com

relacao aquele teste. Um inteiro declarado primo pelo teste e dito um primo provavel.

Dentre os testes mais conhecidos na literatura, foram escolhidos dois para serem im-

plementados em nosso sistema, o chamado teste forte e o teste de Frobenius, este ultimo

devido a J. Grantham. Para cada um dos casos, argumenta-se o motivo de sua escolha

para implementacao.

4.1.1 O teste de Fermat e o teste forte

O primeiro teste de carater pseudoprimo inventado utiliza a recıproca do Pequeno

Teorema de Fermat 2.3.20: se an−1 ≡ 1 (mod n) para algum a 6≡ ±1 (mod n) entao n e

primo com alta probabilidade. O algoritmo e explicitado a seguir.

Algoritmo 4.1.1. E fornecido ao algoritmo um inteiro n > 3 e um inteiro a, 2 ≤ a ≤ n−2,

e o algoritmo retorna uma das duas afirmacoes ‘n e primo provavel de Fermat para a base

a’ ou ‘n e composto’.

1. [Exponenciacao modular]

b = an−1 mod n;

2. [Retornar decisao]

if (b == 1)

return ‘n e primo provavel de Fermat para a base a’;

else

return ‘n e composto’;

39

O tempo de execucao desse teste e O(log nM(n)), onde M(n) e o tempo de execucao

de uma multiplicacao de inteiros modulo n. Assumindo o uso de algoritmos eficientes,

pode-se adotar M(n) = O(log n log log n), de modo que o tempo de execucao do teste e

O(log2 n log log n) = O((log n)2+ε).

Quanto aos pseudoprimos de Fermat para uma dada base a, sabe-se que sao raros em

relacao aos primos, no sentido que o numero de pseudoprimos inferiores a x e o(π(x)),

mas tambem que ha uma quantidade infinita dos mesmos (2).

Poderia-se esperar entao que, aplicando o teste de Fermat para uma quantidade sufi-

ciente de diferentes bases a, seria possıvel certificar o carater primo de um inteiro. Infe-

lizmente, existem inteiros que sao pseudoprimos a todas as bases a, os chamados numeros

de Carmichael. A respeito destes numeros, conhece-se o seguinte teorema de Alford,

Granville e Pomerance.

Teorema 4.1.1 (Alford, Granville, Pomerance). Existem infinitos numeros de Car-

michael. Em particular, para valores suficientemente grandes de x, a quantidade C(x) de

numeros de Carmichael inferiores a x satisfaz a desigualdade C(x) > x2/7.

De certa forma, a existencia dos numeros de Carmichael e decepcionante: seria de-

sejavel que todos os compostos fossem reconhecidos como tais pelo teste de Fermat, para

pelo menos alguma base a. Felizmente, uma pequena modificacao do teste de Fermat

garante essa propriedade. O chamado teste forte e baseado no teorema a seguir (2).

Teorema 4.1.2. Suponha que n > 2 e primo e n − 1 = 2st, onde t e ımpar. Se a nao

e divisıvel por n, entao at ≡ 1 (mod n) ou a2it ≡ −1 (mod n) para algum valor de i no

intervalo [0, s− 1].

Um algoritmo que emprega este criterio para teste de carater pseudoprimo e dado a

seguir.

Algoritmo 4.1.2. Seja n > 3 um inteiro ımpar, representado como n = 1 + 2st com t

ımpar. Tambem e fornecido ao algoritmo um inteiro a, 1 < a < n− 1. E retornada uma

das duas afirmacoes ‘n e um primo provavel forte para a base a’ ou ‘n e composto’.

1. [Parte ımpar de n− 1]

b = at mod n;

if (b == 1 ou b == n− 1)

return ‘n e um primo provavel forte para a base a’;

40

2. [Potencias de 2 de n− 1]

for (0 < j < s) {b = b2 mod n;

if (b == n− 1)

return ‘n e um primo provavel forte para a base a’;

}return ‘n e composto’;

Observa-se que um primo provavel forte para a base a e um primo provavel de Fermat

para a base a, mas a recıproca nao necessariamente e verdadeira. Isso significa que o teste

de carater pseudoprimo forte potencialmente reconhece mais compostos que o teste de

Fermat. Aliado a sua contagem de operacoes virtualmente igual a do teste de Fermat

(assintoticamente, seus tempos de execucao sao iguais), e seguro dizer que o teste forte e

preferıvel ao teste de Fermat.

Quanto a distribuicao dos pseudoprimos fortes, conhece-se o seguinte resultado (2).

Teorema 4.1.3. Seja S(n) o conjunto de bases para as quais n e um pseudoprimo forte.

Se n > 9 e um inteiro composto ımpar, temos que |S(n)| ≤ φ(n)/4.

E possıvel interpretar este teorema da seguinte maneira: escolhendo uma base a ao

acaso para o teste, ha uma probabilidade inferior a 1/4 que n seja pseudoprimo forte para a

base a. Pela escolha de b bases diferentes, e assumindo independencia de eventos, espera-

se que a probabilidade de n ser pseudoprimo a todas essas bases e (1/4)b, podendo-se

tornar essa probabilidade tao pequena quanto desejavel. Essa interpretacao e meramente

heurıstica, e escolher b de modo que (1/4)b < 1/n nao equivale a uma demonstracao do

carater primo de n.

Na implementacao de nosso sistema, o carater pseudoprimo de um inteiro e testado

apenas em relacao a base 2. Esta base foi escolhida por permitir simplificacoes nos algo-

ritmos de exponenciacao que exigem multiplicacoes pela base, como o Algoritmo 2.3.4: a

multiplicacao pode ser substituıda por uma simples adicao. Esta aplicacao do algoritmo

permite eliminar a grande maioria dos compostos, mas quando um inteiro e declarado

primo provavel, ele e submetido a um teste mais rigoroso, o teste de Frobenius descrito a

seguir.

41

4.1.2 O teste de Frobenius

Este teste foi proposto por J. Grantham (15), mas antes de descrever o teste, e preciso

abordar alguns conceitos necessarios ao teste que nao foram descritos anteriormente. Em

particular, o teste de Frobenius e uma extensao do teste de Lucas descrito a seguir, e

como tal, e preciso estudar a teoria por tras deste teste.

A sequencia de Fibonacci cujo conjunto imagem e dado por (1, 1, 2, 3, 5, 8, 13,

. . . ) satisfaz a recorrencia uj = uj−1 + uj−2. Usando conceitos de matematica discreta, e

possıvel demonstrar que a sequencia de Fibonacci possui polinomio de recorrencia x2 −x− 1. Um caso mais geral das sequencias de Fibonacci sao as sequencias de Lucas, cujo

polinomio de recorrencia e f(x) = x2 − ax + b, desde que ∆ = a2 − 4b nao seja um

quadrado perfeito. Define-se

Uj = Uj(a, b) =xj − (a− x)j

x− (a− x)(mod f(x)), (4.1)

Vj = Vj(a, b) = xj + (a− x)j (mod f(x)), (4.2)

onde a operacao de modulo indica o resto da divisao por f(x), onde os coeficientes dos

polinomios sao inteiros. As sequencias (Uj) e (Vj) satisfazem as recorrencias

Uj = aUj−1 − bUj−2,

Vj = aVj−1 − bVj−2,

cujo polinomio de recorrencia, em ambos os casos, e x2−ax+b. Da definicao das sequencias

e possıvel obter os valores iniciais U0 = 0, U1 = 1, V0 = 2, V1 = a.

O teste de Lucas e definido a seguir (2).

Teorema 4.1.4. Sejam a, b, ∆ definidos como acima, e sejam as sequencias (Uj) e (Vj)

definidas conforme (4.1). Se p e primo e mdc(p, 2b∆) = 1, entao

Up−(∆p ) ≡ 0 (mod p).

Define-se tambem o teste de Frobenius (2).

Definicao 4.1.1. Sejam a, b inteiros tais que ∆ = a2−4b nao seja um quadrado perfeito.

Diz-se que um inteiro composto n coprimo a 2b∆ e um pseudoprimo de Frobenius com

42

relacao a f(x) = x2 − ax + b se

xn ≡

a− x (mod (f(x), n)) se (∆n) = −1,

x (mod (f(x), n)) se (∆n) = 1.

Pode-se implementar o teste de Frobenius atraves de sequencias de Lucas, como afirma

o teorema a seguir.

Teorema 4.1.5. Sejam a, b inteiros tais que ∆ = a2 − 4b nao seja um quadrado perfeito,

e n um inteiro composto coprimo a 2b∆. Entao n e um pseudoprimo de Frobenius com

relacao a f(x) = x2 − ax + b se e somente se

Un−(∆n ) ≡ 0 (mod n) e Vn−(∆

n ) ≡

2b se (∆n) = −1,

2 se (∆n) = 1.

Para implementar esse teste de maneira eficiente, primeiramente e preciso considerar

como implementar os calculos de sequencias de Lucas de maneira eficiente. Sejam as

sequencias (Uj) e (Vj) definidas em (4.1). O elemento Um da sequencia pode ser definido

em termos dos elementos Vm e Vm+1 pela identidade

Um = ∆−1(2Vm+1 − aVm).

Isso significa que nao e preciso calcular as duas sequencias; basta calcular a sequencia

(Vj). Duas identidades importantes relacionadas a esta sequencia sao

V2j = V 2j − 2,

V2j+1 = VjVj+1 − a,

desde que b = 1. Quando apenas o valor de (Vj) modulo n e desejado, e possıvel generalizar

estas identidades para o caso b 6= 1 (2). Define-se A = a2b−1 − 2 (mod n). Entao

V2j(A, 1) ≡ V 2j − 2 (mod n),

V2j+1(A, 1) ≡ VjVj+1 − A (mod n),

e e possıvel recuperar V2m(a, b) a partir de Vm(A, 1) pela identidade

V2m(a, b) ≡ bmVm(A, 1) (mod n).

43

Dados os valores de Vj, Vj+1 (mod n), e possıvel empregar estas identidades para calcular

um dos pares V2j, V2j+1 (mod n) ou V2j+1, V2j+2 (mod n). Partindo de V0, V1 (mod n)

e fazendo as escolhas apropriadas ao longo do caminho, e possıvel atingir qualquer par

Vm, Vm+1 (mod n) usando uma construcao semelhante a um algoritmo de exponenciacao,

que nesse caso e conhecido como uma cadeia binaria de Lucas.

Algoritmo 4.1.3. Seja um inteiro m cuja representacao binaria e fornecida atraves de

um vetor m[0 . . . B − 1], em que m[B − 1] e o bit mais significativo. O algoritmo a seguir

calcula os elementos Vm, Vm+1 (mod n) da sequencia de Lucas (Vj), cujo polinomio de

recorrencia e x2 − ax + b e A e definido como a2b−1 (mod n), utilizando uma cadeia

binaria de Lucas.

1. [Inicializacao]

(u, v) = (V0, V1);

2. [Laco]

for (B > j ≥ 0)

if (m[j] == 1)

(u, v) = (uv − A, v2 − 2) mod n;

else

(u, v) = (u2 − 2, uv − A) mod n;

return (u, v);

O resultado a seguir completa o arsenal necessario para implementacao do teste de

Frobenius (2).

Teorema 4.1.6. Suponha que a, b, ∆, A sao definidos de acordo com o texto acima, e

que n e um inteiro composto coprimo a 2ab∆. Entao n e um pseudoprimo de Lucas em

relacao a x2 − ax + b se e somente se

AV 12(n−(∆

n )) ≡ 2V 12(n−(∆

n ))+1 (mod n).

Ademais, n e um pseudoprimo de Frobenius em relacao a x2 − ax + b se e somente se a

relacao acima se verifica, assim como

b(n−1)/2V 12(n−(∆

n )) ≡ 2 (mod n).

O algoritmo para o teste de Frobenius pode ser exposto agora (2).

44

Algoritmo 4.1.4. Sao fornecidos ao algoritmo inteiros n, a, b, tais que ∆ = a2− 4b nao e

um quadrado perfeito, e n > 1 e coprimo a 2ab∆. O algoritmo retorna ‘n e primo provavel

de Frobenius em relacao a x2− ax + b’ se n e primo ou um pseudoprimo de Frobenius em

relacao a x2 − ax + b. Caso contrario, o algoritmo retorna ‘n e composto’.

1. [Parametros auxiliares]

A = a2b−1 − 2 mod n;

m = (n− (∆n))/2;

2. [Cadeia de Lucas]

Calcular Vm, Vm+1 (mod n) utilizando o Algoritmo 4.1.3, utilizando (V0, V1) =

(2, A) como valores iniciais;

3. [Teste de Lucas]

if (AVm 6≡ 2Vm+1 (mod n))

return ‘n e composto’;

4. [Teste de Frobenius]

B = b(n−1)/2 mod n;

if (BVm ≡ 2 (mod n))

return ‘n e primo provavel de Frobenius em relacao a x2 − ax− b’;

else

return ‘n e composto’;

Pode-se mostrar que o tempo de execucao do algoritmo nao ultrapassa tres vezes

o tempo de execucao do teste de carater pseudoprimo forte. A respeito da eficiencia

do teste, conhece-se o seguinte resultado (2) para a versao forte do mesmo, que nao foi

implementada em nosso sistema:

Teorema 4.1.7. Seja n um inteiro composto que nao e quadrado perfeito e nem e divisıvel

por primos p < 50000. Entao n e um pseudoprimo forte de Frobenius com relacao a no

maximo 1/7710 dos polinomios x2 − ax + b, onde 1 ≤ a, b ≤ n, (a2−4bn

) = −1 e ( bn) = 1.

Planeja-se implementar a versao forte do teste como parte dos procedimentos de

otimizacao de nosso sistema.

45

4.2 Testes de carater primo eficientes

Nesta secao, serao considerados testes que determinam inequivocamente o carater

primo de um inteiro, sem haver probabilidade alguma de que um composto seja declarado

primo ou vice-versa. Infelizmente, como sera visto, isso tem um custo: estes algoritmos

sao bem menos eficientes que os testes de carater pseudoprimo da secao anterior.

4.2.1 O teste n − 1 e variantes

O primeiro teste de carater primo a ser descoberto foi o chamado teste n−1. Embora

este teste nao seja exatamente eficiente, sua simplicidade, e a aplicacao de ideias seme-

lhantes no ECPP, justifica a discussao do mesmo neste trabalho. O teste e baseado no

seguinte teorema de E. Lucas.

Teorema 4.2.1. Se a, n sao inteiros com n > 1, e

an−1 ≡ 1 (mod n),

mas para todos os primos q | n− 1,

a(n−1)/q 6≡ 1 (mod n),

entao n e primo.

Infelizmente, o teste exige a fatoracao de n − 1, que em geral e um problema difıcil

(2). Nesse sentido, seria desejavel utilizar apenas fatoracoes parciais de um inteiro no

teste n − 1, por exemplo n − 1 = FR onde a fatoracao completa de F e conhecida e R

e composto sem fatores conhecidos. De fato, isso e possıvel, e o primeiro resultado nesse

sentido foi o teorema a seguir, devido a Pocklington.

Teorema 4.2.2 (Pocklington). Seja F uma fatoracao parcial de n− 1 como discutido

acima, e um inteiro, a, tal que

an−1 ≡ 1 (mod n),

e para cada primo q | F ,

mdc(a(n−1)/q − 1, n

)= 1.

Entao todos os fatores primos de n sao congruentes a 1 modulo F . Em particular, se

46

F ≥√

n, entao n e primo.

Outros teoremas nesse sentido sao o de Brillhart, Lehmer e Selfridge, e o de Konyagin

e Pomerance (2). Pelo uso destes teoremas, e possıvel demonstrar o carater primo de n

conhecendo-se uma fatoracao parcial de n−1 como acima, desde que F ≥ n3/10. Em outras

palavras, quando se busca uma demonstracao de carater primo de um inteiro de, digamos,

10 mil dıgitos, basta obter 3 mil dıgitos de fatores deste inteiro. Apesar disto, o teste

ainda e pouco eficiente, exceto para inteiros de forma especial, que possuam fatoracoes

algebricas conhecidas.

Uma grande vantagem do teste n − 1 e que e possıvel construir um certificado do

carater primo de um inteiro, tal que o tempo requerido para verificar a validade do certi-

ficado e muito menor que o tempo usado para gera-lo. A existencia de certificados para

um determinado teste e uma propriedade muito desejavel, uma vez que um indıviduo nao

precisa acreditar na correcao de uma determinada implementacao do teste, ou no correto

funcionamento dos computadores que realizaram os calculos; ele pode verificar indepen-

dente e eficientemente a validade daquela demonstracao, pela verificacao do certificado

em questao.

Deve-se observar que o teste n− 1 se baseia nas propriedades do grupo (Z/nZ)∗, cuja

ordem e n− 1 caso n seja de fato primo. E possıvel utilizar propriedades semelhantes de

outros grupos para obter testes que dependem da fatoracao de n+1, n2 +n+1, n2−n+1,

n2 + 1 e outros (12). Na realidade, o unico teste de valor pratico e o teste n + 1, ja que os

demais envolvem inteiros com o dobro de dıgitos de n, e espera-se que a fatoracao desses

numeros seja bem mais difıcil que a fatoracao de inteiros com o mesmo numero de dıgitos

de n.

4.2.2 O teste ECPP

E possıvel considerar uma versao do teste n−1 em que o grupo (Z/nZ)∗ e substituıdo

pelo grupo de pontos de uma curva elıptica modulo n. Alguns obstaculos devem ser

ultrapassados para tornar este teste valido e eficiente, o que sera o objetivo de estudo do

restante do capıtulo. Neste ponto, so serao fornecidas algumas informacoes de alto nıvel

a respeito do teste, para justificar sua escolha em relacao aos demais testes.

Em primeiro lugar, pode-se mostrar que o tempo de execucao do algoritmo, com

melhorias apropriadas, e O ((log n)4+ε) para demonstrar o carater primo de um inteiro

n (16), que e o melhor resultado assintotico conhecido para esta classe de problemas.

47

Ademais, esse teste e extremamente pratico; por exemplo, o teste AKS com as melhorias

conhecidas atinge o mesmo desempenho assintotico, porem nao e pratico para inteiros que

seriam considerados faceis para o ECPP.

Outra vantagem e que o ECPP gera certificados de facil verificacao: o tempo de

execucao de um algoritmo para verificar os certificados e apenas O((log n)3+ε). Em termos

praticos, (17) relata que a demonstracao de carater primo de um inteiro de 10 mil dıgitos

levou cerca de 1000 dias de processamento, mas apenas 85 horas para verificacao do

certificado.

Por fim, o teste e facilmente paralelizavel; duas investigacoes deste fato sao (17, 18).

Ainda e uma questao em aberto se o teste adapta-se a um ambiente de computacao

distribuıda de larga escala, e e o objetivo deste trabalho argumentar que isso e possıvel.

4.2.3 Os testes APR-CL e AKS

Sao conhecidos dois outros testes eficientes de carater primo: o teste de Adleman,

Pomerance e Rumely, com melhorias de Cohen e Lenstra (portanto, APR-CL) e o teste

AKS. Infelizmente, nao e possıvel detalhar a teoria por tras dos dois testes, e esta discussao

estara restrita a caracterısticas de alto nıvel dos testes.

O tempo de execucao do teste APR-CL para demonstrar o carater primo de um inteiro

n e O((log n)C log log log n

)(12). Embora, a rigor, isto nao seja tempo polinomial, o valor

de log log log n varia muito lentamente: por exemplo, conforme n varia de um inteiro de

10 mil dıgitos para um inteiro de 100 mil dıgitos, o valor de log log log n varia menos de

10%. O teste tambem e pratico, competindo com o ECPP para inteiros na faixa de 1000

dıgitos.

No entanto, e importante observar que o APR-CL nao gera certificados de carater

primo, o que diminui o interesse nesse algoritmo, principalmente levando-se em conta que

o algoritmo ECPP gera certificados e possui desempenho semelhante.

Por ultimo, o autor nao esta familiarizado com qualquer trabalho que discuta a pa-

ralelizacao do APR-CL, e nem conhece o funcionamento do teste de modo a sugerir uma

tecnica de paralelizacao para o mesmo, enquanto a paralelizacao do ECPP ja foi discutida

amplamente na literatura, como mencionado na secao anterior.

O ultimo teste que sera considerado e o teste AKS, que foi proposto recentemente

por Agrawal, Kayal e Saxena (4). Inicialmente apresentando tempo de execucao de

48

O ((log n)10,5+ε), melhorias por diversos pesquisadores diminuıram a complexidade do al-

goritmo ate atingir O ((log n)4+ε). Porem, no momento da escrita deste trabalho, o teste

permanece como uma mera curiosidade teorica, nao existindo qualquer implementacao

competitiva com o ECPP ou o APR-CL.

4.3 O algoritmo ECPP de Goldwasser e Kilian

Nesta secao, sera estudado o algoritmo ECPP devido a Goldwasser e Kilian, que

embora nao seja pratico, e o precursor direto do algoritmo pratico de Atkin e Morain.

O principal resultado necessario ao funcionamento do algoritmo e o seguinte teorema,

devido a Goldwasser e Kilian (13), e analogo ao Teorema de Pocklington 4.2.2 para o

teste n− 1.

Teorema 4.3.1. Seja n 6= 1 um inteiro coprimo a 6 e E uma curva elıptica modulo n, e

assuma que existam um inteiro m e um ponto P ∈ E(Z/nZ) que satisfazem as condicoes

a seguir.

1. Existe um primo q | m tal que

q >(

4√

n + 1)2

.

2. mP = O.

3. (m/q)P 6= O.

Entao n e primo.

Antes mesmo de discutir o teorema, e preciso esclarecer o significado de uma curva

elıptica sobre Z/nZ, quando n nao e primo. Primeiramente, no jargao da algebra abstrata,

Z/nZ nao e um corpo, e sim um anel. Um anel possui os chamados divisores de zero,

elementos tais que xy = 0 com x, y 6= 0 elementos do anel. A excecao deste detalhe, a

aritmetica dos aneis e semelhante a aritmetica dos corpos. Isso significa que e possıvel

efetuar aritmetica elıptica como se Z/nZ fosse um corpo; caso alguma operacao no anel

se mostre impossıvel, como por exemplo uma inversao modular durante o calculo do

coeficiente angular (supondo que estejam sendo empregadas coordenadas afins), e possıvel

nao apenas afirmar que n e composto, como exibir um fator explıcito de n. De fato, esta

e a ideia por tras do algoritmo ECM de fatoracao (2).

49

Retornando ao teorema, observa-se que a unica escolha nao trivial e o valor de m, e

para tanto, pode ser utilizado o seguinte resultado.

Teorema 4.3.2. Seja n 6= 2, 3 um primo, E uma curva elıptica modulo n e m =

|E(Z/nZ)|. Se m possui um fator primo q tal que

q >(

4√

n + 1)2

,

entao existe um ponto P ∈ E(Z/nZ) tal que mP = O mas (m/q)P 6= O.

De certa forma, esta escolha e intuitiva, uma vez que os valores de m tais que mP = O

sao a ordem do grupo e seus multiplos inteiros, e nao ha motivo para escolher um multiplo

ao inves da propria ordem.

Resta agora a questao de calcular a ordem do grupo. Para isto, aplica-se o chamado al-

goritmo de Schoof (19), cujo tempo de execucao e O(log8 n

). De posse de m = |E(Z/nZ)|

para alguma curva aleatoria E, sao empregado algoritmos de fatoracao para tentar obter

uma fatoracao parcial de m que satisfaca as condicoes do Teorema 4.3.1. Em particular,

e preciso que m possua um fator primo ‘gigante’ q. Observa-se que nao e possıvel certi-

ficar que esse fator q e de fato primo sem dispender um esforco enorme; por enquanto,

e suficiente verificar que q e um primo provavel. Caso nao seja possıvel encontrar esta

fatoracao, todo o processo e repetido escolhendo-se outra curva ao acaso.

Ao obter uma fatoracao de m de acordo com as condicoes do Teorema 4.3.1, verifica-se

entao a validade dos itens 2 e 3 daquele teorema, pela escolha de um ponto P ao acaso.

Se n for de fato primo, a probabilidade de um ponto aleatorio P nao poder ser usado

para verificar as condicoes do teorema e desprezıvel, e mesmo assim basta escolher outro

ponto aleatorio caso isto ocorra.

Resta agora demonstrar que o primo provavel q na fatoracao de m e de fato primo, e

para isso, aplica-se o algoritmo recursivamente. Como cada aplicacao do algoritmo remove

pelo menos um fator 2 (correspondente a 1 bit) do inteiro cujo carater primo esta sendo

verificado, segue que o numero de execucoes recursivas do algoritmo e O (log n).

O algoritmo completo e exposto a seguir.

Algoritmo 4.3.1. Seja n > 1 um inteiro positivo coprimo a 6. Este algoritmo tentara

demonstrar que n e primo. Se n nao for primo, e possıvel que o algoritmo detecte esta

condicao ou que permaneca executando indefinidamente. A funcao e chamada como

ecpp(n) e emprega uma rotina auxiliar ecpp principal(n).

50

ecpp(n)

{

1. [Inicializacao]

i = 0;

n0 = n;

2. [Laco]

while (1) {res = ecpp principal(ni);

if (res == ‘ni e primo se ni+1 e primo’) {i = i + 1;

continue; // aplica o algoritmo recursivamente

}else if (res == ‘ni e primo’)

return n e primo;

else if (res == ‘ni e composto’)

if (i == 0) // Sera ni o proprio n?

return ‘n e composto’;

else { // volta atras na cadeia de certificacao

i = i− 1;

continue;

}}

}

ecpp principal(ni)

{

1. [Condicao de termino]

Se ni for suficientemente pequeno, verificar seu carater primo usando trial di-

vision, e retornar uma das duas assercoes ‘ni e primo’ ou ‘ni e composto’;

2. [Buscar curva apropriada]

Escolher 0 < a, b < ni aleatoriamente, verificando que 4a3 + 27b2 6= 0;

Calcular m = |E(Z/niZ)| usando o algoritmo de Schoof;

Tentar obter uma fatoracao m = tq, onde q e um primo provavel que satisfaz a

51

condicao 1 do Teorema 4.3.1, e caso isso nao seja possıvel, retornar ao inıcio deste

passo;

3. [Verificacao das condicoes do Teorema 4.3.1]

Gerar um ponto P da curva usando o Algoritmo 3.3.1;

Calcular P1 = mP e P2 = (m/q)P , sendo que se uma das computacoes falha-

rem, retornar ‘ni e composto’;

if (P1 6= O)

return ‘ni e composto’;

else if (P2 == O)

goto [Verificacao das condicoes do Teorema 4.3.1];

else {ni+1 = q;

return ‘ni e primo se ni+1 e primo’;

}

}

Pode ser mostrado que o tempo de execucao deste algoritmo e O(log12 n

), ou seja,

tempo polinomial. No entanto, o algoritmo nao e pratico; para tanto, e preciso utilizar as

modificacoes de Atkin e Morain discutidas a frente.

O certificado de carater primo gerado pelo algoritmo e formado pela sequencia de

primos n0 = n, n1, . . ., e tambem os parametros envolvidos na demonstracao de carater

primo de cada ni intermediario: a curva elıptica E, o ponto P e a ordem do grupo

m = E(Z/niZ). No interesse de comprimir os certificados, e possıvel eliminar os pontos

P para cada ni, uma vez que e possıvel gerar novos pontos durante a verificacao do certifi-

cado sem afetar significativamente o tempo de execucao deste processo. Para compressao

maxima dos certificados, e possıvel fornecer somente os parametros da curva e as ordens

de grupo, exigindo do verificador a fatoracao das ordens. Mesmo assim, a complexidade

da verificacao e significativamente inferior a da certificacao.

4.4 Curvas elıpticas com multiplicacao complexa

Nesta secao, sera abordada uma tecnica que permite a obtencao das ordem de grupo

de uma classe de curvas elıpticas, e a posterior construcao de uma curva desta classe

52

caso desejado – no caso do ECPP, caso seja possıvel fatorar uma das ordens de grupo em

tempo habil, obtendo uma fatoracao que satisfaca as condicoes do Teorema 4.3.1.

Seja uma curva elıptica E definida sobre os numeros complexos C. Consideraremos

agora os endomorfismos de E, que sao homomorfismos do grupo de pontos de E para si

mesmo e dados por funcoes racionais. O conjunto destes endomorfismos, associado a uma

operacao de adicao (relacionada a adicao elıptica) e a operacao de composicao, forma um

anel, que sera denotado End(E). Esclarecendo as operacoes do anel: se φ, σ ∈ End(E),

entao φ + σ e o endomorfismo que envia um ponto P para φ(P ) + σ(P ), onde esta ultima

operacao de adicao e adicao elıptica comum. Ja φ ◦ σ e a operacao que envia P para

φ(σ(P )).

Um conjunto de endomorfismos de E e fornecido pela multiplicacao de pontos da curva

por inteiros. Seja φ(P ) = nP e σ(P ) = mP . Entao φ(P )+σ(P ) = nP +mP = (n+m)P ,

e φ(P ) ◦ σ(P ) = φ(σ(P )) = n(mP ) = (nm)P . Claramente, estes sao endomorfismos

validos, de modo que End(E) possui uma copia isomorfica dos inteiros Z. Pode-se provar

que, em geral, esses sao os unicos endomorfismos de E, ou seja, End(E) ∼= Z. Porem,

para uma certa classe de curvas, End(E) e ligeiramente maior que Z, sendo isomorfico

a uma ordem em um corpo quadratico imaginario de numeros1. Neste caso, diz-se que

a curva E tem multiplicacao complexa, ou que e uma curva CM (CM e a abreviacao de

complex multiplication, o termo em ingles para estas curvas).

A teoria de multiplicacao complexa e bastante vasta, e esta alem do escopo deste

trabalho. Desse modo, a exposicao estara concentrada somente nos resultados da teoria,

e como estes podem ser empregados para forjar um teste de carater primo mais eficiente.

A primeira definicao relacionada a teoria e a de discriminante fundamental de um

corpo quadratico imaginario (2). Esta e a definicao corrente na literatura para trabalhos

teoricos, mas uma definicao alternativa, a de discriminante reduzido, e mais popular em

trabalhos focados no aspecto computacional (20).

Definicao 4.4.1. Um inteiro negativo D e um discriminante fundamental se a parte

ımpar de D nao possui fatores primos repetidos, e |D| ≡ 3, 4, 7, 8, 11, 15 (mod 16).

A relacao entre um discriminante fundamental D e um discriminante reduzido D′ e a

seguinte (21).

1Formalmente, uma ordem e um subanel de ındice finito do anel de inteiros algebricos do corpo. Infeliz-mente, estas definicoes estao alem do escopo do trabalho, mas nao sao necessarias para o desenvolvimentoque se segue.

53

• Se |D′| ≡ 1, 2 (mod 4), entao |D| = 4|D′|, caso contrario, |D| = |D′|;

• Se |D| ≡ 0 (mod 4), entao |D′| = |D|/4, caso contrario, |D′| = |D|.

Por convencao, sera admitido que os discriminantes reduzidos sao positivos. O restante

desta secao lidara com discriminantes reduzidos, de modo que, exceto quando indicado,

qualquer mencao a um discriminante D sera a forma reduzida.

Pode-se verificar, pelas classes de congruencia permitidas para um discriminante fun-

damental, que as duas definicoes sao funcionalmente equivalentes; nenhuma delas con-

templa uma classe maior de discriminantes que a outra. Deve-se tomar cuidado para

nao confundir as duas definicoes durante a implementacao das rotinas de multiplicacao

complexa.

A cada discriminante esta associado um grupo de classe H(D). Antes de definir este

grupo, e necessaria a seguinte definicao (20).

Definicao 4.4.2. Uma matriz simetrica reduzida possui a forma

S =

[A B

B C

],

onde os inteiros A, B, C satisfazem as seguintes condicoes:

1. mdc(A, 2B, C) = 1;

2. |2B| ≤ A ≤ C;

3. Se A = |2B| ou A = C, entao B ≤ 0.

Por razoes de economia de espaco, a matriz S sera abreviada como [A, B, C].

Definicao 4.4.3. Seja D = AC − B2 o determinante da matriz S da Definicao 4.4.2.

O grupo de classe H(D) corresponde ao conjunto de matrizes simetricas reduzidas de

determinante D. O numero de classe h(D) e a cardinalidade do conjunto H(D).

A determinacao do grupo de classe de um determinado discriminante pode ser feita

pelo seguinte algoritmo.

Algoritmo 4.4.1. Dado um discriminante reduzido D, o algoritmo determina o grupo

de classe H(D).

54

1. [Inicializacao]

s = d√

D/3e;H(D) = ∅;

2. [Laco]

for (0 ≤ B ≤ s) {Listar os divisores positivos A1, . . . , Ar de D + B2 tais que 2B ≤ A ≤

√D + B2;

for (1 ≤ i ≤ r) {C = (D + B2)/Ai;

if (mdc(Ai, 2B, C) == 1) {H(D) ∪ [Ai, B, C];

if (0 < 2B < Ai < C)

H(D) ∪ [Ai,−B, C];

}}

}

Uma vez que os discriminantes envolvidos sao relativamente pequenos (nao mais que

10 dıgitos), nao e preciso usar algoritmos sofisticados de fatoracao para encontrar os

divisores pedidos; o metodo de trial divison e rapido o suficiente para os propositos do

algoritmo.

De posse do grupo de classe de um discriminante, e possıvel construir o polinomio re-

duzido de classe wD(x), um polinomio de coeficientes inteiros e grau h(D). Esse polinomio

sera aplicado a seguir na construcao de curvas elıpticas com multiplicacao complexa.

Antes de descrever a construcao desse polinomio, sao necessarias algumas definicoes.

Seja

F (z) = 1 +∞∑

j=1

(−1)j(zj(3j−1)/2 + zj(3j+1)/2

)= 1−

(z + z2

)+(z5 + z7

)−(z12 + z15

)+ . . .

Define-se tambem

θ = exp

(−√

D + jB

Aπ

).

55

onde j =√−1, e as funcoes

f0(A, B, C) = θ−1/24F (−θ)/F (θ2),

f1(A, B, C) = θ−1/24F (θ)/F (θ2),

f2(A, B, C) =√

2θ1/12F (θ4)/F (θ2).

E possıvel agora definir o invariante de classe W (A, B, C) (20), cujo calculo envolve a

verificacao de diversas condicoes especiais, e nao e reproduzido aqui por falta de espaco.

Se [A1, B1, C1], . . . , [Ah, Bh, Ch] (onde h = h(D)) sao as matrizes simetricas reduzidas

de determinante D, entao o polinomio reduzido de classe para D e

wD(x) =h∏

j=1

(x−W (Aj, Bj, Cj)).

As raızes modulares deste polinomio permitem a construcao de curvas elıpticas com

ordem de grupo pre-determinada. Se a curva e considerada sobre o corpo Z/pZ, essa

ordem e dada por p + 1± U , onde U provem da solucao da equacao

4p = U2 + DV 2, (4.3)

nas variaveis U, V , com D > 3 dado, desde que a equacao tenha solucao. Diz-se que E tem

multiplicacao complexa por√−D. Para o caso D = 3, ha 6 ordens de grupo possıveis,

mais especificamente p + 1 ± U e p + 1 ± (U ± 3V )/2. No caso D = 1, ha 4 ordens de

grupo possıveis, p + 1± U e p + 1± 2U .

A primeira questao a ser levantada e como resolver a equacao (4.3). O algoritmo

de Cornacchia (2), dado a seguir, pode ser utilizado para resolver a equacao de forma

eficiente.

Algoritmo 4.4.2. Dado um primo p e um discriminante D tal que 0 < D < 4p e D ≡ 0, 3

(mod 4), este algoritmo determina U, V tal que 4p = U2+DV 2, ou afirma que uma solucao

nao existe.

1. [Teste de solvabilidade]

if ((Dp) 6= 1)

return ‘Nao existe solucao’;

2. [Raiz quadrada modular]

x0 =√−D (mod p);

56

if (x0 6≡ D (mod 2))

x0 = p− x0;

3. [Inicializacao da cadeia de Euclides]

(a, b) = (2p, x0);

c = b2√pc;

4. [Cadeia de Euclides]

while (b > c)

(a, b) = (b, a mod b);

5. [Conclusao]

t = 4p− b2;

if (t 6≡ 0 (mod D))

return ‘Nao existe solucao’;

if (t/D nao e quadrado perfeito)

return ‘Nao existe solucao’;

return (b,√

t/D);

Caso a ordem do grupo apresente as propriedades desejaveis para a aplicacao em

questao, efetua-se a construcao da curva. O primeiro passo e a geracao do polinomio

reduzido de classe, e sua reducao modulo p (que e a caracterıstica do corpo-base da

curva). Apos isso, e preciso determinar uma raiz modulo p do polinomio, podendo-se

aplicar por exemplo o metodo de Cantor-Zassenhaus (1, 2, 12). De posse da raiz do

polinomio, emprega-se um algoritmo descrito em (20) para construir uma curva E com

uma das ordens de grupo indicadas. A curva que apresenta a outra ordem de grupo

possıvel e dita o twist quadratico de E, e sua relacao com E e bastante simples (20):

basta determinar um resıduo nao-quadratico g de p, e multiplicar os coeficientes a e b da

equacao na forma (3.1) por g2 e g3, respectivamente.

Resta determinar qual das duas ordens corresponde a qual curva. Felizmente, isso e

simples, uma vez que qualquer ponto sobre uma curva elıptica, quando multiplicado pela

ordem do grupo correspondente, resulta no ponto no infinito O, enquanto a multiplicacao

por outro valor escolhido aleatoriamente resulta em um ponto qualquer diferente de O.

Uma observacao: formalmente, e possıvel que a ordem do grupo de uma das curvas coin-

cida com a ordem do ponto gerado para outra curva, levando a uma conclusao erronea

a respeito das associacoes entre curvas e ordens de grupo, mas esse evento tem proba-

bilidade desprezıvel. Se mesmo assim houver interesse em eliminar esta possibilidade, e

57

possıvel procurar uma ‘testemunha’ para o fato que um dado valor nao corresponde a

ordem do grupo considerado, pela aplicacao da contrapositiva da afirmacao do comeco do

paragrafo.

4.5 O algoritmo ECPP de Atkin e Morain

Em (14), Atkin e Morain sugeriram alterar o algoritmo ECPP de Goldwasser e Kilian,

substituindo a geracao de curvas aleatorias e determinacao da ordem do grupo pelo algo-

ritmo de Schoof, pelo uso de curvas elıpticas com multiplicacao complexa. Essa alteracao

e bastante vantajosa, uma vez que o tempo de execucao do algoritmo para demonstrar o

carater primo de um inteiro p cai para O ((log p)5+ε), e o teste mostra-se bastante pratico.

Devido a semelhanca com o algoritmo de Goldwasser e Kilian, e por razoes de espaco,

o algoritmo de Atkin e Morain nao sera explicitado aqui.

E possıvel realizar tambem uma modificacao no formato dos certificados para o al-

goritmo de Goldwasser e Kilian: ao inves de fornecer os coeficientes da curva, e possıvel

fornecer apenas o discriminante, exigindo a reconstrucao do polinomio durante a veri-

ficacao, o que e viavel quando o esforco exigido para construir o polinomio nao e muito

grande. Em casos extremos, e possıvel construir certificados com alto grau de compressao

fornecendo somente o discriminante, e exigindo do verificador a determinacao da ordem

do grupo pelo algoritmo de Cornacchia, a fatoracao desta ordem e a construcao da curva.

Mesmo assim, a verificacao e mais eficiente que a certificacao, uma vez que o grande gar-

galo do algoritmo e encontrar discriminantes que produzam solucao para a equacao (4.3)

e que sejam completamente fatoraveis, satisfazendo as condicoes do Teorema 4.3.1.

4.6 A variante fastECPP do algoritmo ECPP

Concluımos o capıtulo com uma melhoria que pode ser feita ao esquema basico de

Atkin e Morain, e que reduz sua complexidade de O ((log n)5+ε) para O ((log n)4+ε).

Verifica-se que, durante a execucao do algoritmo de Atkin e Morain, a maior parte do

tempo e dispendida na execucao do algoritmo de Cornacchia. Este algoritmo envolve a

extracao da raiz quadrada modular do discriminante sob consideracao.

Retornando a teoria de multiplicacao complexa, e possıvel especificar a fatoracao em

primos de um discriminante fundamental valido (14). O algoritmo fastECPP considera

58

uma pequena base de primos pi e tenta construir todas as combinacoes de fatores possıveis

a partir dessa base. Precomputando os valores de√

pi (mod p), e possıvel construir um

discriminante pelo produto dos pi’s e sua raiz quadrada pelo produto dos√

pi’s corres-

pondentes. Desta forma, a excecao das precomputacoes, o custo das raızes quadradas e

efetivamente eliminado do algoritmo de Cornacchia. A contrapartida e que nem todos

os discriminantes possıveis serao considerados, apenas aqueles cuja fatoracao em primos

possa ser expressa atraves dos pi’s escolhidos.

Observa-se que nem todos os primos podem ser adicionados a base de fatores em

questao: somente aqueles tais que(

p∗in

)= 1, onde p∗i =

(−1n

)pi e n e o numero cujo

carater primo esta sendo verificado. Pode-se observar que alguns primos da base de

fatores possuirao sinal negativo; isto limita as combinacoes possıveis entre eles, uma vez

que o produto final deve ser obrigatoriamente negativo.

Ha outra vantagem em utilizar este metodo, relacionada a fatoracao modulo n do

polinomio de classe. Conforme n cresce, este e o passo que domina o tempo de execucao

do algoritmo, devido ao alto grau dos polinomios envolvidos: sabe-se que na media, h(D)

comporta-se como 0, 46√|D| (12), tornando a fatoracao do polinomio inviavel se p e muito

grande, mesmo para valores moderados de D. Felizmente, Atkin e Morain descrevem uma

tecnica de fatoracao algebrica do polinomio de classe, denominada fatoracao sobre o corpo

de genero, permitindo obter fatores de grau h(D)/2k, onde k e o numero de fatores primos

do discriminante D. A obtencao de discriminantes de alto valor no algoritmo fastECPP

esta geralmente associado a um maior numero de fatores primos do discriminante, o que

por sua vez leva a fatoracoes algebricas de grau menor, constituindo uma especie de

realimentacao negativa no sistema.

59

5 Sistemas Distribuıdos

O capıtulo introdutorio deste trabalho ja apresentou argumentos para o uso de com-

putacao distribuıda na solucao de problemas computacionais de grande magnitude. As-

sim, este capıtulo estara confinado a discussao dos obstaculos que surgem na imple-

mentacao de uma versao distribuıda de um algoritmo.

Sistemas distribuıdos de larga escala geralmente apresentam altas latencias e baixa

vazao de comunicacoes, com relacao a interconexoes dedicadas e mesmo redes locais co-

mercialmente disponıveis como a Ethernet. A Secao 5.1 discute a distribuicao do algoritmo

ECPP, e argumenta que ele se adapta a um sistema sujeito as restricoes discutidas. A

Secao 5.2 mostra como aumentar a eficiencia da propagacao de informacoes num sistema

distribuıdo, e propoe uma arquitetura de rede adaptada ao ECPP e que leva essas ideias

em conta. Por fim, a Secao 5.3 discute os desafios de realizar computacoes validas quando

os nos da rede podem nao ser confiaveis, contemplando desde falhas de hardware ate

ataques maliciosos ao sistema.

5.1 Distribuindo o algoritmo ECPP

Relembramos aqui os passos principais da variante fastECPP do algoritmo ECPP,

lembrando que o algoritmo comeca com n0 = n e termina quando ni e pequeno o suficiente

para ter seu carater primo demonstrado por outros metodos. Omitiu-se as condicoes de

falha do algoritmo e a forma como devem ser tratadas, pois sao irrelevantes a discussao

desta secao.

1. Precomputacoes:

(a) Gerar uma lista de primos que podem ser fatores de discriminantes fundamen-

tais, conforme discutido na Secao 4.6;

(b) Precomputar raızes quadradas modulares dos elementos na base de fatores;

60

2. Encontrar um discriminante valido D:

(a) Construir discriminantes possıveis Dj a partir de multiplicacoes dos elementos

da base de fatores;

(b) Usando o algoritmo de Cornacchia, encontrar os valores de Dj tais que 4ni =

U2 + DjV2 possui solucao;

(c) Dentre as solucoes da equacao acima, encontrar uma ordem de grupo de uma

curva elıptica com multiplicacao complexa por√−Dj, que possa ser fatorada

conforme as condicoes do Teorema 4.3.1;

3. Construir uma curva elıptica com multiplicacao complexa por√−D, onde D e o

discriminante encontrado no item 2(c);

4. Verificar as condicoes do Teorema 4.3.1 para esta curva e a fatoracao encontrada no

item 2(c);

5. Executar o algoritmo para ni+1, o cofator primo da ordem de grupo da curva em

questao.

As precomputacoes do passo 1 sao comuns a todos os clientes da rede. A secao seguinte

discute como evitar que estas precomputacoes sejam repetidas em todos os clientes, e ao

mesmo tempo evitar uma carga muito grande de comunicacao com o servidor.

O algoritmo permanecera no passo 2 durante a maior parte de sua execucao, e e

justamente este passo que apresenta possibilidades de paralelizacao. Observa-se que cada

processador poderia receber um Dj, para executar o passo 2(b) e possivelmente o passo

2(c) de maneira independente dos demais.

Para minimizar os requisitos de comunicacao, nao e interessante fornecer apenas um

Dj a cada processador por vez, e sim um conjunto de Dj’s. Tambem nao seria interessante

que o servidor central gerasse esse conjunto de Dj’s, para minimizar a carga computacional

sobre o mesmo. Nossa implementacao conciliou os dois requisitos da seguinte maneira:

representa-se um subconjunto de elementos da base de fatores por uma string de bits, onde

os valores 0 ou 1 de cada bit indicam a presenca ou ausencia de um primo da base de fatores

nesse subconjunto. Esta string de bits pode ser interpretada como um numero binario,

possibilitando a especificacao bastante compacta de intervalos de busca. Por exemplo, o

intervalo 001-111 indica que o cliente deve considerar os subconjuntos representados por

001, 010, 011, 100, 101, 110 e 111. Esses correspondem aos discriminantes D001 = p1,

D010 = p2, D011 = p1p2, . . . , D111 = p1p2p3.

61

E difıcil prever a quantidade de computacao delegada a cada cliente atraves desse

esquema. Em princıpio, poderia-se realizar uma analise levando em conta que a proba-

bilidade de um dado D satisfazer a equacao do passo 2(b) e 1/(2h(D)), onde h(D) e o

numero de classe do discriminante D (14). Existem tambem estimativas para os valores

de h(D), dado D (12). Mas ainda e preciso conhecer a distribuicao dos valores de D

nos intervalos de subconjuntos discutidos acima para poder aplicar estas estimativas, e

o autor desconhece algum metodo que possa simplificar a analise deste problema. Desta

forma, heurısticas terao de ser desenvolvidas para distribuir uma quantidade razoavel-

mente padronizada de computacao para cada cliente.

Quanto aos passos 3 e 4, nao e viavel distribuir as computacoes envolvidas nos mesmos,

e nem e necessario. Estes passos falharao apenas com probabilidade desprezıvel (tao baixa

quanto a probabilidade de falha de um teste de carater pseudoprimo), de forma que estas

computacoes sao delegadas a um unico cliente da rede, enquanto os demais ja comecam

a trabalhar na certificacao do proximo primo da cadeia, o cofator da ordem do grupo em

questao. Caso ocorra uma falha nos passos 3 e 4, todos os clientes da rede devem retornar

a certificacao do primo anterior da cadeia, mas como dito, a probabilidade de ocorrencia

deste evento e desprezıvel.

O passo 5 do algoritmo, que exige a migracao de todos os clientes da rede para uma

nova tarefa, tambem levanta questoes relacionadas a minimizacao da carga de comu-

nicacao do servidor central. Novamente, a tecnica de distribuicao de comunicacoes da

secao seguinte e util nesta situacao.

Deve-se observar tambem que, somente porque ha uma nova tarefa disponıvel, nao

significa que clientes trabalhando na tarefa antiga estejam desperdicando tempo de pro-

cessamento. Suponha por exemplo que a rede estivesse trabalhando na certificacao de ni,

um primo provavel de k bits, e que um dos clientes tenha encontrado uma curva cuja

ordem do grupo possua fatores pequenos, digamos 10 bits ao total, e um cofator ni+1 de

k − 10 bits. Enquanto o servidor migra os clientes para a certificacao de ni+1, um cliente

trabalhando na tarefa antiga encontra um curva cuja ordem do grupo possua fatores to-

talizando 20 bits, com um cofator de k− 20 bits. E vantajoso nessa situacao interromper

a certificacao de ni+1 e substitui-lo pelo novo cofator encontrado. Uma estrategia que

guarda semelhancas com a descrita, em que cofatores muito proximos do ni original sao

simplesmente descartados, foi utilizada com sucesso para reduzir o tempo de computacao

do ECPP distribuıdo (17).

62

5.2 Algoritmos para distribuicao de dados

A motivacao para esta secao e o seguinte problema: dada uma certa informacao,

presente em um no de um sistema distribuıdo, como transmitir esta informacao para todos

os nos do sistema da forma mais eficiente possıvel? No contexto do algoritmo ECPP, esta

informacao poderia ser, por exemplo, um comando para migrar para a proxima tarefa de

certificacao, ou as precomputacoes necessarias para execucao do algoritmo. Na literatura,

esta operacao e conhecida como broadcast (7).

Vamos considerar o primeiro exemplo. Neste caso, o servidor central, que coordena

todas as tarefas da rede, recebeu de um cliente a informacao de que e possıvel proceder a

uma nova etapa de certificacao. Apos verificar a veracidade dessa informacao, o servidor

precisa notificar todos os clientes da rede que devem migrar para uma nova tarefa.

O servidor poderia conectar em cada um dos clientes e transferir esta informacao,

porem isto exigiria c conexoes (onde c e o numero de clientes na rede) por parte do

servidor, implicando em um alto custo de comunicacao para o mesmo. A quantidade de

tempo necessaria para realizar todas as conexoes tambem seria relativamente grande.

Permitindo aos clientes conectarem-se entre si, e possıvel distribuir a carga de conexoes

de maneira aproximadamente uniforme entre todos os elementos da rede. Primeiramente

numera-se cada elemento da rede de maneira aleatoria, exceto que ao servidor e atribuıdo

o numero 0. Num primeiro instante, o no 0 (o servidor) envia os dados aos no 1. Num

segundo instante, o no 0 envia os dados ao no 2, e o no 1 envia os dados ao no 3.

Prosseguindo desta forma, apos dlog2 ce passos, todos os nos da rede terao recebido os

dados, e a quantidade maxima de conexoes realizadas por no tambem e dlog2 ce. O

processo e ilustrado graficamente na Figura 5.1.

Figura 5.1: Propagacao eficiente de dados.

Pode nao ser desejavel envolver todos os usuarios na retransmissao das informacoes,

por exemplo por motivos de seguranca. Outra razao e que dois usuarios que estejam

63

por tras de firewalls nao conseguirao conectar-se entre si. Uma organizacao semelhante

seria uma estrutura hierarquica de nos, conforme ilustrada na Figura 5.2. Estes nos

poderiam ser nos privilegiados, executando um software diferente (e possivelmente nem

mesmo contribuindo para as tarefas com tempo de processamento), ou simplesmente nos

comuns, em que o administrador da maquina configurou a rede de maneira a permitir

conexoes. Em ambos os casos, estes nos serao conhecidos como proxies.

Figura 5.2: Estrutura hierarquica de rede.

Alem de reduzir os requerimentos de comunicacao no servidor central e o tempo

necessario a propagacao de informacoes pela rede inteira, as estruturas hierarquicas de

rede apresentam outra vantagem: e possıvel realizar verificacoes distribuıdas de validade

de resultados, uma medida descrita na secao seguinte para deteccao de usuarios maliciosos

ou com hardware defeituoso. No entanto, utilizar maquinas nao-confiaveis para verificar a

confiabilidade de resultados nao prove garantias de validade, de modo que alguns nos na

hierarquia devem ser nos cuja confiabilidade possa ser garantida de alguma forma. Mesmo

assim, verificacoes em nıveis mais baixos da hierarquia permitem a eliminacao de alguns

(senao todos) os resultados incorretos, diminuindo a carga sobre os nıveis superiores.

5.3 Computacao em ambientes nao-confiaveis

Como garantir que uma computacao realizada em um computador desconhecido esteja

correta, ou mesmo que ela tenha sido realizada de fato? Este e um dos grandes problemas

enfrentados pelas redes de computacao distribuıda atuais.

Primeiramente, e preciso questionar as razoes que levam participantes da rede a reali-

zar computacoes incorretas. Alguns casos estao relacionados a falhas de hardware, devidas

a componentes de baixa qualidade, susperaquecimento, ou a pratica conhecida como over-

64

clocking, que e a operacao de alguns subsistemas do computador fora de sua espeficacao.

Outra possibilidade sao indivıduos com intencoes maliciosas, dispostos a demonstrar a

vulnerabilidade dos sistemas distribuıdos a ataques. Uma ultima e importante possibi-

lidade esta relacionada as ‘estatısticas’ do projeto, que coletam dados como os usuarios

e times de usuarios que mais contribuıram para o projeto; alguns indivıduos, sem poder

computacional para avancar nesta lista, empregam meios ilıcitos para manipula-la.

A vulnerabilidade de um sistema distribuıdo a computacoes incorretas depende, em

ultima instancia, da vulnerabilidade do algoritmo implementado no sistema (o ECPP no

caso deste trabalho) para resolver o problema proposto. Felizmente, o ECPP possibi-

lita diversas verificacoes intermediarias da validade da computacao, todas de baixo ou

medio custo, que serao estudadas agora. Serao feitas referencias aos passos do algoritmo

fastECPP na ordem descrita na Secao 5.1.

Primeiramente, seja uma potencial fatoracao da ordem do grupo de uma curva elıptica,

realizada durante o passo 2 do algoritmo. A verificacao da validade deste resultado poderia

proceder da seguinte maneira:

1. Primeiramente, verifica-se se o discriminante em questao e valido. E razoavel exigir

que, ao inves de transmitir o discriminante em si, o cliente transmita os fatores

do discriminante, utilizando a representacao binaria de subconjuntos da base de

fatores discutida na Secao 5.1. Atraves deste artifıcio, a verificacao da validade do

discriminante e dispensada.

2. Verifica-se entao que a ordem do grupo e valida. Exceto para os casos D = −3,−4,

a ordem e dada por ni+1±U , onde ni e conhecido, e U satisfaz a relacao 4ni = U2+

DV 2, sendo que D tambem e conhecido. Pode-se exigir a transmissao de V junto

com o resultado, simplificando consideravelmente a verificacao, mas aumentando os

requerimentos de comunicacao; ou pode-se verificar que (4ni−U2)/D e um inteiro e

quadrado perfeito. Nem e preciso calcular uma raiz quadrada do valor para verificar

que o mesmo e um quadrado perfeito; pode-se utilizar os metodos descritos em (12),

que testam se o inteiro em questao e um resıduo quadratico modulo primos pequenos,

o que sempre ocorre quando o mesmo e um quadrado perfeito.

3. Por fim, determina-se se a fatoracao relatada da ordem de grupo e valida. E desejavel

que os fatores encontrados sejam transmitidos junto com o resultado; geralmente

o tamanho dos mesmos sera de algumas dezenas (ou no maximo poucas centenas)

de bits. Dividindo a ordem do grupo pelos fatores, o resultado deve ser um inteiro,

65

o que e de facil verificacao, mas tambem um primo provavel; a verificacao desta

ultima propriedade exige uma quantidade razoavel de computacao.

O ultimo passo, que envolve um teste de carater pseudoprimo, parece indicar que a

verificacao de validade nao possui tao baixo custo quanto desejavel. No entanto, e preciso

colocar este fato em perspectiva: a obtencao de valores que satisfacam as verificacoes

anteriores e uma tarefa relativamente custosa, bem mais custosa que o teste de carater

pseudoprimo. Isto sugere a seguinte estrategia: ao realizar o teste de carater pseudoprimo

sobre o cofator do resultado em questao, caso o teste afirme que o cofator e composto,

o proxy nao descartara os parametros em questao (como discriminante, ordem de grupo,

fatores, etc.) apos a verificacao, como poderia se esperar. Ao inves disso, estes parametros

sao armazenados (e possivelmente enviados a outros proxies) para que tentativas poste-

riores de verificacao usando este resultado sejam detectadas imediatamente, evitando o

desperdıcio de computacao. Assim, um adversario malicioso precisa executar uma quan-

tidade muito grande de computacao em troca de um pequeno desperdıcio nos proxies,

tornando tais ataques futeis.

Deve-se verificar tambem a validade dos resultados obtidos no item 3 e 4 do algoritmo

fastECPP. Felizmente, isto tambem e facil, uma vez que e a mesma tarefa que deve ser

realizada para verificar a validade de um certificado do ECPP. Poderia-se argumentar que

o custo de O ((log ni)2+ε), onde ni e o primo atual da cadeia de certificados, nao e tao

baixo assim. Porem, deve-se lembrar que a construcao de curvas e um evento que ocorre

com baixıssima frequencia; ha no total O(log n) destes eventos durante a certificacao de

um inteiro n.

Assumindo que resultados incorretos sejam devidos somente a hardware defeituoso, o

custo computacional das verificacoes e desprezıvel. No entanto, caso a rede seja alvo de

um ataque malicioso bem planejado, os protocolos de rede do sistema deverao levar este

fato em conta para evitar desperdıcios e ate uma possıvel exaustao de recursos.

Uma possibilidade e o esquema de (22) e seus sucessores; quando o cliente conectar a

um proxy para retornar resultados, sera exigido do cliente a realizacao de uma computacao

de alguns segundos, especıfica para aquela conexao. Isto limita a taxa de conexoes de

adversarios, enquanto usuarios honestos, que conectam pouco frequentemente, nao sao

afetados.

Ao mesmo tempo, pode-se empregar um sistema seguro de identificacao de usuarios,

baseado em assinaturas digitais. Deste modo, e possıvel associar resultados ao usuario

66

que produziu os mesmos, e rejeitar resultados de usuarios suspeitos. Poderia-se empre-

gar o esquema de (23) ou as versoes melhoradas de (24, 25), que permitem verificacao

extremamente rapida de assinaturas.

Por outro lado, devido aos problemas de hardware defeituoso ja mencionados, nao

se deve assumir que um resultado incorreto e sinal de ataque a rede: o usuario deve ser

informado do fato e posto em quarentena ate que corrija o suposto problema de hardware.

67

6 Projeto e Implementacao doSistema

A pior inimiga da seguranca e a complexidade . . . Nao existe substitutopara a simplicidade.

Bruce Scheneier

Otimizacao prematura e a raiz de todos os males.

Donald E. Knuth

Nesta secao, sao descritos os passos tomados para implementar o sistema descrito

ate agora. Inicialmente e resolvida a questao do licenciamento do projeto, e argumenta-

se a decisao de distribuir o software sob a licenca de software livre GPL. Em seguida,

sao descritos os princıpios que nortearam o projeto do sistema, para entao descrever em

detalhes o estagio atual da implementacao, incluindo a organizacao do codigo-fonte e

detalhes como estruturas de dados e algoritmos utilizados.

6.1 Licenciamento

Assim como qualquer outro software no mercado, e preciso decidir sob quais termos

de licenciamento o software sera distribuıdo.

A primeira e mais importante decisao neste sentido e se o software sera gratuito

ou pago. Nao foi difıcil decidir pela distribuicao gratuita, visto que o projeto depende

da doacao de recursos computacionais de voluntarios, e nao seria possıvel exigir destes

mesmos voluntarios que pagassem pelo direito de doar recursos ao projeto.

Em seguida, foi preciso decidir se o codigo-fonte do projeto seria distribuıdo aberta-

mente (open source) ou mantido em sigilo. A decisao pela distribuicao aberta foi natural:

visto que o software esta sendo distribuıdo gratuitamente, nao ha razao para esconder

seu codigo-fonte, mas ha diversas razoes para distribuı-lo. Pode-se citar a transparencia

68

do projeto perante os seus usuarios – que, deve-se lembrar mais uma vez, sao os unicos

responsaveis pelo eventual sucesso do projeto – e a facilidade de atrair outros desenvol-

vedores para o projeto, que nao precisam de uma afiliacao formal ao mesmo para enviar

melhorias, identificar brechas de seguranca, etc. Espera-se tambem que o codigo seja util

a outros projetos, da mesma forma como codigo de outros projetos foi reutilizado neste

sistema.

Tomada a decisao que o software seria distribuıdo gratuitamente e sob uma licenca

open source, resta decidir qual das licencas disponıveis sera empregada. Dentre as mais

notorias licencas desta classe, encontram-se a licenca BSD e a licenca GNU GPL. Ha

uma grande diferenca na filosofia das duas licencas, e em particular a licenca GPL exige

que modificacoes a um software com esta licenca sejam distribuıdas sob a mesma licenca.

O objetivo desta medida e evitar a apropriacao de codigo de um projeto, sem nenhuma

contrapartida ao autor deste codigo. Existem argumentos contra e a favor desta filosofia, e

a opiniao pessoal do autor e que se alguem teve acesso ao tremendo corpo de conhecimento

formado pelos softwares livres, e tomou emprestado destes softwares para construir seu

proprio, e obrigacao deste indivıduo contribuir de volta para a comunidade que viabilizou

seu projeto; caso o indıviduo considere isto um preco muito alto a pagar, ele tem a opcao

de escrever seu proprio projeto sem nenhuma contribuicao de terceiros.

Outro detalhe a favor da escolha da licenca GPL e a existencia de softwares dis-

tribuıdos atraves desta licenca, e que possuem codigos que podem ser reutilizados no

projeto. Um exemplo e o GMP-ECM, uma implementacao bastante eficiente de algorit-

mos de fatoracao como Pollard p − 1 e ECM. A quantidade de esforco necessaria para

produzir outra implementacao de mesma eficiencia, caso nao fosse feita a opcao pela

licenca GPL, seria gigantesca.

6.2 Projeto do sistema

O projeto do sistema foi norteado por diversas metas, listadas a seguir em ordem

aproximada de importancia.

1. correcao;

2. eficiencia;

3. escalabilidade;

69

4. seguranca;

5. facilidade de uso;

6. facilidade de manutencao:

(a) clareza;

(b) simplicidade;

(c) documentacao.

O restante desta secao esclarece o significado destas metas.

Correcao e a propriedade do sistema de realizar todas as operacoes corretamente.

Embora pareca uma propriedade tao obvia que nao deveria nem ser listada, infelizmente

muitos softwares atuais tem colocado a correcao em segundo plano. Pela propria natureza

de nosso sistema, fica claro que o funcionamento correto deve estar acima de todas as

demais metas.

A eficiencia tambem e uma das propriedades mais importantes do sistema; um sis-

tema ineficiente negaria todos os ganhos proporcionados pela distribuicao do algoritmo.

A principal ferramenta para garantir a eficiencia do sistema e a implementacao de me-

lhorias descritas na literatura, desde operacoes de baixo nıvel como aritmetica de inteiros

ate otimizacoes de alto nıvel como a fatoracao sobre o corpo de genero. Quando possıvel,

e reutilizado codigo de outras fontes que seja reconhecidamente eficiente para uma deter-

minada tarefa, por exemplo atraves do uso da biblioteca GMP para aritmetica de intei-

ros e ponto flutuante, e o programa GMP-ECM para fatoracao de inteiros. Quando as

melhorias algorıtmicas forem esgotadas, serao explorados outros meios de aumento de de-

sempenho, como o uso de multithreading para execucao paralela em SMPs e programacao

em linguagem assembly.

Escalabilidade e a propriedade do sistema de operar eficientemente na presenca de

grandes quantidades de clientes. Esta propriedade esta particularmente relacionada ao

projeto do protocolo de rede do sistema, e foi a principal motivacao para a proposta de

uma estrutura hierarquica de rede. A logica de verificacao de resultados, discutida na

Secao 5.3, tambem foi projetada com a escabilidade em mente; caso contrario, o sistema

seria vulneravel a ataques de exaustao de recursos.

A seguranca tambem e uma propriedade desejavel do sistema. Parte desta seguranca

esta relacionada a prevencao de erros de programacao, que podem levar a vulnerabilidades

70

que poem em risco os usuarios do software. Outro aspecto e o uso de protocolos crip-

tograficos para autenticacao dos usuarios com o objetivo de prevenir ataques ao sistema,

como a exaustao de recursos ja mencionada, e atribuicao incorreta de resultados, entre

outros.

Facilidade de uso e uma propriedade que torna o sistema atrativo para os usuarios.

As ferramentas para garantir esta propriedade sao o projeto de interfaces de usuario

seguindo recomendacoes de especialistas, e a prevencao da delegacao de decisoes desne-

cessarias e confusas para o usuario. O website do projeto tambem deve apresentar esta

propriedade, por corresponder ao primeiro contato que o usuario tera com o projeto, alem

de ser um recurso valioso para a operacao do sistema: facilidades como relatorios de

bugs, verificacao de estatısticas, gerenciamento de listas de discussao, etc. serao realiza-

dos atraves do website, e devem levar a conta a experiencia do usuario tanto quanto a

funcionalidade.

Por fim, a facilidade de manutencao esta relacionada a diversos fatores ja citados;

por exemplo, a simplicidade esta relacionada a seguranca e correcao do sistema, pois

facilita a analise do mesmo com vistas a estes objetivos. Por outro lado, a simplicidade

geralmente e concorrente da eficiencia, devido a todas as melhorias que necessitam ser

implementadas para obtencao de maxima eficiencia do sistema. Neste caso, as ferramen-

tas para lidar com a complexidade sao a clareza e a documentacao, uma vez que nao

ha nada mais nocivo ao sistema que tentar modificar o codigo sem compreender comple-

tamente a operacao do trecho que esta sendo modificado. Os princıpios citados tambem

sao desejaveis para atrair outros desenvolvedores para o projeto, que se sentirao mais

motivados se puderem compreender facilmente a operacao do codigo.

Uma decisao muito importante e que afeta o projeto como um todo e a escolha da

linguagem de programacao e da metodologia de projeto. Foram escolhidas, respectiva-

mente, a linguagem C++ e a metodologia de projeto orientado a objeto, por poderem

ajudar a gerenciar a complexidade do sistema quando corretamente aplicadas (26).

6.3 Implementacao do sistema

Nesta secao, e descrito o codigo do programa, que foi fornecido num CD-ROM em

anexo ao trabalho. Exceto quando indicado, os arquivos descritos encontram-se no di-

retorio src/algorithms do disco.

71

6.3.1 Aritmetica de inteiros e de ponto flutuante

As operacoes mais basicas de todo o sistema sao a aritmetica de inteiros e de ponto

flutuante. Todas as demais operacoes dependem destas de uma maneira ou outra, e os

atributos da aritmetica usada (como eficiencia e clareza de codigo) influenciarao signifi-

cativamente nos atributos do sistema como um todo.

Decidiu-se pelo emprego da biblioteca GNU MP (27) para esta funcao. As principais

razoes para esta decisao foram a reconhecida eficiencia desta biblioteca (embora ainda

deixe a desejar em alguns aspectos), e a interface da biblioteca para C++: sua imple-

mentacao e baseada na tecnica de gabaritos de expressoes (28), que utiliza o mecanismo de

sobrecarga de operadores de C++ para maxima clareza do codigo, ao mesmo tempo que

elimina tradicionais ineficiencias causadas por este mecanismo, como criacao desnecessaria

de temporarios.

6.3.2 Algoritmos para teoria dos numeros

A biblioteca GMP ja implementa diversos algoritmos para teoria dos numeros, como

pode ser constatado em sua documentacao: o algoritmo de Euclides para maximo divisor

comum, a versao estendida do algoritmo de Euclides para inversao modular, sımbolos

de Jacobi e Legendre e testes de carater pseudoprimo. No entanto, a implementacao do

ECPP exige outros algoritmos nao contemplados nesta lista, como raiz quadrada modular,

o algoritmo de Cornacchia e fatoracao de inteiros.

O primeiro detalhe e que os testes de carater pseudoprimo foram reimplementados. As

definicoes estao no arquivo prptests.h e a implementacao no arquivo prptests.cpp. O

teste de Frobenius, descrito na Secao 4.1, foi implementado devido a ausencia do mesmo na

biblioteca. A funcao para isso chama-se frobprp. Ja o teste forte de carater pseudoprimo,

embora esteja presente no GMP, foi reimplementado para utilizar exclusivamente a base 2

e o Algoritmo 2.3.4, com a melhoria descrita na Secao 2.3.3, que permite a substituicao de

algumas multiplicacoes por adicoes no algoritmo. A funcao que implementa este algoritmo

chama-se sprp. Ha tambem um wrapper para as duas funcoes, chamado ispseudoprime,

que testa o carater pseudoprimo de um inteiro aplicando inicialmente o teste forte, e caso

o inteiro seja declarado primo provavel por este teste, aplica-se o teste de Frobenius.

O calculo de raızes quadradas modulares e feito pela funcao modsqrt, definida no

arquivo modsqrt.h e implementada no arquivo modsqrt.cpp. Inicialmente o algoritmo

implementado havia sido o de Cipolla (Algoritmo 2.3.6), mas devido ao baixo desempenho

72

do mesmo, foi implementado o algoritmo de Tonelli (2).

O algoritmo de Cornacchia foi definido no arquivo cornacchia.h e implementado

no arquivo cornacchia.cpp. O nome da funcao e simplesmente cornacchia. A imple-

mentacao segue a exposicao de (2), exceto por desconsiderar algumas verificacoes de erro,

e por tomar como um dos argumentos a raiz quadrada de D modulo p. A razao para isto

e que, como descrito na Secao 4.6, a variante fastECPP do algoritmo ECPP permite a

construcao de raızes quadradas modulares a partir de precomputacoes. Desta forma, ao

inves de calcular a raiz quadrada por uma chamada a modsqrt, o valor da raiz quadrada ja

e passada a funcao, e o metodo de calculo da mesma fica a criterio da funcao chamadora.

Para fatoracao de inteiros, foram implementados os algoritmos de trial division e Pol-

lard rho, e reutilizado o codigo do programa GMP-ECM para o algoritmo Pollard p− 1,

com possibilidade de reutilizar tambem o codigo do algoritmo ECM no futuro, caso haja

necessidade. A definicao das funcoes e feita no arquivo intfact.h e a implementacao no

arquivo intfact.cpp, a excecao do codigo do GMP-ECM, que se encontra no diretorio

src/gmpecm da distribuicao. A implementacao destes algoritmos apresenta uma particu-

laridade: nao se buscam os fatores primos dos inteiros a serem fatorados, de modo que

qualquer divisor encontrado e adicionado a lista de fatores, sem tentar separa-lo em seus

fatores primos.

O algoritmo de trial division, implementado pela funcao trialdiv, emprega um tru-

que bastante conhecido para aumentar seu desempenho: ao inves de tomar o resto da

divisao de um inteiro por todos os primos ate um certo limite, precomputam-se produtos

de primos e potencias de primos no vetor P td, buscando que cada elemento do vetor pos-

sua aproximadamente o dobro do tamanho dos inteiros a serem fatorados pelo software.

E calculado o MDC entre o inteiro sendo fatorado e os elementos deste vetor, e quaisquer

divisores comuns encontrados nesse procedimento sao adicionados a lista de fatores do

inteiro. O calculo deste MDC envolve a divisao de dois inteiros gigantescos como passo

inicial, e neste ponto os algoritmos de divisao rapida implementados pela biblioteca GMP

aumentam a eficiencia com relacao ao algoritmo tradicional para trial division.

E preciso gerar uma lista de todos os primos ate um dado limite para a aplicacao do

algoritmo de trial division, e operacoes para manipular esta lista; isto e feito pelas funcoes

definidas no arquivo sieve.h e implementadas no arquivo sieve.cpp. O algoritmo uti-

lizado foi o Crivo de Eratostenes, Algoritmo 2.3.3, com a adicao de uma roda (em ingles,

wheel) para aumento de eficiencia. Buscando a economia de memoria, os primos sao lis-

tados numa estrutura de dados de 8 bits, que armazena somente a diferenca de um primo

73

em relacao ao seu antecessor dividida por 2 (uma vez que todos os primos, a excecao de

2, sao ımpares, a diferenca de dois primos e um numero par). Esta forma de armazena-

mento exige leitura sequencial da lista de primos, porem isto nao e uma limitacao para

os algoritmos que utilizam essa lista.

A implementacao do algoritmo Pollard rho, na funcao rho definida em intfact.h e

implementada em intfact.cpp, segue a exposicao de (12). E empregado o polinomio

x2 + 1 exclusivamente, e o metodo de busca de ciclos de Brent. Uma vez que os fatores

sao acumulados durante toda a execucao do algoritmo, e calculado somente um MDC ao

final do algoritmo, ao inves dos calculos frequentes sugeridos em (12).

Por fim, a funcao intfact implementa algumas heurısticas para tentar obter o maior

desempenho possıvel combinando os algoritmos de fatoracao descritos. Infelizmente, estas

heurısticas ainda nao estao satisfatorias; uma comparacao rudimentar foi realizada com

o software PRIMO de Marcel Martin (29), denunciando a atual inferioridade de nossa

implementacao.

6.3.3 Aritmetica de polinomios

Infelizmente, a biblioteca GMP nao oferece aritmetica de polinomios, que teve de

ser implementada pelo autor, por ser necessaria para a construcao de curvas elıpticas

com multiplicacao complexa. Dois conjuntos de rotinas foram implementados, uma para

polinomios com coeficientes complexos (representados em ponto flutuante), e outro para

polinomios com coeficientes provindos de Z/nZ.

6.3.3.1 Coeficientes complexos em ponto flutuante

Polinomios com coeficientes complexos sao empregados na construcao do polinomio

de classe (Secao 4.4). A classe que implementa as rotinas de aritmetica e manipulacao de

polinomios e definida e parcialmente implementada no arquivo complexpoly.h, enquanto

o restante da implementacao e feita no arquivo complexpoly.cpp.

Quanto as operacoes de adicao e subtracao, sao empregados os algoritmos tradicio-

nais, uma vez que nao existem opcoes mais eficientes. Ja a multiplicacao de polinomios

emprega tecnicas de multiplicacao rapida, uma vez que o grau dos polinomios envolvidos,

assim como a precisao de seus coeficientes, pode atingir valores bastante altos. Foram im-

plementados tres algoritmos com este fim: o algoritmo classico, o algoritmo de Karatsuba

e a convolucao por FFTs (1, 2). A decisao por cada um dos algoritmos e feita com base

74

no grau do polinomio sendo multiplicado; os limiares foram determinados atraves de ex-

perimentacao. Verificou-se um problema de cancelamento com o algoritmo de Karatsuba,

que leva a perda de precisao; desta forma, os limiares de Karatsuba foram ajustados de

forma a empregar outros algoritmos mesmo havendo uma pequena perda de desempenho

– somente quando a vantagem do algortimo de Karatsuba e muito grande que o mesmo e

empregado.

Foi implementado um FFT split-radix, nas variantes decimation-in-time (DiT) e

decimation-in-frequency (DiF) (30). A razao para isso e que, ao realizar um FFT DiF,

seguido de convolucao no domınio da frequencia e FFT inverso DiT, nao e necessario

realizar as operacoes de bit reversal do FFT. A implementacao seguiu o estilo da biblio-

teca FXT de Jorg Arndt (31). Deve-se observar que o uso de FFTs para esta tarefa foi

aparentemente negligenciado na literatura, mas levou a grandes ganhos de desempenho

em nossa implementacao.

Quanto a operacao de corpo, isto e, a multiplicacao de numeros complexos, foi empre-

gada uma identidade que permite a multiplicacao de dois numeros complexos atraves de

somente 3 multiplicacoes reais, ao inves das 4 esperadas (1, 32). A aplicacao desta identi-

dade tambem e controlada por um limiar sobre a precisao dos valores em questao, uma vez

que para valores muito pequenos, esta identidade e menos eficiente que a multiplicacao

tradicional.

6.3.3.2 Coeficientes modulares

Polinomios com coeficientes modulares sao empregados para obtencao de uma raiz

modular do polinomio de classe (Secao 4.4). A definicao e implementacao parcial da

classe e feita no arquivo modpoly.h, enquanto o restante da implementacao e feita no

arquivo modpoly.cpp.

Naturalmente, o algoritmo principal e o de fatoracao de polinomios. Por simplicidade,

foi implementado o algoritmo de Cantor-Zassenhaus (1, 2, 12). Outra possibilidade mais

eficiente e o algoritmo de Berlekamp (1), porem a quantidade de espaco exigida por este

algoritmo torna-o inviavel para a fatoracao de polinomios de alto grau. Uma possibili-

dade a ser estudada e o algoritmo de Kaltofen e Shoup (33), embora tambem existam

preocupacoes a respeito do espaco utilizado pelo algoritmo.

O algoritmo de Cantor-Zassenhaus consiste em exponenciacoes modulares (que por

sua vez empregam operacoes de multiplicacao e modulo) e MDCs. Este algoritmo e

75

implementado pela funcao polfact. Descrevemos agora os algoritmos utilizados para

garantir maxima eficiencia da rotina de fatoracao de polinomios.

Embora existam diversos algoritmos de multiplicacao especıficos para polinomios,

incluindo variantes do algoritmo de Karatsuba para multiplicacao de inteiros, e uma

tecnica empregando FFTs (33), decidiu-se pelo uso de binary segmentation (2), que nada

mais e que uma maneira de dispor os coeficientes de um polinomio em inteiros, de modo

que a multiplicacao de dois polinomios representados desta maneira nao provocara carries

(vai-uns) entre diferentes coeficientes do polinomio. Desta forma, e possıvel utilizar uma

rotina eficiente de multiplicacao de inteiros para emular uma multiplicacao de polinomios.

Este e o algoritmo implementado no operador de multiplicacao da classe.

A operacao de modulo foi implementada usando um algoritmo de reciprocidade analogo

aos metodos de Newton para inversao de valores em ponto flutuante (2). Deve-se observar

que este algoritmo exige uma precomputacao um pouco custosa para cada modulo a ser

empregado, de modo que nao e vantajoso quando o modulo e alterado frequentemente.

No entanto, para operacoes de exponenciacao modular, em que operacoes utilizando o

mesmo modulo sao repetidas multiplas vezes, o algoritmo e particularmente eficiente. A

implementacao foi realizada no operador de modulo da classe, utilizando as subrotinas

reciprocal, ind e rev.

Quanto as cadeias de exponenciacao, foi implementado o Algoritmo 2.3.4, embora

haja planos para implementacao de cadeias mais sofisticadas, como as descritas em (1, 5).

A funcao powmod implementa este algoritmo.

Tambem em nome da simplicidade, o algoritmo de MDC implementado na funcao gcd

foi o algoritmo de Euclides, onde a divisao de polinomios e realizada atraves de divisao

Euclidiana na funcao euclidrem, uma vez que o metodo de Newton nao seria vantajoso

nesse caso. E desejavel implementar futuramente o algoritmo de maximo divisor comum

recursivo, descrito em (2, 34).

6.3.4 Construcao dos polinomios de classe

Os procedimentos para construcao dos polinomios de classe sao definidos no arquivo

weber.h, que utiliza subrotinas definidas em weber-aux.h, enquanto as implementacoes

encontram-se em weber.cpp e weber-aux.cpp.

A funcao classgroup determina o grupo de classe de um dado determinante, utili-

zando a funcao divisors como subrotina para listar divisores de um inteiro. Esta funcao,

76

por sua vez, utiliza a funcao primefactors para determinacao dos fatores primos de um

inteiro atraves de trial division. Embora a eficiencia deste metodo possa ser questionada,

os inteiros a serem fatorados sao relativamente pequenos, e a preocupacao com a eficiencia

e infundada.

As funcoes F, f e C implementam as funcoes correspondentes descritas em (20). Pre-

computacoes sao realizadas quando possıvel, em particular para raızes quadradas e cubicas

de 2 na precisao desejada.

O arquivo weber.cpp emprega as funcoes auxiliares descritas para calculo do po-

linomio de classe. A funcao weber polynomial calcula o polinomio para uma dada

precisao de calculo. Esta e uma subrotina da funcao weber poly mod p, que contem

heurısticas para determinar a precisao necessaria para o calculo do polinomio de classe,

podendo repetir a computacao caso a precisao mostre-se insuficiente, e reduz o polinomio

modulo um primo p. A funcao build cm curve realiza todo o processo de construcao de

uma curva elıptica com multiplicacao complexa: primeiramente o calculo do polinomio

de classe reduzido modulo p, depois a obtencao de uma raiz deste polinomio modulo p, e

por fim a construcao da curva a partir desta raiz, conforme descrito em (20).

Neste ponto, e preciso comentar a respeito das heurısticas de precisao para o calculo

dos polinomios de classe. Existem estimativas de precisao obtidas analiticamente para o

calculo de polinomios de Hilbert (que tambem sao polinomios de classe, porem exigem

precisao superior aos polinomios de Weber empregados no trabalho). Estas estimativas

podem ser adaptadas para os polinomios de Weber, porem mostraram-se insatisfatorias

na pratica. Nesse sentido, foi desenvolvida uma heurıstica que tem se mostrado valida

nas computacoes realizadas neste trabalho.

Parte-se do princıpio que o polinomio de classe e um polinomio com coeficientes in-

teiros. Seja ai o maior coeficiente deste polinomio. Obrigatoriamente, e necessario um

mınimo de log2 ai bits para representar este inteiro. Para estimar o valor de log2 ai, inicial-

mente realiza-se a computacao do polinomio de classe em baixa precisao, por exemplo 128

bits. Este calculo e relativamente rapido (poucos minutos) e fornece uma boa estimativa

da precisao final necessaria. No entanto, devido as diversas computacoes intermediarias,

erros de arredondamento e problemas de estabilidade numerica dos algoritmos utilizados,

e preciso adicionar uma margem de seguranca ao valor calculado. No estagio atual de im-

plementacao, este valor e uma funcao do numero de classe e do discriminante em questao,

embora nao tenha sido realizado nenhum estudo a respeito das reais variaveis envolvi-

das. Uma linha de estudo neste sentido e a geracao de diversos polinomios de classe,

77

calculando a precisao mınima necessaria para a tarefa, e tentando utilizar metodos de

analise estatıstica e regressao para determinar heurısticas com uma certa fundamentacao

experimental.

6.3.4.1 Funcoes transcendentais

O calculo do polinomio de classe exige o uso da funcao exponencial e do valor de π.

Como os argumentos da funcao exponencial sao numeros complexos, decidiu-se pelo uso

da formula de Euler ejθ = cos θ+j sen θ para o calculo da parte imaginaria da exponencial.

Desta forma, e preciso implementar as funcoes exponencial, seno e cosseno, alem de um

metodo para calcular π. Estas funcoes sao definidas no arquivo transcendental.h e

implementadas no arquivo transcendental.cpp.

O calculo de π e feito atraves do celebrado algoritmo de Brent-Salamin, que usa o

conceito de media aritmetica-geometrica e certas relacoes envolvendo integrais elıpticas

(35, 36). A funcao em questao e chamada pi. A implementacao deste algoritmo e bastante

simples e sua convergencia e quadratica com relacao ao numero de dıgitos, indicando que

serao necessarias apenas algumas iteracoes para o calculo de π para praticamente qualquer

precisao pratica. Ademais, cada iteracao consiste essencialmente de uma operacao de

elevar ao quadrado e uma raiz quadrada, utilizando a formulacao de (37).

Ja as funcoes transcendentais sao calculadas atraves do metodo de (38). Este metodo

envolve um escalonamento do argumento das funcoes que acelera a convergencia, seguido

da aplicacao de identidades para escalonar o resultado final. O trabalho citado menciona

diversas tecnicas a serem aplicadas para garantir a manutencao da precisao maxima, como

a inclusao de uma palavra de guarda no calculo e identidades alternativas ao metodo

inicial proposto, que nao sofrem de problemas de cancelamento. Todas estas melhorias

foram implementadas para garantir a maxima eficiencia no calculo destas funcoes, uma

vez que sao chamadas repetidamente durante o calculo dos polinomios de classe. O

calculo de exponenciais reais e feito atraves da funcao exp, enquanto o calculo de senos e

cossenos e feito atraves das funcoes sin e cos. Ambas utilizam a funcao auxiliar cosm1,

que calcula cos x − 1 empregando as melhorias descritas. O calculo da funcao cosseno

a partir de cosm1 e direto, enquanto o calculo da funcao seno emprega a identidade

fundamental sen2 x + cos2 x = 1, novamente com modificacoes para prevenir o fenomeno

de cancelamento.

78

6.3.5 Aritmetica elıptica

O ultimo detalhe importante da implementacao e o sistema de coordenadas empregado

para aritmetica elıptica. E definida uma estrutura de dados para curvas elıpticas e pontos

sobre as mesmas, alem de operacoes sobre pontos, no arquivo elliptic.h, enquanto a

implementacao destas operacoes e realizada no arquivo elliptic.cpp.

Nao sao utilizadas as coordenadas afins e projetivas discutidas na Secao 3.3, mas

sim as chamadas coordenadas de Montgomery, propostas em (34). Este e um sistema

de coordenadas projetivas com uma mudanca crucial: os valores da coordenada y de

pontos da curva nunca sao calculados. Embora isso possa parecer absurdo, existem muitas

situacoes em que as coordenadas y sao dispensaveis. Aqui, a aplicacao da aritmetica

elıptica e na verificacao das condicoes do Teorema 4.3.1, em que basta decidir se um

ponto corresponde ao ponto no infinito O ou nao, e para esta operacao basta verificar se

as coordenadas x, z sao nulas ou nao.

Atraves do descarte das coordenadas y, e possıvel eliminar diversas adicoes e multi-

plicacoes da aritmetica em coordenadas projetivas, porem ha um detalhe importante: as

formulas para a adicao de dois pontos P1 e P2 exigem, alem das coordenadas dos pontos

em si, as coordenadas do ponto P1 − P2. Embora isto pareca limitar a utilidade das co-

ordenadas de Montgomery, e possıvel forjar um algoritmo de multiplicacao de pontos por

inteiros empregando as cadeias de Lucas discutidas na Secao 4.1.2. Recorda-se daquela

secao que a cada iteracao da cadeia, as coordenadas de kP, (k + 1)P sao conhecidas, e

e possıvel calcular as coordenadas de 2kP, (2k + 1)P ou (2k + 1)P, (2k + 2)P , onde k e

um inteiro e P e um ponto sobre uma curva. Observa-se que a diferenca entre os dois

elementos dos pares de coordenadas citadas e sempre P , que obviamente e conhecido.

No entanto, as cadeias de Lucas apresentam uma desvantagem: o calculo de nP exigira

invariavelmente 2dlog2 ne+ 1 operacoes elıpticas, enquanto uma cadeia de exponenciacao

comum exigira bem menos – mesmo o simples Algoritmo 2.3.4 exigira cerca de 1, 5dlog2 neoperacoes, supondo que n e um inteiro com uma distribuicao aproximadamente igual de

bits 1 e 0 em sua representacao binaria. Algoritmos mais sofisticados exibirao uma quan-

tidade ate menor de operacoes. No entanto, (2) defende as coordenadas de Montgomery

em funcao da grande economia de operacoes modulares para cada operacao elıptica indi-

vidual. Seria interessante implementar a aritmetica em outros sistemas de coordenadas

para efeito de comparacao, porem isto nao foi feito neste trabalho.

79

7 Resultados

Dentre as subrotinas do algoritmo ECPP, o maior esforco foi dispendido na imple-

mentacao da construcao de curvas com multiplicacao complexa. Assim, os resultados

deste trabalho consistirao exclusivamente de computacoes de curvas com multiplicacao

complexa por√−D, para valores bastante grandes de D.

As computacoes consistiram nas curvas citadas na dedicatoria e agradecimentos do

trabalho. Alguns dados a respeito destas computacoes sao fornecidos na Tabela 7.1, em

que todos os discriminantes sao dados na forma fundamental, ao inves da forma reduzida

empregada no restante do trabalho.

D h(D) h(D) precisao usando precisao usandoesperado heurıstica inical nova heurıstica

-1000147768 4128 14597 12832-2001806020 5904 20651 19104-3006633688 7248 25309 22656-4004850712 9536 29209 28864 29120-5022511288 9968 32711 30816-6005976568 9616 35770 31040 31296-7005075940 12504 38631 39648 40480-8011737892 12192 41313 39104 40000-9003700612 12760 43796 41408 42368-10000129528 16336 46156 50944 51968-20029259608 19676 65322 66880-50051763448 26272 103261 93792

Tabela 7.1: Dados das computacoes realizadas neste trabalho.

Deve-se observar que os numeros de classe dos discriminantes escolhidos estao muito

abaixo da media, dada pela formula 0, 461559√|D| (12). Isto foi proposital; o numero

de classe afeta diretamente o tempo de execucao do algoritmo (lembrando que o grau do

polinomio de classe a ser construıdo e igual ao numero de classe). Alem disso, a precisao

necessaria para os calculos tambem e funcao do numero de classe.

80

Para realizar estes calculos, criamos uma versao modificada do software que busca por

discriminantes com numero de classe abaixo de um certo limite, e comunica ao usuario os

discriminantes encontrados e seu numero de classe. Para cada um destes discriminantes,

foi executada a primeira passada do algoritmo de calculo do polinomio de classe (em-

pregando baixa precisao), para estimativa da precisao real necessaria. Os discriminantes

mais favoraveis encontrados nessa etapa sao os listados na Tabela 7.1. A quantidade de

processamento empregada nessa etapa foi cerca de 1,5 dia, em um computador Pentium

4 2,6 GHz com 1 GB de memoria RAM.

As curvas foram calculadas neste Pentium 4 2,6 GHz e em um Athlon XP 1,83 GHz

com 1 GB de RAM, gentilmente cedido por Heron Franklin, exceto pela ultima linha da

tabela. Esta computacao exigiu uma quantidade maior de memoria RAM e utilizou um

computador Athlon MP 1,66 GHz com 4 GB de RAM, pertencente a um dos laboratorios

do Departamento de Engenharia Eletrica. Os dez menores discriminantes foram calcu-

lados em menos de 2 dias de processamento nos dois computadores citados no inıcio do

paragrafo, sendo que ao mesmo tempo o programa de busca de discriminantes com baixo

numero de classe era executado no computador Pentium 4, de modo que o tempo real de

processamento e ainda menor. O discriminante -20029259608 exigiu pouco mais de 1 dia

de processamento no Athlon XP 1,83 GHz, enquanto o discriminante -50051763448 exigiu

mais de 2 dias de processamento no Athlon MP 1,66 GHz.

Deve-se observar que, durante as computacoes iniciais, foi descoberto que a heurıstica

para estimativa de precisao dos calculos estava subestimando a precisao real necessaria.

Os discriminantes -4004850712 e -6005976568 nao puderam ser calculados com a esti-

mativa inicial de precisao, mas a heurıstica de reestimativa de precisao em face deste

problema, que adiciona um multiplo do numero de falhas devidas a baixa precisao ate

entao, permitiu o calculo ainda na segunda tentativa. Atribuımos este problema ao con-

junto de dados utilizado para desenvolvimento da heurıstica inicial, que era composto de

discriminantes com numeros de classe mais proximos da media. Ademais, essa heurıstica

dependia somente da precisao estimada pelos calculos em baixa precisao e do numero de

classe. No entanto, observa-se na Tabela 7.1 que discriminantes com numero de classe

aproximadamente igual ainda apresentam divergencias na precisao necessaria, indicando

uma dependencia da precisao com o valor do discriminante em si. Este fato foi levado em

conta na formulacao da nova heurıstica, que tambem depende do valor do discriminante.

Atraves dela, os polinomios de classe restantes foram calculados na primeira tentativa

sem erros de baixa precisao.

81

E possıvel perceber que todos os discriminantes calculados sao divisıveis por 4, e ne-

nhum e divisıvel por 3. De fato, estes discriminantes apresentam propriedades desejaveis.

A divisibilidade por 3 leva a requerimentos muito maiores de precisao, em torno de 3 vezes

maiores. Ja a divisibilidade por 4 leva a caracterısticas mais proximas de discriminantes

menores, facilitando as computacoes: os numeros de classe sao visivelmente menores, e a

precisao exigida para as computacoes tambem e ligeiramente menor, que discriminantes

na mesma faixa nao divisıveis por 4.

Acreditamos que estes discriminantes representam novos recordes de computacao: o

maior discriminante anteriormente calculado (julho/2004), ate onde sabemos, e -8581560955

(39). Ate dezembro de 2004, nossas computacoes permanecem recordes.

82

8 Conclusao

Argumentou-se neste trabalho (particularmente nas Secoes 5.1 e 5.2) que e possıvel

realizar demonstracoes de carater primo em sistemas distribuıdos de larga escala. In-

felizmente, o objetivo original do trabalho, que era fornecer uma prova concreta disso,

atraves de um software que realizasse esta tarefa e fosse mais eficiente que as alternativas

monoprocessadas existentes, nao pode ser atingido por questoes de tempo.

Apesar disso, a implementacao parcial do sistema mostrou-se competitiva, pelo menos

na area em que foi dedicado mais esforco, a construcao de curvas elıpticas com multi-

plicacao complexa. Os resultados relatados nos Agradecimentos do trabalho, e discutidos

na Secao 7, incluem uma curva elıptica com multiplicacao complexa por um discriminante

que e (ate o conhecimento do autor) o maior ja empregado neste tipo de calculo.

Embora esse resultado pareca impressionante, ele tambem enfatiza uma das princi-

pais deficiencias da implementacao nesse ponto: conforme sao empregados discriminantes

progressivamente maiores nos calculos, a ineficiencia das rotinas de aritmetica modular de

polinomios fica mais clara, assim como as limitacoes do algoritmo de Cantor-Zassenhaus

implementado para a fatoracao desses polinomios. Mas otimizacao nenhuma nessas areas

permitira atingir resultados realmente espetaculares; para tanto, e preciso implementar

uma tecnica como a fatoracao sobre o corpo de genero, ou uma das tecnicas de solubi-

lidade por radicais introduzidas por Francois Morain, que levam em conta a estrutura

especial dos grupos de Galois dos polinomios de classe (40, Cap. 3.1) (41).

Outra deficiencia esta relacionado ao uso dos invariantes IEEE P1363 (20). Para

discriminantes divisıveis por 3, esses invariantes exigem uma precisao cerca de 3 vezes

maior que a media para discriminantes do mesmo tamanho. Outros invariantes foram

propostos na literatura, como γ2 (14), e devem ser implementados futuramente.

Tambem esta claro que as rotinas de aritmetica modular empregadas poderiam ser

melhoradas. Em (17), e utilizada a biblioteca FFTW para substituir as rotinas de mul-

tiplicacao da biblioteca GMP, obtendo-se um grande ganho de desempenho. Por outro

83

lado, o website do GMP (27) afirma que a versao 5.0 da biblioteca esta planejada para

novembro de 2005, incluindo diversos algoritmos de complexidade reduzida e uma rotina

de FFT mais eficiente para multiplicacao de inteiros. Desta forma, a melhor estrategia e

nao otimizar a aritmetica modular neste momento, mas sim completar a implementacao

do sistema e otimizar outras areas que necessitam de melhorias com maior urgencia, como

as descritas no paragrafo acima. Neste ponto, em que a nova versao do GMP ja deve estar

disponıvel, pode-se avaliar se ainda e vantajoso substituir suas rotinas de multiplicacao

por uma implementacao baseada na biblioteca FFTW.

Outra grande area de estudo e a selecao de parametros para os algoritmos de fatoracao

de inteiros. Experimentos preliminares indicam que os parametros atuais estao longe de

serem competitivos com outras implementacoes do ECPP. Neste sentido, o autor vislum-

brou uma nova forma de analise do algoritmo ECPP, que pode contribuir com esta selecao

de parametros, mas isto sera objetivo de um trabalho futuro. Deve-se estudar tambem

a precisao necessaria para calculo dos polinomios de classe: mesmo na geracao de alguns

resultados para este trabalho, foram observadas deficiencias na heurıstica utilizada ate

entao para estimativa de precisao. Nesse sentido, talvez uma abordagem experimental

para a determinacao do comportamento desse parametro seja valida, uma vez que as

abordagens teoricas se mostraram insatisfatorias.

84

ANEXO A -- Artigo Publicado no XXI

Simposio Brasileiro de

Telecomunicacoes

XXI SIMPOSIO BRASILEIRO DE TELECOMUNICACOES-SBT2004, 06-09 DE SETEMBRO DE 2004, BELEM, PA

Demonstracoes Distribuıdas de Carater Primo deLarga Escala

Decio Luiz Gazzoni Filho e Taufik Abrao

Resumo— Descrevemos uma implementacao distribuıda doalgoritmo ECPP devido a Atkin e Morain, para demonstracao decarater primo de inteiros de forma geral. Sugerimos uma novaarquitetura de rede para implementacoes distribuıdas, e umanova tecnica para estimativa de precisao de um dos calculosintermediarios do algoritmo. Por fim, relatamos um resultadopreliminar obtido com a atual implementacao.

Palavras-Chave— Numero primos, curvas elıpticas,demonstracoes de carater primo, computacao distribuıda

Abstract— We describe a distributed implementation of Atkinand Morain’s ECPP algorithm for primality proving of integerswithout special form. We suggest a new network architecture fordistributed implementations, and a new technique for estimatingthe precision of one of the intermediate computations of ECPP.Finally, we relate a preliminary result obtained with the currentimplementation.

Keywords— Prime numbers, elliptic curves, primality proofs,distributed computing

I. I NTRODUCAO

O grupo de pontos de uma curva elıptica tem se mostradouma importante ferramenta na criptografia e teoria dosnumeros computacional. Criptossistemas empregando o prob-lema do logaritmo discreto sobre este grupo tem se mostradoimbatıveis em certas aplicacoes, como smart cards [1]. Afatoracao de inteiros atraves do metodo ECM de Lenstraeo metodo mais eficiente conhecido [2] (exceto para modulosRSA [3]), e as demonstracoes de carater primo de inteiros deforma geral, atraves do algoritmo ECPP de Atkin e Morain,atingiram patamares de desempenho ineditos: ja foram obtidoscertificados de carater primo para inteiros de ate 7760 dıgitosem uniprocessadores [4] e 15071 dıgitos para implementacoesdistribuıdas [5].

Os numeros primos sao uma ferramenta basica deconstrucao de sistemas criptograficos.E possıvel argumentarque as demonstracoes de carater primo sao superfluas, emfuncao da existencia de algoritmos que indicam o caraterprimo de um numero com alta probabilidade, os chamadostestes de carater pseudoprimo (ver [6] para uma visao geraldo assunto). No entanto, para certas aplicacoes onde exige-seo maximo possıvel de seguranca, pode ser desejavel obter umcertificado de carater primo, que os testes de carater pseudo-primo nao podem fornecer. E embora os numeros primos deinteresse criptografico estejam ao alcance de implementacoesmonoprocessadas no momento, o desenvolvimento de novoscriptossistemas, ou de algoritmos que simplifiquem a quebra

Universidade Estadual de Londrina, Departamento de Engenharia Eletrica,Caixa Postal 6001, 86051-990 - Londrina - PR. Emails: decio@decpp.net,taufik@uel.br

dos criptossistemas atuais, pode requerer o uso de primosmaiores. Uma implementacao distribuıda permite, por exem-plo, que uma empresa certifique o carater primo de um inteiroutilizando apenas recursos ociosos dos computadores de suarede.

A proposta deste trabalhoe uma implementacao distribuıdaem larga escala do algoritmo ECPP (a implementacao de[5] restringe-se aclusters) na tentativa de estabelecer novosrecordes.

Na secao II, sao introduzidos os conceitos necessarios paracompreensao do funcionamento do algoritmo ECPP, queedescrito na secao III. Na secao IV, e discutida a estrategiapara paralelizacao do algoritmo e os compromissos necessariospara implementacoes em larga escala. Na secao V, e discutidaa implementacao do algoritmo e outras subrotinas necessariaspara sua operacao (fatoracao de inteiros, testes de carater pseu-doprimo etc.). Na secao VI, relatamos resultados preliminaresobtidos com a atual implementacao.

II. CURVAS EL IPTICAS

A equacao geral de um polinomio de grau 3, com coefi-cientes provindos de um corpoF e igualada a zero,e

ax3 + bx2y + cxy2 + dy3 + ex2+

+ fxy + gy2 + hx + iy + j = 0, (1)

com a, b, c, d 6= 0. Os pares ordenados(x, y) ∈ F × F quesatisfazem (1) sao ditas as solucoes afim da equacao. Taissolucoes sao estritamente relacionadasas solucoesprojetivasda curva, que satisfazem

ax3 + bx2y + cxy2 + dy3 + ex2z+

+ fxyz + gy2z + hxz2 + iyz2 + jz3 = 0. (2)

Se estas curvas foremsuaves, ou seja, nenhuma solucao daequacao apresentar as tres derivadas parciais simultaneamentenulas, entao a curvae dita umacurva elıptica. Impondo acondicao adicional que a caracterıstica do corpoF deve serdiferente de 2 e 3,e sabido que toda equacao da forma (2)pode ser transformada por uma mudanca de variaveis numaequacao da forma

y2z = x3 + axz2 + bz3, a, b ∈ F, (3)

cuja forma afimy2 = x3 + ax + b (4)

e conhecida comoparametrizacao de Weierstrass. Uma curvanesta formae suave se e somente se4a3 + 27b2 6= 0.

Independentemente de se estar empregando a forma afimou projetiva da curva, sera usada a notacao O para denotar

XXI SIMPOSIO BRASILEIRO DE TELECOMUNICACOES-SBT2004, 06-09 DE SETEMBRO DE 2004, BELEM, PA

o ponto no infinito que ocorre na forma projetiva da curva.Temos entao:

Definicao 2.1: Uma curva cubica suave da forma (2), comcoeficientes pertencentes a um corpoF e pelo menos umasolucao com coordenadas emF nao simultaneamente nulas,edita uma curva elıptica sobreF . Se a caracterıstica deF naofor 2 ou 3, a equacao (3) tambem define uma curva elıpticasobreF , contanto que4a3 + 27b2 6= 0. Denota-se porE(F )o conjunto de pontos com coordenadas emF que satisfazema equacao, adicionado do ponto no infinitoO. Ou seja,

E(F ) = {(x, y) ∈ F × F : y2 = x3 + ax + b} ∪ {O}.

A. O Grupo de Pontos de uma Curva Elıptica

O interesse criptografico nas curvas elıpticas surge dadefinicao de uma certa operacao sobre os pontos do conjuntoE(F ) dado pela Definicao 2.1, dando origem a um grupoabeliano. Parte-se de uma interpretacao geometrica para aoperacao do grupo quandoF = R, a partir da qual seraodeduzidas expressoes validas em qualquer corpo, ainda quea interpretacao geometrica perca o sentido. A operacao dogrupo sobre dois pontos distintose feita tracando uma reta quecontenha ambos os pontos, obtendo uma terceira intersecaodesta reta com a curva. Este pontoe entao refletido atraves doeixo x. Quando os pontos sao os mesmos, a reta empregadaea tangentea curva nesse ponto. A notacao padrao na literaturapara a operacao deste grupoe aditiva. Apos um pouco degeometria analıtica e algebra, obtem-se:

Definicao 2.2: SejaE(F ) uma curva elıptica definida pelaequacao (3) sobre um corpoF de caracterıstica diferente de2 e 3, e P1 = (x1, y1), P2 = (x2, y2) dois pontos naonecessariamente distintos sobre esta curva. Denotando porO oponto no infinito, define-se uma operacao comutativa+, comoperacao inversa−, como segue:

1. −P1 = (x1,−y1);2. P1 + P2 = (x3, y3), com

x3 = m2 − x1 − x2

y3 = m(x1 − x3)− y1,

onde ainclinacao m e definida por

m =

{y2−y1x2−x1

, sex1 6= x2

3x21+a

2y1, sex1 = x2.

E uma consequencia surpreendente que a operacao assimdefinida, em conjunto comE(F ), forme um grupo. Ademais,e conhecido um profundo teorema a respeito da ordem dessegrupo:

Teorema 2.3 (Hasse):A ordem#E(Fpk) do grupo de pon-tos de uma curva elıptica satisfaz a desigualdade

|#E − (pk + 1)| ≤ 2√

pk

Essencialmente, o teorema de Hasse afirma que a ordem dogrupo e proxima da caracterıstica do corpo-base.

B. Curvas Elıpticas com Multiplicacao Complexa

Seja −D um discriminante fundamental, i.e.D ≡3, 4, 7, 8, 11, 15 (mod 16) e D nao possui fatores primos

ımpares repetidos, e sejap um primo. Caso existamu, v ∈ Ztal que4p = u2 + Dv2 (o algoritmo de Cornacchia[7], [6]pode ser empregado para obter estes valores), entao existemcurvas elıpticas tais que

#E =

p + 1± u, p + 1± (u± 3v)/2 seD = 3,

p + 1± u, p + 1± 2v seD = 4,

p + 1± u seD > 4.

(5)

A teoria fornece entao metodos eficientes para a construcaode curvas com as ordens de grupo indicadas.

III. O A LGORITMO ECPPDE ATKIN -MORAIN

O seguinte teorema, fruto do trabalho de Goldwasser eKilian [8] numa primeira versao (teorica) do ECPP,e crucialpara o algoritmo:

Teorema 3.1:Sejan > 1 um inteiro relativamente primo a6 eE(Fn) uma curva elıptica modulon. Sejamm um inteiroe P ∈ E(Fn) um ponto da curva satisfazendo as seguintescondicoes:

1. Existe um fator primoq de m tal que

q >(

4√

n + 1)2

.

2. mP = O.3. (m/q)P 6= O.

Entao n e primo.Cason nao seja primo, a curva elıptica E(Fn) nao forma

um grupo, e nao sera possıvel satisfazer as condicoes doteorema.

A estrategia do algoritmo ECPPe construir diversas curvaselıpticas, ate obter uma ordem de grupom = #E(Fn) queseja fatoravel na pratica e que possua um fator pseudoprimop0 satisfazendo as condicoes do Teorema 3.1. Pela aplicacaodo teorema, obtem-se um certificado do tipo “sep0 e primo,entao n e primo”. Aplica-se o procedimento recursivamentesobrep0 para obter um certificado do tipo “sep1 e primo,entao p0 e primo”. Dessa maneira, constroi-se uma cadeia decertificados. . . → p2 → p1 → p0 → n, ate atingir pk ’scujo tamanho permita uma demonstracao de carater primo pormetodos mais simples, como o crivo de Eratostenes.

Na versao atual do ECPP, a construcao das curvas elıpticasemprega o metodo de multiplicacao complexa exposto acima[9]. O metodo envolve a aplicacao do algoritmo de Cornacchiapara obtencao da ordem do grupo, que sem modificacoes erelativamente custoso, por envolver uma raiz quadrada mod-ular. Uma ideia atribuıda a J. Shallite a construcao de umabase de fatores e raızes quadradas modulares precomputadas,combinando-se os elementos dessa base para a construcaode discriminantes, e removendo o custo das raızes quadradasda aplicacao do algoritmo de Cornacchia. Incidentalmente,discriminantes compostos de diversos fatores primos sao de-sejaveis na construcao da curva elıptica implıcita no Teorema3.1, por motivos descritos na secao V-B.

Um resumo do algoritmoe dado abaixo, para referenciafutura. A entradae o pseudoprimo atual na cadeia de certi-ficados, digamospi, e a saıda e o proximo pseudoprimo nacadeia,pi+1.

XXI SIMPOSIO BRASILEIRO DE TELECOMUNICACOES-SBT2004, 06-09 DE SETEMBRO DE 2004, BELEM, PA

1. Construa a base de fatores dos discriminantes,Q ={q∗1 , q∗2 , . . . , q∗r} para umr qualquer, e precompute asraızes quadradas modulo pi da base de fatores,S ={√

q∗1 ,√

q∗2 , . . . ,√

q∗r}.2. Construa discriminantes−Dj como produtos de sub-

conjuntos deQ, tentando representa-los na forma4qi =u2 + Djv

2.3. Para os discriminantes que possuem uma representacao

nessa forma, tente fatorar as possıveis ordens de grupo(5), buscando um inteiro da formax = mqi+1, onde ocofatorqi+1 e um pseudoprimo que satisfaz as condicoesdo Teorema 3.1.

4. Construa uma curva elıptica com a ordem de grupoobtida no item anterior, e verifique as condicoes doTeorema 3.1 para essa curva e um ponto escolhido aoacaso.

5. Se as condicoes do teorema forem satisfeitas, o algo-ritmo termina com resultadoqi+1.

Se o algoritmo esgotar os discriminantes possıveis, existemtres saıdas: repetir as computacoes sobre os discriminantesexistentes (aplicando um esforco maior na busca de fatoresgrandes das ordens de grupo), estender a base de fatores, ouvoltar atras na cadeia de certificados.

IV. PARALELIZAC AO DO ECPP

Em teoria, o ECPP pode ser paralelizado sem esforco.Epossıvel distribuir os subconjuntos do item 2 do algoritmoentre diversos computadores e, a rigor, nao e necessarioesperar a confirmacao das condicoes do Teorema 3.1 para oprocedimento do algoritmo, uma vez que uma falha naquelepasso do algoritmoe rara e implicaria no termino da tentativade demonstracao do carater primo do numero em questao.

Porem, surgem certas dificuldades de ordem pratica parauma implementacao de larga escala com servidor central, emparticular a repeticao das precomputacoes do item 1 em cadacliente, e o desperdıcio de computacoes durante a transicao deum pseudoprimo para outro na cadeia deqi’s, uma vez quetodos os computadores da rede precisam ser avisados quandoda ocorrencia dessa transicao. Tambeme desejavel evitar umasobrecarga do servidor central para nao limitar a escalabilidadeda rede. Assim, propoe-se o uso de uma arquitetura de redede multiplos nıveis, com um servidor central no topo,proxiesnos nıveis do meio e os clientes em baixo. As vantagens saomultiplas:

1. o onus da transferencia de dadose reduzido nos nıveissuperiores deproxies, uma vez que os mesmos soprecisam se comunicar com outrosproxiese nao direta-mente com os clientes;

2. relacionado a isso, torna-se viavel propagar um aviso detransicao na cadeia de certificacao, ao inves de esperarnova comunicacao provinda dos clientes;

3. o servidor central so precisa ficar exposto ao primeironıvel de proxies da rede (supostamente instalacoesconfiaveis), aumentando a seguranca do sistema.

4. as precomputacoes do passo 1 podem ser efetuadas nosproxies e transmitidas para os clientes;

5. e viavel realizar verificacoes parciais dos resultadoscomputados pelos clientes, na busca de maquinas comdefeito ou tentativas de trapaca.

Ate onde os autores tem conhecimento, essa arquitetura derede nao foi proposta na literatura especializada uma vez quenao ha trabalhos estudando implementacoes de larga escalacomo essa.

V. I MPLEMENTACAO

O programa encontra-se em fase de implementacao. Umavez que o programa sera distribuıdo sob a licenca GNU GPL,e possıvel reutilizar codigo de outros projetos distribuıdos sobesta licenca. Istoe vantajoso, uma vez quee possıvel encontrarcodigo de altıssima qualidade, como por exemplo o programaGMP-ECM [2], do qual foi empregado o codigo de fatoracaode inteiros usando o algoritmop− 1, e a biblioteca TrolltechQt [10], empregada para desenvolvimento da interface deusuario do programa. Outros projetos de software livre usadosna implementacao do programa incluem a biblioteca GNUCommon C++ e o banco de dados PostgreSQL.

Expomos a seguir os algoritmos empregados na confeccaodo programa.

A. Fatorando a ordem de grupo

Para a tarefa de fatoracao das potenciais ordens de grupo,os principais algoritmos disponıveis sao trial division, Pollardrho [11], Pollard p-1 [12] e ECM [13]. A implementacao detrial division gera o produto de diversos primos pequenos ecalcula o MDC do inteiro sendo fatorado com este produto.A implementacao de Pollard rho utiliza a tecnica de buscade ciclos de Brent [14]. Como mencionado, foi empregada aimplementacao do programa GMP-ECM do algoritmo Pollardp-1. O algoritmo ECM, embora implementado no programaGMP-ECM, nao e utilizado ainda.

A selecao de parametros e a divisao de tempo entreesses algoritmose crucial para maximizar a eficiencia doprocedimento da fatoracao das ordens de grupo. Como aimplementacao ainda nao esta completa, nao foram realizadosexperimentos nesse sentido ainda.

B. Gerando curvas elıpticas com multiplicacao complexa

Para verificar as condicoes do teorema 3.1,e preciso con-struir uma curva elıptica sobreFqi

com a ordem de grupoindicada, empregando a teoria de multiplicacao complexa. Oprocedimentoe o seguinte:

• construir opolinomio de classe, um polinomio com co-eficientes inteiros cujas raızes geram o corpo quadraticoimaginario Q(

√−D);

• Reduzir os coeficientes do polinomio modulo qi;• Encontrar uma raiz desse polinomio emFqi

;• Calcular os coeficientes da curva a partir dessa raiz.

Para o passo 1, o procedimento tradicionale a construcaodo chamado polinomio de Hilbert. No entanto, os coefi-cientes deste polinomio tendem a ser muito grandes, exigindocomputacao em alta precisao, o que leva a um desperdıciode tempo e espaco (memoria). Na pratica sao empregados

XXI SIMPOSIO BRASILEIRO DE TELECOMUNICACOES-SBT2004, 06-09 DE SETEMBRO DE 2004, BELEM, PA

outros polinomios, como os polinomios de Weber e outros,baseados em diferentesinvariantes de classe. Nesse sentido,um conjunto de invariantes foi padronizado pelo IEEE nodocumento p1363, na qual baseamos nossa implementacao.

Resumidamente, o processo envolve a geracao das raızescomplexas do polinomio, a partir dos invariantes de classeaplicados a cada elemento do grupo de classe do discriminanteassociado, e a posterior reconstrucao desse polinomio a partirde suas raızes. Os calculos sao realizados em ponto flutuantede precisao multipla, levantando duas grandes questoes:

• qual e a precisao mınima requerida para o processo?• quais os melhores algoritmos nessa faixa de precisao?

Quantoa primeira questao, embora existam estimativas naliteratura, elas nao sao de valor pratico. A tecnica empregadaem nossa implementacao, que ate onde sabemose inedita,envolve o calculo do polinomio em baixa precisao, que podeser feito rapidamente, para obter uma estimativa da magnitudedos coeficientes do mesmo. Essa estimativa, somada a umamargem de seguranca (cujo valorotimo ainda esta sendoestudado, mas parece ser da ordem de

√h, o numero de classe

do discriminante em questao),e entao utilizada para o computofinal do polinomio.

A segunda questao e abordada a seguir.1) Aritmetica de polinomios com coeficientes complexos:A

aritmetica dos coeficientese realizada pela propria bibliotecaGMP, restando apenas a questao da aritmetica de polinomios.As unicas operacoes necessarias para a reconstrucao dopolinomio a partir de suas raızes sao a multiplicacao, somae subtracao (as duasultimas como rotinas auxiliares para arotina de multiplicacao). As algoritmos de soma e subtracaosao os algoritmos classicos, enquanto que para multiplicacao,sao empregados tres algortimos diferentes: classico, Karatsubae convolucoes por FFT.

O algoritmo classico multiplicaa(x) =∑m

i=0 aixi por

b(x) =∑n

j=0 bjxj , resultando num polinomio c(x) =

a(x)b(x)∑m+n

k=0 ckxk atraves da avaliacao da expressao

ck =k∑

i=0

aibk−i. (6)

No entanto, o tempo de execucao desse algoritmoe propor-cional amn, sendo deixado para tras pelo algoritmo de Karat-suba mesmo para pequenos valores dem e n. O algoritmo deKaratsubae baseado na observacao quee possıvel particionarum polinomio em duas partes, digamosaL(x) =

∑bm/2ci=0 aix

i

e aH(x) =∑dm/2e

j=0 aj+bm/2c+1xj , e de maneira semelhante

para bL(x) e bH(x). Seja n = bm/2c + 1. O polinomioresultantec(x) e calculado pela expressao

c = aHbHx2n + aLbL + (7)

+ ((aH + aL)(bH + bL)− aLbL − aHbH)xn.

Esta expressao envolve apenas tres multiplicacoes depolinomios, e nao as quatro esperadas, e pode ser aplicadarecursivamente. O tempo de execucao e entao da ordem demax(m,n)log2 3 ≈ max(m,n)1,58. Durante a implementacao,foi observado que o terceiro termo do lado direito da equacao7 gera o problema de cancelamento em ponto flutuante, o que

leva a perda de precisao. Assim, pode ser desejavel ajustar olimiar de transicao em favor do algoritmo classico (a despeitode seu tempo de execucao maior), para evitar esse problema.

Existe tambem um algoritmo com tempo de execucao pro-porcional amax(m,n) log max(m,n), baseado na observacaode que convolucoes no domınio da frequencia podem serefetudas de maneira bastante eficiente (multiplicacao ponto-a-ponto dos elementos dos vetores sendo convoluıdos), e que aconversao entre o domınio do tempo e o domınio da frequenciatambem pode ser efetuado de maneira eficiente atraves doalgoritmo FFT. Nossa implementacao utiliza um FFT split-radix, uma das variantes mais eficientes, com planos paraimplementacao de um FFT four-step no futuro, para permitirexecucao paralela em sistemas SMP.

Mencionamos de passagem que a literatura nao mencionanenhuma implementacao que utiliza FFTs para multiplicacaode polinomios, embora nossa implementacao tenha mostradoum ganho bastante significativo por conta disso. Naturalmente,os ganhos do FFT so vem a ser realizados para discriminantesmaiores, de modo que outros implementadores podem estarsatisfeitos com o desempenho do algoritmo de Karatsuba se afaixa de discriminantes for limitada.

2) Aritmetica de polinomios com coeficientes deFp: Opasso 3 do algoritmo de construcao de curvas acima exigea obtencao de uma raiz de um polinomio com coeficientesprovindos de um corpo finitoFp. O algoritmo empregadoeo de Cantor e Zassenhaus, que busca uma raiz de graud dopolinomio W (x) atraves do calculo de

mdc(W,T (pd−1)/2 − 1),

ondeT e um polinomio tomado aleatoriamente deFp[x],e a exponenciacao indicadae realizada modulo W . Assim,e necessario implementar rotinas de aritmetica de polinomiospara a aplicacao do algoritmo de Cantor e Zassenhaus, em par-ticular algoritmos de soma e subtracao, multiplicacao, reducaomodular e mdc. Destes, apenas a escolha dos algoritmos desoma e subtracao e trivial, uma vez que o desempenho dosalgoritmos classicose satisfatorio. A escolha do algoritmode mdc tambem e imediata, empregando-se o algoritmo deEuclides.

Para o algoritmo de multiplicacao, foi empregado ummetodo conhecido porsegmentacao binaria [6]. Neste metodo,sao construıdo inteiros a partir dos coeficientes dos polinomiosa serem multiplicados, e a multiplicacao dos doise feitausando uma rotina de multiplicacao de inteiros, reconstruindoo polinomio produto a partir do resultado desta operacao.A vantageme que e possıvel utilizar a mesma rotina paramultiplicacao de inteiros e multiplicacao de polinomios (nessecaso, a rotina do GMP), concentrando todos os esforcos deotimizacao nessa rotina.

Resta entao a rotina de exponenciacao, que emprega reducaomodular como subrotina. Inicialmente foi implementado umalgoritmo de exponenciacao esquerda-direita [6], [7], emboraum algoritmo mais eficiente deva ser implementado no futuro.Para reducao modular,e empregada uma tecnica remanescentedos metodos de Newton para divisao, descrita em [6, Alg.9.6.4].

XXI SIMPOSIO BRASILEIRO DE TELECOMUNICACOES-SBT2004, 06-09 DE SETEMBRO DE 2004, BELEM, PA

C. Projetos em andamento

Algumas melhoras cruciais para a eficiencia do programaestao em fase de planejamento ou implementacao. Sao elas:

• determinacao da precisao mınima necessaria para ocomputo dos polinomios de Weber;

• implementacao de invariantes de classe alternativos, paraobtencao de polinomios de menor grau;

• fatoracao sobre o corpo de genero, que reduz o grau dopolinomio de Weber gerado [9];

• multiplicacao mais eficiente de inteiros gigantescos ([15]relata uma melhora significativa pela substituicao da roti-nas de multiplicacao da biblioteca GMP por multiplicacaousando FFTs da biblioteca FFTW);

• ajustes nos parametros das rotinas de fatoracao de in-teiros.

VI. RESULTADOS PRELIMINARES

Ate este momento, os esforcos dispendidos naimplementacao foram concentrados na geracao dos polinomiosde classe, a mais custosa subrotina envolvida na verificacaodas condicoes do teorema 3.1. Para verificacao da correcaoda implementacao, foram geradas diversas curvas elıpticascom multiplicacao complexa, e foi verificado que suas ordensde grupo coincidissem com os valores esperados atravesdo sistema PARI/GP, que inclui facilidades para aritmeticaelıptica. Destes, o resultado mais interessante foi a geracaode uma curva elıptica com multiplicacao complexa por√−5000500423. Os autores tem conhecimento de apenas

um esforco semelhante [16], porem com discriminante maisbaixo (-1000004099). A caracterıstica do corpo basee801819385093403524905014779542892948310645897957,a ordem do grupoe 801819385093403524905014367592-618830819049962784 e a equacao da curvae y2 = x3 +711559983408124438501193588840331868725406278023x−638081151684080295558784651392045096297528964752.A computacao toda foi realizada em 27h25m em umcomputador Intel Pentium 4 2.6 GHz com 1 GB de memoria,rodando o sistema operacional Linux.

Alguns dados a respeito desta computacao: o numero declasse do discriminante em questao e 29098, o mesmo graudo polinomio obtido. Inicialmente o polinomio foi calculadocom precisao de 128 bits, levando menos de um minuto paratanto. Com base nesse calculo, a precisao estimada para acomputacao real foi 42208 bits. A obtencao das raızes dopolinomio nao foi cronometrada, mas levou em torno de 20horas. A construcao do polinomio a partir de suas raızes levou6h10m. O tempo de reducao modular dos coeficientes dopolinomio e insignificante, assim como o tempo de construcaoda curva dado uma raiz desse polinomio, sobrando um tempode aproximadamente 1 hora para a extracao dessa raiz peloalgoritmo de Cantor-Zassenhaus.

REFERENCIAS

[1] Alfred J. Menezes. Elliptic curve cryptosystems.ftp://ftp.rsa.com/pub/cryptobytes/crypto1n2.pdf , 1995.

[2] Paul Zimmermann. The ECMNET project.http://www.loria.fr/˜zimmerma/records/ecmnet.html .

[3] Stefania Cavallar, Bruce Dodson, Arjen K. Lenstra, Walter M. Lioen,Peter L. Montgomery, Brian A. Murphy, and Herman J. J. te Riele et al.Factorization of a 512-bit RSA modulus. Technical Report MAS-R0007,Centrum voor Wiskunde en Informatica, February 2000.

[4] Mike Oakes. ECPP proof of 7760-digit Euler-irregularprime. Comunicacao a lista de discussao NMBRTHRY,http://listserv.nodak.edu/scripts/wa.exe?A2=ind0407&L=nmbrthry&F=&S=&P=%2292 .

[5] Francois Morain. A new large primality proof usingfastECPP. Comunicacao a lista de discussao NMBRTHRY,http://listserv.nodak.edu/scripts/wa.exe?A2=ind0407&L=nmbrthry&F=&S=&P=%2165 .

[6] Richard Crandall and Carl Pomerance.Prime Numbers: A Computa-tional Perspective. Springer-Verlag, New York, 2000.

[7] Henri Cohen. A Course in Computational Algebraic Number Theory,volume 138 of Graduate Texts in Mathematics. Springer, Berlin,Heidelberg, New York, third edition, 1996.

[8] S. Goldwasser and J. Kilian. Almost all primes can be quickly certified.In Proceedings of the 18th Annual ACM Symposium on the Theory ofComputing, pages 316–329, 1986.

[9] A. O. L. Atkin and Francois Morain. Elliptic curves and primalityproving. Mathematics of Computation, 61(203):29–68, 1993.

[10] Trolltech. Qt application framework.http://www.trolltech.com.

[11] John M. Pollard. A Monte Carlo method for factorization.NordiskTidskr. Informationsbehandling (BIT), 15:331–334, 1975.

[12] John M. Pollard. Theorems on factorization and primality testing. InProceedings of the Cambridge Philosophical Society, volume 76, pages521–528, 1974.

[13] Hendrik W Lenstra Jr. Factoring integers with elliptic curves.Annalsof Mathematics, 2:649–673, 1987.

[14] Richard P. Brent. An improved Monte Carlo factorization algorithm.Nordisk Tidskr. Informationsbehandling (BIT), 20:176–184, 1980.

[15] Jens Franke, T. Kleinjung, Francois Morain, and T. Wirth.Proving the primality of very large numbers with fastECPP.ftp://lix.polytechnique.fr/pub/submissions/morain/Preprints/large.ps.gz% , 2004. Manuscript.

[16] Reynald Lercier. Elliptic curves with complex multiplication.Comunicacao a lista de discussao NMBRTHRY, http://listserv.nodak.edu/scripts/wa.exe?A2=ind0401&L=nmbrthry&F=&S=&P=%1098 .

90

Referencias

1 KNUTH, D. E. The Art of Computer Programming: Seminumerical Algorithms.Terceira edicao. [S.l.]: Addison-Wesley, 1997.

2 CRANDALL, R.; POMERANCE, C. Prime Numbers: A Computational Perspective.New York: Springer-Verlag, 2000.

3 JONES, G. A.; JONES, J. M. Elementary Number Theory. New York: Springer-Verlag,1998. (Springer Undergraduate Mathematics Series).

4 AGRAWAL, M.; KAYAL, N.; SAXENA, N. PRIMES is in P. 2002. http://www.cse.iitk.ac.in/news/primality_v3.pdf.

5 MENEZES, A. J.; OORSCHOT, P. C. van; VANSTONE, S. A. Handbook of AppliedCryptography. [S.l.]: CRC Press, 1997.

6 HENNESSY, J. L.; PATTERSON, D. A. Arquitetura de Computadores: umaAbordagem Quantitativa. Rio de Janeiro: Editora Campus, 2003.

7 PACHECO, P. S. Parallel Programming with MPI. San Francisco: Morgan Kaufmann,1997.

8 DISTRIBUTED.NET. http://www.distributed.net.

9 SETI@HOME. http://setiathome.ssl.berkeley.edu.

10 GREAT Internet Mersenne Prime Search. http://www.mersenne.org.

11 DUMMIT, D. S.; FOOTE, R. M. Abstract Algebra. Segunda edicao. New York: JohnWiley and Sons, 1999.

12 COHEN, H. A Course in Computational Algebraic Number Theory. Terceira edicao.Berlin, Heidelberg, New York: Springer, 1996. (Graduate Texts in Mathematics, v. 138).

13 GOLDWASSER, S.; KILIAN, J. Almost all primes can be quickly certified. In:Proceedings of the 18th Annual ACM Symposium on the Theory of Computing. [S.l.:s.n.], 1986. p. 316–329.

14 ATKIN, A. O. L.; MORAIN, F. Elliptic curves and primality proving. Mathematicsof Computation, v. 61, p. 29–68, 1993.

15 GRANTHAM, J. A probable prime test with high confidence. Journal of NumberTheory, v. 72, p. 32–47, 1998.

16 MORAIN, F. Implementing the asymptotically fast version ofthe elliptic curve primality proving algorithm. 2004. Disponıvel em:<http://www.lix.polytechnique.fr/Labo/Francois.Morain/Articles/fastecpp040825.pdf>.

91

17 FRANKE, J. et al. Proving the primality of very large numbers with fastECPP. In:Algorithmic Number Theory – Proceedings of ANTS 2004. [S.l.: s.n.], 2004. p. 194–207.

18 MORAIN, F. Distributed primality proving and the primality of (23539 + 1)/3. In:DAMGARD, I. (Ed.). Advances in Cryptology – Proceedings of EUROCRYPT ’90. NewYork: Springer-Verlag, 1991. (Lecture Notes in Computer Science, v. 473), p. 110–123.

19 SCHOOF, R. Elliptic curves over finite fields and the computation of square rootsmodulo p. Mathematics of Computation, v. 44, p. 483–494, 1985.

20 INSTITUTE OF ELECTRICAL AND ELECTRONICS ENGINEERS. StandardSpecifications for Public Key Cryptography. Rascunho versao 13. [S.l.], 1999.

21 MARTIN, M. Comunicacao privada. 2004.

22 DWORK, C.; NAOR, M. Pricing via processing or combatting junk mail. In:Advances in Cryptology – Proceedings of CRYPTO ’92. New York: Springer-Verlag,1993. (Lecture Notes in Computer Science, v. 740), p. 137–147.

23 WILLIAMS, H. C. A modification of the RSA public-key encryption procedure.IEEE Transactions on Information Theory, v. 26, p. 726–729, 1980.

24 BERNSTEIN, D. J. A secure public-key signature system with extremely fastverification. 1997. Disponıvel em: <http://cr.yp.to/papers/sigs.pdf>.

25 BERNSTEIN, D. J. Proving tight security for standard Rabin-Williams signatures.2003. Disponıvel em: <http://cr.yp.to/sigs/rwtight-20030926.pdf>.

26 STROUSTRUP, B. A Linguagem de Programacao C++. Terceira edicao. PortoAlegre: Bookman, 2000.

27 GNU Multiple Precision Arithmetic Library. http://www.swox.com/gmp.

28 VELDHUIZEN, T. Expression templates. C++ Report, v. 7, n. 5, p. 26–31, Junho1995.

29 MARTIN, M. PRIMO. http://www.ellipsa.net.

30 LOAN, C. V. Computational Frameworks for the Fast Fourier Transform. [S.l.]:SIAM, 1992. (Frontiers in Applied Mathematics).

31 ARNDT, J. The FXT library: Fast transforms and low level algorithms.http://www.jjj.de/fxt/fxtpage.html.

32 PRESS, W. et al. Numerical Recipes in C. [S.l.]: Cambridge University Press, 1996.

33 SHOUP, V. A new polynomial factorization algorithm and its implementation.Journal of Symbolic Computation, v. 20, p. 363–397, 1995.

34 MONTGOMERY, P. L. An FFT Extension of the Elliptic Curve Method ofFactorization. Tese (Doutorado) — University of California, Los Angeles, 1992.

35 BRENT, R. P. Fast multiple-precision evaluation of elementary functions. Journalof the ACM, v. 23, p. 242–251, 1976.

92

36 SALAMIN, E. Computation of π using arithmetic-geometric mean. Mathematics ofComputation, v. 30, p. 565–570, 1976.

37 GOURDON, X. Archimedes’ constant π. http://numbers.computation.free.fr/Constants/Pi/pi.html.

38 BRENT, R. P. The complexity of multiple-precision arithmetic. In: ANDERSSEN,R. S.; BRENT, R. P. (Ed.). The Complexity of Computational Problem Solving. Brisbane:University of Queensland Press, 1976. p. 126–165.

39 MORAIN, F. Comunicacao a lista de discussao NMBRTHRY. http://listserv.nodak.edu/scripts/wa.exe?A2=ind0407&L=nmbrthry&F=&S=&P=21%65.

40 MORAIN, F. Courbes elliptiques et tests de primalite. Tese (Doutorado) —Universite de Lyon I, 1990.

41 HANROT, G.; MORAIN, F. Solvability by radicals from an algorithmic point ofview. In: Proceedings of ISSAC 2001. [S.l.]: ACM, 2001. p. 175–182.

93

Indice Remissivo

(Z/nZ)∗

comutatividade, 20condicao para ser cıclico, 20definicao, 20ordem, 20

Qn

como subgrupo de (Z/nZ)∗, 21descricao quando (Z/nZ)∗ e cıclico,

21Z/nZ

definicao, 16π(x), 14

AKS, 47algoritmo de divisao, 11algoritmo de Euclides, 12APR-CL, 47aritmetica modular, 11

implementacao, 18

cadeia binaria de Lucas, 43certificados de carater primo, 46compostos, veja numeros compostoscongruencia

aritmeticadivisao, 17exponenciacao, veja exponenciacao

modularinversao, veja inversao modularusando o Teorema Chines do Resto,

18validade, 16

como relacao de equivalencia, 15definicao, 15

coprimos, 13corpo

caracterıstica, 10definicao, 9extensao de, 11finito

caracterıstica, 10definicao, 10grupo multiplicativo de, 10implementacao, 10isomorfismo, 10, 11

Crivo de Eratostenes, 1curva elıptica

aritmeticacontagem de operacoes, 33coordenadas afins, 32coordenadas projetivas, 33

definicao, 28determinacao de um ponto sobre, 31discriminante, 26forma afim, 27forma projetiva, 27

classe de equivalencia de solucoes,27

grupo de pontosdefinicao, 29estrutura algebrica, 30expressoes para operacao de grupo,

29limites para a ordem do grupo, 31

lei de grupo, 28parametrizacao de Weierstrass, 26ponto no infinito, 27relacao entre solucoes afins e projeti-

vas, 27sobre um anel, 48

divisao euclidiana, veja algoritmo de di-visao

divisibilidadedefinicao, 11propriedades, 12

divisor comum, 12

ECDH, 26ECDSA, 26

94

ECM, 26ECPP, 26endomorfismo, 52exponenciacao modular

algoritmo, 16definicao, 16

funcao φ de Eulerdefinicao, 19propriedades, 19valor quando o argumento e com-

posto, 19valor quando o argumento e potencia

de primo, 19

grupoabeliano, 5cıclico

definicao, 8isomorfismo a Z/nZ, 8propriedades, 8, 9

definicao, 5homomorfismo, 7isomorfismo, 7

criterio, 7lei de cancelamento, 6notacao, 5ordem

de um elemento, 6do grupo, 6

potencias de elementos, 6propriedades, 5

grupo de classe, 53

inversao modular, 17

Lei de Moore, 2lema de Euclides, 12

maximo divisor comum, 12matriz simetrica reduzida, 53multiplicacao complexa

discriminante fundamental, 52relacao entre discriminantes funda-

mentais e reduzidos, 52

numero de classe, 53numeros compostos

definicao, 1

maior fator primo de, 14numeros de Carmichael, 39numeros primos

definicao, 1distribuicao dos, 14infinitude dos, 14

nao-singularidade, 26

Pequeno Teorema de Fermat, 20polinomio

criterio de irredutibilidade, 11polinomio reduzido de classe, 54polinomios sobre Z/nZ

numero de raızes, 19primos, veja numeros primospseudoprimo

de Fermat, 39definicao, 37forte, 40forte de Frobenius, 44

raızes quadradas modularescalculo, 24modulo composto, 25numero de, 21

raiz primitiva(Z/nZ)∗, 20

numero de raızes primitivas em, 21teste para, 21

F∗pk , 10numero de raızes primitivas em, 10teste para, 10

reciprocidade quadratica, 23relativamente primos, 13resıduos quadraticos

definicao, 21o conjunto Qn de, veja Qn

sımbolo de Jacobicalculo, 23definicao, 22propriedades, 22

sımbolo de Legendrecalculo, 22definicao, 21propriedades, 22

sequencia de Fibonacci, 41sequencia de Lucas, 41

95

subgrupo, 7estrutura de subgrupos de um grupo

cıclico, 9

Teorema Chines do Resto, 18Teorema de Fermat-Euler, 20

versao sem restricoes sobre mdc(a, n),20

teorema de Goldwasser-Kilian, 48

teorema de Pocklington, 45Teorema dos Numeros Primos, 14Teorema Fundamental da Algebra, 19Teorema Fundamental da Aritmetica, 1teste de carater pseudoprimo, 37

de Fermat, 38de Frobenius, 41de Lucas, 41forte, 39