Η διείσδυση των υπολογιστών, τόσο στα σπίτια μας, όσο και κυρίως στις επιχειρήσεις, κατά τα τελευταία χρόνια, καθώς επίσης και ο συνεχώς αυξανόμενος ρυθμός χρήσης του διαδικτύου, έχουν καταστήσει την ανάγκη για ασφαλείς ηλεκτρονικές επικοινωνίες και συναλλαγές κάτι παραπάνω από επιτακτική. Ένα από τα κυρίαρχα, σήμερα, συστήματα ασφαλούς ανταλλαγής δεδομένων είναι ο αλγόριθμος RSA, η ασφάλεια του οποίου βασίζεται στο γεγονός ότι είναι πολύ δύσκολο να παραγοντοποιήσουμε έναν «μεγάλο» αριθμό στους πρώτους παράγοντές του. Ο RSA αλγόριθμος θεωρείται αρκετά ασφαλής, αν βέβαια χρησιμοποιούμε κατάλληλο, για τα σημερινά δεδομένα, μέγεθος κλειδιού. Παρόλα αυτά, σε περίπτωση που βρεθεί κάποιος αποδοτικός αλγόριθμος που να μπορεί σε «λογικό» χρόνο να παραγοντοποιήσει οποιονδήποτε μεγάλο ακέραιο, τότε αυτομάτως η ασφάλεια του αλγορίθμου αυτού έχει παραβιαστεί και θα πρέπει να στραφούμε σε εναλλακτικές μεθόδους προστασίας της πληροφορίας. Ο πιο αποδοτικός σήμερα αλγόριθμος παραγοντοποίησης μεγάλων ακεραίων είναι ο Number Field Sieve. Η έρευνα που έχει γίνει πάνω σε αυτόν τον αλγόριθμο, έχει οδηγήσει σε σημαντική πρόοδο και έχει καταστήσει, πλέον, εφικτή την παραγοντοποίηση ακεραίων που υπό άλλες προϋποθέσεις θα απαιτούσε χιλιάδες χρόνια από cpu time σε supercomputers. Αν και ακόμη και σήμερα υπάρχουν αρκετά σημεία που θα μπορούσαν να βελτιωθούν στον αλγόριθμο, κάνοντάς τον ακόμη πιο αποδοτικό, ωστόσο η πολυπλοκότητά του αποτρέπει αρκετούς να ασχοληθούν με την βελτίωσή του. Με την εργασία αυτή θα προσπαθήσουμε αρχικά να διασαφηνίσουμε όλες τις πληροφορίες που απαιτούνται για την σωστή κατανόηση της λειτουργίας του αλγορίθμου. Θα γίνει λεπτομερής περιγραφή των διαφόρων βημάτων του αλγορίθμου και θα δοθεί αναλυτικό παράδειγμα παραγοντοποίησης. Τέλος, θα παρουσιαστεί η παράλληλη υλοποίησή του αλγορίθμου, η οποία μπορεί να εκτελεστεί τόσο σε supercomputer, όσο και σε cluster υπολογιστών που επικοινωνούν μεταξύ τους με χρήση του MPI. / The recent advances in computer science, in combination with the proliferation of computers in home and businesses and the explosive growth rate of the internet transactions, have increased the needs for secure electronic communications. One of the dominant systems of secure data transactions is the RSA algorithm. RSA’ s security relies on the fact that it is computationally difficult to factor a “large” integer into its component prime integers. RSA is considered secure as long as we use proper key length. However, if an efficient algorithm is developed that can factor any arbitrarily large integer in a “reasonable” amount of time, then the whole security of the algorithm will be broken, and we will have to use alternative methods to secure our systems. Today, the fastest known method for factoring large integers is the General Number Field Sieve algorithm. Research and development of the algorithm has enabled the factorization of integers that were once thought to require thousands of years of CPU time to accomplish. While there are still many possible optimizations that could increase the algorithm’s efficiency, however the complexity of the algorithm prevents many researchers from attempting to improve it. In this master thesis we present the information needed to understand the principles upon which the algorithm is based. The discrete steps of the algorithm are described in full detail, as well as a detailed factorization example, in order to enlighten the way each step works. Finally a parallel implementation is presented, able to be executed on a supercomputer or a computer cluster, with the use of MPI.

Submitted by LEANDRO RODRIGUES DE CARVALHO null (leandrorodca@gmail.com) on 2016-05-20T19:48:46Z No. of bitstreams: 1 dissertacao-Leandro-profmat-2016.pdf: 1207301 bytes, checksum: 3605d67341c1a33446dc9c537f6b735e (MD5) / Rejected by Juliano Benedito Ferreira (julianoferreira@reitoria.unesp.br), reason: Foram realizadas suas submissões. Favor submeter novamente apenas uma vez com o arquivo correto. on 2016-05-24T14:34:08Z (GMT) / Submitted by LEANDRO RODRIGUES DE CARVALHO null (leandrorodca@gmail.com) on 2016-05-25T10:37:49Z No. of bitstreams: 1 dissertacao-Leandro-profmat-2016.pdf: 1207301 bytes, checksum: 3605d67341c1a33446dc9c537f6b735e (MD5) / Approved for entry into archive by Juliano Benedito Ferreira (julianoferreira@reitoria.unesp.br) on 2016-05-25T19:03:01Z (GMT) No. of bitstreams: 1 carvalho_lr_me_rcla.pdf: 1207301 bytes, checksum: 3605d67341c1a33446dc9c537f6b735e (MD5) / Made available in DSpace on 2016-05-25T19:03:01Z (GMT). No. of bitstreams: 1 carvalho_lr_me_rcla.pdf: 1207301 bytes, checksum: 3605d67341c1a33446dc9c537f6b735e (MD5) Previous issue date: 2016-04-28 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / O grande desafio no ensino da matemática, pelo menos no meu ponto de vista como professor nos últimos dez anos, é fazer com que os alunos percebam a importância e a praticidade da matemática em suas vidas. Isso vai além das teorias da Aritmética, Álgebra ou Geometria ensinadas na educação básica. Os alunos precisam perceber que os conceitos matemáticos são ferramentas que os ajudam a compreender o mundo a sua volta. Diante disto, esta dissertação busca apresentar conceitos matemáticos que levam à compreensão da Criptografia: conceitos da Teoria dos Números e da Álgebra. Fazemos ainda, um breve histórico sobre a Criptografia descrevendo a cifra de César e as cifras afins, o Sistema RSA e alguns métodos de troca de chaves. Relatamos alguns trabalhos desenvolvidos pelos estudantes do PROFMAT neste tema e apresentamos uma proposta de atividade para os estudantes do ensino básico. Esta atividade consiste na construção de um kit de encriptação e decriptação utilizando copos descartáveis. Com dinâmicas unindo elementos da Criptografia e o aplicativo Whatsapp, como meio de troca das mensagens criptografadas, motivamos a sala de aula para o aprendizado da Divisão Euclidiana e da Permutação. Além disso, pretendemos despertar nos alunos o interesse em aprofundar-se nos estudos da Matemática, principalmente na Teoria dos Números, já que esta é uma das ferramentas fundamentais no contexto da Criptografia, uma ciência com grande aplicabilidade na atualidade. / The great challenge in teaching mathematics, at least in my point of view as a teacher in the past ten years is to make students understand the importance and practicality of mathematics in their lives. This goes beyond the theories of arithmetic, algebra or geometry taught in basic education. Students need to realize that mathematical concepts are tools that help them understand the world around them. In view of this, this dissertation aims to present mathematical concepts that lead to understanding of cryptography: concepts of number theory and algebra. We also a brief history on the Encryption describing the Caesar cipher and related figures, the RSA system and some methods of key exchange. We report some work done by students PROFMAT this theme and present a proposal activity for students of basic education. This activity consists in building a kit of encryption and decryption using disposable cups. With dynamic linking elements Encryption and Whatsapp application as a means of exchange of encrypted messages, we motivate the classroom for learning Euclidean division and permutation. In addition, we intend to arouse students' interest in deepening the study of mathematics, especially in Number Theory, as this is one of the fundamental tools in the context of cryptography, a science with great applicability today.

The goal of this thesis is to present the pretentious approach to analytic number theory recently developed by Granville, Soundararajan, and others. In the first four chapters, we show the classical proof of the prime number theo- rem. We then develop the pretentious approach, explain its differences, advan- tages, and disadvantages and present another proof of the prime number theorem based on Hal'asz's theorem. This theorem is then proven using new techniques of Granville, Harper, and Soundararajan, which are substantially easier than the previous proofs. In the last chapter, we show how pretentious techniques can be used to obtain more intuitive proofs of other classical theorems or obtain new results. 1

Orientador: Flávia Souza Machado da Silva / Banca: Michelle Ferreira Zanchetta Morgado / Banca: Ana Paula Tremura Galves / Resumo: Este trabalho apresenta a construção formal do conjunto dos números racionais, a partir do conjunto dos números inteiros; desse modo, explicando o porquê de certos procedimentos e algoritmos usados no aprendizado dos números racionais. Apresenta também, alguns jogos que podem ser utilizados para abordar frações no que diz respeito a formas de representação, equivalência, operações (adição, subtração, multiplicação, divisão) e comparação. Sendo assim, busca-se apresentar uma proposta de ensino das frações com o objetivo de fazer com que os alunos possam se engajar no aprendizado desse tópico / Abstract: This work presents the formal construction of the rational numbers obtained from the set of the integers numbers, thus explaining why some procedures and algorithms are used in the learning of rational numbers. Also, some games that can be used in the classroom to teach representation forms, equivalence, operations (addition, subtraction, multiplication, division) and comparison of fractions. Thus, seeks to present a teaching proposal of the fractions in order to make with the students to can engage in learning this topic / Mestre

Made available in DSpace on 2016-04-01T17:54:40Z (GMT). No. of bitstreams: 0 Previous issue date: 2015-08-28. Added 1 bitstream(s) on 2016-04-01T18:00:20Z : No. of bitstreams: 1 000860277.pdf: 1012693 bytes, checksum: a64995a4e274cfc4d8fe4457bd66529b (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Este trabalho apresenta a construção formal do conjunto dos números racionais, a partir do conjunto dos números inteiros; desse modo, explicando o porquê de certos procedimentos e algoritmos usados no aprendizado dos números racionais. Apresenta também, alguns jogos que podem ser utilizados para abordar frações no que diz respeito a formas de representação, equivalência, operações (adição, subtração, multiplicação, divisão) e comparação. Sendo assim, busca-se apresentar uma proposta de ensino das frações com o objetivo de fazer com que os alunos possam se engajar no aprendizado desse tópico / This work presents the formal construction of the rational numbers obtained from the set of the integers numbers, thus explaining why some procedures and algorithms are used in the learning of rational numbers. Also, some games that can be used in the classroom to teach representation forms, equivalence, operations (addition, subtraction, multiplication, division) and comparison of fractions. Thus, seeks to present a teaching proposal of the fractions in order to make with the students to can engage in learning this topic

Submitted by Viviane Lima da Cunha (viviane@biblioteca.ufpb.br) on 2015-05-27T15:49:59Z No. of bitstreams: 1 arquivototal.pdf: 791381 bytes, checksum: 38dd57e91539c2f7bfdaf6d1092eff37 (MD5) / Approved for entry into archive by Leonardo Americo (leonardo@sti.ufpb.br) on 2015-05-27T17:33:15Z (GMT) No. of bitstreams: 1 arquivototal.pdf: 791381 bytes, checksum: 38dd57e91539c2f7bfdaf6d1092eff37 (MD5) / Made available in DSpace on 2015-05-27T17:33:15Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 791381 bytes, checksum: 38dd57e91539c2f7bfdaf6d1092eff37 (MD5) Previous issue date: 2013-08-13 / In this work we present the concept of cryptography, highlighting the differences between symmetric encryption and asymmetric encryption. We also show how RSA encryption works. Moreover, we study the main mathematical results that justify the operation of this cryptosystem and its security, such as: congruences, Euler's theorem, Fermat's Little Theorem, Wilson's Theorem, Euler's criterion for quadratic residues, Law of Quadratic Reciprocity and primality tests. / Neste trabalho apresentamos o conceito de criptografia, diferenciamos a criptogra fia simétrica da criptografia assimétrica e mostramos como funciona a criptografia RSA. Além disso, destacamos os principais resultados matemáticos que justificam o funcionamento desse criptossistema e sua segurança, tais como: congruências, Teorema de Euler, Pequeno Teorema de Fermat, Teorema de Wilson, Critério de Euler para resíduos quadráticos, Lei de Reciprocidade Quadrática e testes de primalidade.

Orientador: Erika Capelato / Banca: Renata Zotin Gomes de Oliveira / Banca: Camila Fernanda Bassetto / Resumo: O grande desafio no ensino da matemática, pelo menos no meu ponto de vista como professor nos últimos dez anos, é fazer com que os alunos percebam a importância e a praticidade da matemática em suas vidas. Isso vai além das teorias da Aritmética, Álgebra ou Geometria ensinadas na educação básica. Os alunos precisam perceber que os conceitos matemáticos são ferramentas que os ajudam a compreender o mundo a sua volta. Diante disto, esta dissertação busca apresentar conceitos matemáticos que levam à compreensão da Criptografia: conceitos da Teoria dos Números e da Álgebra. Fazemos ainda, um breve histórico sobre a Criptografia descrevendo a cifra de César e as cifras afins, o Sistema RSA e alguns métodos de troca de chaves. Relatamos alguns trabalhos desenvolvidos pelos estudantes do PROFMAT neste tema e apresentamos uma proposta de atividade para os estudantes do ensino básico. Esta atividade consiste na construção de um kit de encriptação e decriptação utilizando copos descartáveis. Com dinâmicas unindo elementos da Criptografia e o aplicativo Whatsapp, como meio de troca das mensagens criptografadas, motivamos a sala de aula para o aprendizado da Divisão Euclidiana e da Permutação. Além disso, pretendemos despertar nos alunos o interesse em aprofundar-se nos estudos da Matemática, principalmente na Teoria dos Números, já que esta é uma das ferramentas fundamentais no contexto da Criptografia, uma ciência com grande aplicabilidade na atualidade / Abstract: The great challenge in teaching mathematics, at least in my point of view as a teacher in the past ten years is to make students understand the importance and practicality of mathematics in their lives. This goes beyond the theories of arithmetic, algebra or geometry taught in basic education. Students need to realize that mathematical concepts are tools that help them understand the world around them. In view of this, this dissertation aims to present mathematical concepts that lead to understanding of cryptography: concepts of number theory and algebra. We also a brief history on the Encryption describing the Caesar cipher and related figures, the RSA system and some methods of key exchange. We report some work done by students PROFMAT this theme and present a proposal activity for students of basic education. This activity consists in building a kit of encryption and decryption using disposable cups. With dynamic linking elements Encryption and Whatsapp application as a means of exchange of encrypted messages, we motivate the classroom for learning Euclidean division and permutation. In addition, we intend to arouse students' interest in deepening the study of mathematics, especially in Number Theory, as this is one of the fundamental tools in the context of cryptography, a science with great applicability today / Mestre

Orientador: José Carlos Rodrigues / Coorientador: Marco Antônio Piteri / Banca: Aylton Pagamisse / Banca: Vera Lúcia Carbone / Resumo: Os tradicionais jogos de baralho são excelentes para se aplicar diversos conceitos matemáticos. A lógica matemática, a análise combinatória e a probabilidade são a base das regras que geram a competitividade desses jogos. Além disso, diversos jogos baseiam-se em cálculos, como é o caso da Escopa e do Black Jack, este último já muito estudado por se tratar de um jogo amplamente usado em casas de apostas. Pelo fato de estar muito associado a vícios e até à contravenção, o baralho não vem sendo usado como ferramenta no ensino de matemática. O objetivo desse trabalho é adaptar o jogo de escopa para uso didático, colaborando com o cálculo mental da soma de números inteiros, suas propriedades operatórias, o conceito do elemento neutro e de números opostos / Abstract: The traditional card games are excellent when applying several mathematical concepts. Mathematical logic, combinatorial analysis and probability are the foundations of the rules that create the competitiveness in those games. Furthermore, many games such as Scopa and Black Jack rely on calculations, but the latter has already been widely studied because it is a distinguishing game in gambling houses. However, since those games are related to compulsiveness and even to legal offenses, the card deck has not been used as a tool in the teaching of Mathematics. Thus, this paper is aimed to adapt Scopa to didactic use, fostering mental calculation of the sum of integers, and the teaching of the properties of the operations, and the concept of identity element and additive inverse / Mestre

Made available in DSpace on 2014-06-11T19:30:22Z (GMT). No. of bitstreams: 0 Previous issue date: 2013-01-28Bitstream added on 2014-06-13T19:25:46Z : No. of bitstreams: 1 marchiori_rm_me_rcla.pdf: 441197 bytes, checksum: dfc9ce6e00b97ad657ecd6859c6787a4 (MD5) / Tudo é número, diria o famoso matemático grego Pitágoras. Os números estão a nossa volta, como o oxigênio que respiramos. Primeiro vieram os naturais, depois os inteiros, os racionais e os incríveis irracionais, que deixaram os pitagóricos tão perplexos a ponto de escondê-los. Números primos, perfeitos e outros vieram. E quando tudo parecia ser real apareceram os imaginários. Que imaginação tem esses matemáticos! Vamos nos aprofundar em um grupo intrigante de números chamados transcendentes e aos números estudados por um matemático francês chamado Liouville / All is number, say the famous Greek mathematician Pythagoras. The numbers are all around us, like the oxygen we breathe. First came the natural, then the integers, the rational and the irrational incredible that left perplexed the Pythagoreans so as to hide them. Prime numbers, perfect and others came. And when everything seemed to be real the imaginary appeared. What have these mathematical imagination! Let's delve in a group of intriguing numbers called transcendental numbers and studied by a French mathematician named Liouville

Orientador: Sueli Irene Rodrigues Costa / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-10T04:41:55Z (GMT). No. of bitstreams: 1 Carlos_TatianaBertoldi_D.pdf: 779190 bytes, checksum: d0ff8f53ff44a5f19c7edb1427cd1a82 (MD5) Previous issue date: 2007 / Resumo: Neste trabalho abordamos a construção de reticulados usando propriedades da teoria dos números algébricos. Enfocamos particularmente a construção, como reticulado ideal, de rotações do reticulado n-dimensional dos inteiros, usando corpos ciclotômicos. Reticulados desta forma tem se mostrado uma eficiente ferramenta para obtenção de bons esquemas de codificação para canais com desvanecimento, pois permitem estimativas da distância produto e diversidade, parâmetros que controlam a probabilidade de erro no envio de informações por estes canais. Apresentamos uma nova construção de tais reticulados no caso em que n é uma potência de 2, através do subcorpo maximal real do n-ésimo corpo ciclotômico. Estabelecemos também condições para que um reticulado ideal seja rotação do reticulado n-dimensional dos inteiros, usando algoritmos de redução de base, LLL (Lenstra-Lenstra- Lovász) e Minkowski. Outros resultados incluem caracterizações geométricas de grafos circulantes e de alguns reticulados construídos algebricamente. / Abstract: In this work we approach lattice constructions using properties of algebraic number theory. One focus is on the construction of ideal lattices via cyclotomic fields. Those lattices have been used as an efficient tool for designing coding strategies for the Rayleigh fading channels since it is possible to estimate the product distance and the diversity, parameters which control the error probability transmission for those channels. A special case, due to "shaping gain", is when those lattices are rotations of the n-dimensional integer lattice. We present a new construction of such lattices when n is a power of 2, via the maximal sub-field of the n-cyclotomic field. We also establish conditions for an ideal lattice to be a Zn-lattice using the Minkowski and the LLL (Lenstra-Lenstra-Lovasz) reductions. Other results include geometric characterizations of circulant graphs and of some algebraic lattices. / Doutorado / Doutor em Matemática