Criptografia, Números Primos e Algoritmos Publicações Matemáticas Criptografia, Números Primos e Algoritmos 4a edição Manoel Lemos Universidade Federal de Pernambuco impa Copyright  2010 by Manoel Lemos Impresso no Brasil / Printed in Brazil Capa: Noni Geiger / Sérgio R. Vaz Publicações Matemáticas • Introdução à Análise Funcional – César R. de Oliveira • Introdução à Topologia Diferencial – Elon Lages Lima • Criptografia, Números Primos e Algoritmos – Manoel Lemos • Introdução à Economia Dinâmica e Mercados Incompletos – Aloísio Araújo • Conjuntos de Cantor, Dinâmica e Aritmética – Carlos Gustavo Moreira • Geometria Hiperbólica – João Lucas Marques Barbosa • Introdução à Economia Matemática – Aloísio Araújo • Superfícies Mínimas – Manfredo Perdigão do Carmo • The Index Formula for Dirac Operators: an Introduction – Levi Lopes de Lima • Introduction to Symplectic and Hamiltonian Geometry – Ana Cannas da Silva • Primos de Mersenne (e outros primos muito grandes) – Carlos Gustavo T. A. Moreira e Nicolau Saldanha • The Contact Process on Graphs – Márcia Salzano • Canonical Metrics on Compact almost Complex Manifolds – Santiago R. Simanca • Introduction to Toric Varieties – Jean-Paul Brasselet • Birational Geometry of Foliations – Marco Brunella • Introdução à Teoria das Probabilidades – Pedro J. Fernandez • Teoria dos Corpos – Otto Endler • Introdução à Dinâmica de Aplicações do Tipo Twist – Clodoaldo G. Ragazzo, Mário J. Dias Carneiro e Salvador Addas Zanata • Elementos de Estatística Computacional usando Plataformas de Software Livre/Gratuito – Alejandro C. Frery e Francisco Cribari-Neto • Uma Introdução a Soluções de Viscosidade para Equações de Hamilton-Jacobi – Helena J. Nussenzveig Lopes, Milton C. Lopes Filho • Elements of Analytic Hypoellipticity – Nicholas Hanges • Métodos Clássicos em Teoria do Potencial – Augusto Ponce • Variedades Diferenciáveis – Elon Lages Lima • O Método do Referencial Móvel – Manfredo do Carmo • A Student's Guide to Symplectic Spaces, Grassmannians and Maslov Index – Paolo Piccione e Daniel Victor Tausk • Métodos Topológicos en el Análisis no Lineal – Pablo Amster • Tópicos em Combinatória Contemporânea – Carlos Gustavo Moreira e Yoshiharu Kohayakawa • Uma Iniciação aos Sistemas Dinâmicos Estocásticos – Paulo Ruffino • Compressive Sensing – Adriana Schulz, Eduardo A.B.. da Silva e Luiz Velho • O Teorema de Poncelet – Marcos Sebastiani • Cálculo Tensorial – Elon Lages Lima Distribuição: IMPA E-mail: [email protected] - http://www.impa.br ISBN: 978-85-244-0043-8 “criptografia” i i 2010/3/26 page iii i i a Adilson e Astr´ea i i i i “criptografia” i i 2010/3/26 page iv i i i i i i “criptografia” i i 2010/3/26 page v i i Pref´acio No ano de 1989, h´a precisamente duas d´ecadas, lecionei um curso no 17o Colo´quio Brasileiro de Matema´tica entitulado de Criptografia, nu´meros primos e algoritmos. As notas de aulas escritas para este curso esta˜o esgotadas. Diante da solicitac¸˜ao feita pelo IMPA para a sua reimpress˜ao, achei interessante as reescrever completa- mente. Quatro motivos principais me levaram a tormar esta decis˜ao: algunserrostipogr´aficospresentesnasnotasoriginais;osavanc¸osque ocorreram nestas duas u´ltimas d´ecadas em teoria dos nu´meros com- putacional; a abordagem realizada de forma sucinta na maioria dos to´picos; e a presenc¸a de poucos exerc´ıcios. Nos quatro primeiros meses de 1989, as notas de aulas para o cursoquelecioneinocolo´quioemjulhodomesmoanoforamescritas. Redigi estas notas em um caderno. Como, naquela ´epoca, n˜ao utili- zava o TEX, n˜ao digitei as notas. Quem o fez foi Oscar. Aos erros tipoga´ficos que cometi ao redigir, Oscar talvez tenha acrescentado mais alguns. Na revisa˜o, n˜ao fui capaz de encontrar todos. Para os mais jovens, pode parecer estranho n˜ao ter digitado em TEX. Mas a d´ecada de 80 foi de transic¸˜ao. Quando fazia o Ensino Fundamental fiz um curso de datilografia. Ganhei dos meus pais uma m´aquina de escreverOlivetti. Paraqueamargemesquerdafossealinhada, neces- sitava, ao chegar na u´ltima palavra, fazer a conta de quantas letras podiam ser digitadas antes do fim da linha para fazer o ajuste. Era um processo muito trabalhoso. A pior parte era jogar fora toda uma p´agina quando um erro era cometido. S´ımbolos matem´aticos nem pensar! S´o os dispon´ıveis no teclado. Esta m´aquina me acompanhou tamb´em no Ensino M´edio. v i i i i “criptografia” i i 2010/3/26 page vi i i vi Ao ingressar na universidade, n˜ao necessitava digitar textos, pois n˜ao´e comum que trabalhos sejam solicitados nas disciplinas de ciˆen- cias matem´aticas. Na˜o lembro de nenhum. Apenas no mestrado tive de escrever minha dissertac¸˜ao. Digitei a vers˜ao preliminar em uma m´aquinael´etrica quepodiacorrigiroserros. Quandonecess´ario, tive de deixar espac¸o para escrever `a m˜ao as letras gregas e os s´ımbolos matem´aticos. A vers˜ao final, digitada por Delsa ou Neide, n˜ao lem- bro bem, foi feita em m´aquina similar. Nestas m´aquinas, as letras vinham em relevo em uma esfera. Existiam esferas com s´ımbolos matem´aticos e letras gregas. Quando era necess´ario digitar um ca- racter deste tipo, bastava trocar a esfera. Era muito trabalhoso, mas era um enorme progresso. Na vers˜ao final de minha dissertac¸˜ao nada foi escrito a m˜ao. Fui para o doutorado. Ao chegar em Oxford deparei com m´aquinas de escrever, na sala de caf´e dos estudantes, que possu´ıam dois teclados: um normal e outro com letras gregas e s´ımbolos matem´aticos. Para mudar de teclado, bastava transferir o tambor. Achei que teria dificuldade em redigir meus resultados em uma m´aquina ta˜o estranha. Logo descobri que o Instituto de Matema´tica tinha disponibilizado 1 computador pessoal para todos osestudantes dep´os-graduac¸˜ao digitarem seusresultados equeestas m´aquinastinhamsidodescartadas. Est´avamosnofinalde1984. Des- taquei o nu´mero 1 porque computadores pessoais eram raros nesta ´epoca. Um novo mundo se abriu para mim. Descobri que podia digitar todos os s´ımbolos matem´aticos. Bastava escolher em algumas tabe- las. A margem esquerda era feita automaticamente. As f´ormulas podiam ser centralizadas sem dificuldade. Utilizava o processador de textos conhecido como T3. Ou era T3? Na˜o lembro bem. Ao chegar de volta no Brasil, passei a utilizar o CHIWRITE. Ambos, quando comparadoscomoTEX,sa˜obastanterudimentares. Em1989,ainda n˜aoutilizavaoTEX.Hojeutilizoumadesuasvariantesque´econhe- cida como LATEX. Estas notas foram digitadas por mim. Qualquer erro tipogr´afico ser´a de minha inteira responsabilidade. Na˜o terei como terceirizar parte deles. A maior parte destas notas foi redigida quando lecionava a disci- plina Criptografia e Algoritmos aqui na UFPE. Os textos utilizados parailustrarasaplicac¸˜oesdosdiversossistemasdecriptografiaabor- dadostratamdefutebol. Quandoescritos,oSantaCruzaindajogava i i i i “criptografia” i i 2010/3/26 page vii i i vii na segunda divis˜ao. Neste ano, terminou como lanterna de um dos grupos da quarta. Deixo, como exerc´ıcio para o leitor, adivinhar em que ano lecionei a disciplina. Nestas duas u´ltimas d´ecadas, a pesquisa nesta ´area foi intensa. Destaco dois grandes avanc¸os. O primeiro foi um algoritmo polino- mial para fatorar inteiros em um computador quˆantico. O segundo, adescobertadeumalgoritmopolinomialparadecidirquandoumin- teiro ´e primo. Este algoritmo ficou conhecido como AKS. Portanto, toda a discuss˜ao sobre o algoritmo de Lenstra, que foi escrita para o curso do Colo´quio, se tornou obsoleta. Abordamos os algoritmos para decidir primalidade no quarto cap´ıtulo destas notas. Continua- mos apresentando o algoritmo randomizado de Rabin que, apesar de termaisde30anos,ainda´eutilizadoparaencontrarnu´merosprimos grandes. DiscutimosoAKS,masdevidoaoesp´ıritodestasnotas,n˜ao odemonstramos. Noprimeiroenosegundocap´ıtulosabordamosres- pecitivamenteaspropriedadesdosinteirosecongruˆencias. Noquinto e u´ltimo cap´ıtulo fazemos uma pequena discuss˜ao sobre livros relaci- onados. Por fim fac¸o um pequeno comenta´rio sobre a u´ltima reforma em nossa ortografia. A desconsideramos completamente, j´a que a antiga ainda vale at´e 2011, isto ´e, bem depois da pr´oxima Copa. Portanto, palavrascomoconsequ¨entementeesequ¨ˆenciaaindatˆemotremanes- tas notas. Ficaria estranho adotar a nova ortografia sem o novo alfabeto ser utilizado para escrever mensagens. Todos os exemplos foram feitos em um alfabeto sem as letras K, Y e W. Gostaria de agradecer ao meu colega de departamento, Profes- sor Antonio Carlos Rodrigues Monteiro, por ter lido atentamente estas notas e feito inu´meras sugest˜oes. Por insitˆencia dele, o zero vi- rou um nu´mero natural. Na minha abordagem inicial tinha adotado uma possic¸˜aoamb´ıgua, o quepodeparecerestranho emmatem´atica. Como alguns autores consideram o zero como natural e outros n˜ao, tinha decidido considerar o zero como um natural dependendo da situac¸˜ao. O que, de fato, ´e estranho. Portanto, descartei esta abor- dagem informal para esta questa˜o. Gostaria de deixar claro que o Professor Antonio n˜ao tem nenhuma resposabilidade sobre qualquer erroqueporventuraexistanestasnotas. Todos,queimaginoformem o conjunto vazio, sa˜o de minha inteira responsabilidade. Sobre esta questa˜o, vale a pena aguardar o prefa´cio da terceira edic¸˜ao destas i i i i “criptografia” i i 2010/3/26 page viii i i viii notas, caso sejam escritas algum dia. Em1989,dediqueiasnotasdeaulasescritasespecialmenteparao Colo´quio ao Professor Adilson Gonc¸alves e `a Professora Astr´ea Bar- reto. Ambos foram meus professores na UFPE e, quando estava no doutorado, solicitaram transferˆencia para a UFRJ. A contribuic¸˜ao que deram para a consolidac¸˜ao da matem´atica brasileira, atrav´es de sua atuac¸˜ao profissional consistente ao longos das u´ltimas 4 d´ecadas, foi significativa. Passados 20 anos do Colo´quio, entendo que a dedi- cat´oria continua muito atual. E´ pena que n˜ao existam tantos profes- sores nas universidades brasileiras com uma atuac¸˜ao ta˜o destacada e positiva quanto a dos dois. Manoel Lemos Recife, 20 de setembro de 2009 i i i i