Systolic architectures are capable of achieving high throughput by maximizing pipelining and by eliminating global data interconnects. Recursive algorithms with regular data flows are suitable for systolization. The computation of multiplicative inversion using algorithms based on EEA (Extended Euclidean Algorithm) are particularly suitable for systolization. Implementations based on EEA present a high degree of parallelism and pipelinability at bit level which can be easily optimized to achieve local data flow and to eliminate the global interconnects which represent most important bottleneck in todays sub-micron design process. The net result is to have high clock rate and performance based on efficient systolic architectures. This thesis examines high performance but also scalable implementations of multiplicative inversion or field division over Galois fields <i>GF</i>(2<i>^m</i>) in the specific case of cryptographic applications where field dimension <i>m</i> may be very large (greater than 400) and either <i>m</i> or defining irreducible polynomial may vary. For this purpose, many inversion schemes with different basis representation are studied and most importantly variants of EEA and binary (Stein's) GCD computation implementations are reviewed. A set of common as well as contrasting characteristics of these variants are discussed. As a result a generalized and optimized variant of EEA is proposed which can compute division, and multiplicative inversion as its subset, with divisor in either <i>polynomial</i> or <i>triangular</i> basis representation. Further results regarding Hankel matrix formation for double-basis inversion is provided. The validity of using the same architecture to compute field division with polynomial or triangular basis representation is proved. Next, a scalable unidirectional bit serial systolic array implementation of this proposed variant of EEA is implemented. Its complexity measures are defined and these are compared against the best known architectures. It is shown that assuming the requirements specified above, this proposed architecture may achieve a higher clock rate performance w. r. t. other designs while being more flexible, reliable and with minimum number of inter-cell interconnects. The main contribution at system level architecture is the substitution of all counter or adder/subtractor elements with a simpler distributed and free of carry propagation delays structure. Further a novel restoring mechanism for result sequences of EEA is proposed using a double delay element implementation. Finally, using this systolic architecture a CMD (Combined Multiplier Divider) datapath is designed which is used as the core of a novel systolic elliptic curve processor. This EC processor uses affine coordinates to compute scalar point multiplication which results in having a very small control unit and negligible with respect to the datapath for all practical values of <i>m</i>. The throughput of this EC based on this bit serial systolic architecture is comparable with designs many times larger than itself reported previously.

Systolic architectures are capable of achieving high throughput by maximizing pipelining and by eliminating global data interconnects. Recursive algorithms with regular data flows are suitable for systolization. The computation of multiplicative inversion using algorithms based on EEA (Extended Euclidean Algorithm) are particularly suitable for systolization. Implementations based on EEA present a high degree of parallelism and pipelinability at bit level which can be easily optimized to achieve local data flow and to eliminate the global interconnects which represent most important bottleneck in todays sub-micron design process. The net result is to have high clock rate and performance based on efficient systolic architectures. This thesis examines high performance but also scalable implementations of multiplicative inversion or field division over Galois fields <i>GF</i>(2<i>^m</i>) in the specific case of cryptographic applications where field dimension <i>m</i> may be very large (greater than 400) and either <i>m</i> or defining irreducible polynomial may vary. For this purpose, many inversion schemes with different basis representation are studied and most importantly variants of EEA and binary (Stein's) GCD computation implementations are reviewed. A set of common as well as contrasting characteristics of these variants are discussed. As a result a generalized and optimized variant of EEA is proposed which can compute division, and multiplicative inversion as its subset, with divisor in either <i>polynomial</i> or <i>triangular</i> basis representation. Further results regarding Hankel matrix formation for double-basis inversion is provided. The validity of using the same architecture to compute field division with polynomial or triangular basis representation is proved. Next, a scalable unidirectional bit serial systolic array implementation of this proposed variant of EEA is implemented. Its complexity measures are defined and these are compared against the best known architectures. It is shown that assuming the requirements specified above, this proposed architecture may achieve a higher clock rate performance w. r. t. other designs while being more flexible, reliable and with minimum number of inter-cell interconnects. The main contribution at system level architecture is the substitution of all counter or adder/subtractor elements with a simpler distributed and free of carry propagation delays structure. Further a novel restoring mechanism for result sequences of EEA is proposed using a double delay element implementation. Finally, using this systolic architecture a CMD (Combined Multiplier Divider) datapath is designed which is used as the core of a novel systolic elliptic curve processor. This EC processor uses affine coordinates to compute scalar point multiplication which results in having a very small control unit and negligible with respect to the datapath for all practical values of <i>m</i>. The throughput of this EC based on this bit serial systolic architecture is comparable with designs many times larger than itself reported previously.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2018-06-29T10:56:16Z No. of bitstreams: 2 Dissertação - Felipe Barbosa Franco - 2018.pdf: 2597060 bytes, checksum: b4c3ff56766b29c5a01cd7de1c3ba60a (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2018-06-29T11:55:57Z (GMT) No. of bitstreams: 2 Dissertação - Felipe Barbosa Franco - 2018.pdf: 2597060 bytes, checksum: b4c3ff56766b29c5a01cd7de1c3ba60a (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-06-29T11:55:57Z (GMT). No. of bitstreams: 2 Dissertação - Felipe Barbosa Franco - 2018.pdf: 2597060 bytes, checksum: b4c3ff56766b29c5a01cd7de1c3ba60a (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2018-04-03 / This work is theoretical, and its methodology was initially based on the research and bibliographic review of the Euclidean Algorithm, as well as the use of games in Mathematics education. A proposal was elaborated for the 7th year of Middle School, based on the Algebraic Dominoes of Freitas-Teodoro [8]. This proposal follows the methodology of Souza [22], which has lesson plans defined in four different moments. An analysis was made to justify the efficiency and importance of the Adapted Algebraic Domino restricted to the Use of Games in education based on the work of authors Regina Grando [10], Kishimoto [13], [14], [15], [16], [17] and Cristiano Muniz [18]. In addition, some simulations of plays related to the Algebraic Domino were made, for better understanding of the proposed subject. / Este trabalho é de cunho teórico, cuja metodologia baseou-se inicialmente na elaboração de pesquisas e revisões bibliográficas sobre o Algoritmo de Euclides, bem como sobre do Uso de Jogos no ensino de Matemática. Foi elaborada uma proposta inédita para o Sétimo Ano do Ensino Fundamental com base no Dominó Algébrico de Freitas-Teodoro [8]. Essa proposta segue a metodologia de Souza [22], que tem planos de aula definidos em quatro Momentos. Foi realizada uma análise para justificar a eficiência e importância da proposta do Dominó Algébrico Adaptado restritas ao Uso de Jogos no ensino com base em obras dos autores Regina Grando [10], Tizuko Kishimoto [13], [14], [15], [16], [17] e Cristiano Muniz [18]. Ademais, foram realizadas algumas simulações de jogadas relativas ao jogo Dominó Algébrico para melhor elucidação do tema proposto.

Egyptian fractions are what we know as unit fractions that are of the form 1/n - with the exception, by the Egyptians, of 2/3. Egyptian fractions have actually played an important part in mathematics history with its primary roots in number theory. This paper will trace the history of Egyptian fractions by starting at the time of the Egyptians, working our way to Fibonacci, a geologist named Farey, continued fractions, Diophantine equations, and unsolved problems in number theory.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This work presents an educational experiment carried out in a 9th grade class of elementary school, in order to assess the didactic and pedagogical possibilities involving the Linear Diophantine Equations theme, with the contextual support of Problem Solving. This application intends to expand the students' conceptions in arithmetic and algebra courses, also providing a concrete possibility of applicability of the greatest common divisor of two integers, a very neglected theme throughout the elementary school. In a level of elementary school, one of the main vehicles that allows you to work the initiative, creativity and exploring spirit is through Problem Solving. A Mathematics Teacher has a great opportunity to challenge the curiosity of the students by presenting them problems that are compatible with their knowledge and guiding them through incentive questions and this teacher can also try to input on them a taste for discovery and independent thinking. Thus, a very reasonable way is to prepare the student to deal with new situations, whatever they may be. The paper is organized in three chapters. In the first chapter entitled "Problem Solving in mathematics teaching" a theoretical foundation on the Teaching of Problem Solving is searched based on the Hungarian-American author George Polya and Luiz Roberto Dante and, it also presents some aspects from the learning theory proposed by Vygotsky. In the second chapter entitled "arithmetic concepts" the themes treated are: Greatest Common Divisor (gcd), Euclidean algorithm, Bèzout theorem and Linear Diophantine Equations. In the third and final chapter entitled "pedagogical experimentation" as mentioned above, the experimentation in a class of ninth grade of an elementary school. This experiment is based on the Didactic Engineering methodology, comprising the following stages: theme and scope of action; previous analyzes associated with the dimensions: epistemological, didactic and cognitive; prior analysis; experimentation; aftermost analysis and validation of Didactic Engineering. / Este trabalho apresenta uma experimentação pedagógica realizada numa turma de 9ºano do Ensino Fundamental com o objetivo de aferir as possibilidades didático-pedagógicas envolvendo a temática Equações Diofantinas Lineares, tendo como suporte contextual a Resolução de Problemas. Tal aplicação tem o intento de ampliar as concepções dos alunos nos campos da aritmética e da álgebra, dando também uma possibilidade concreta de aplicabilidade do máximo divisor comum de dois números inteiros, tema tão negligenciado ao longo do Ensino Fundamental. Em um nível de Ensino Fundamental, um dos principais veículos que permite trabalhar a iniciativa, a criatividade e o espírito explorador é a Resolução de Problemas. O professor de Matemática tem, dessa forma, uma grande oportunidade de desafiar a curiosidade de seus alunos, apresentando-lhes problemas compatíveis com os conhecimentos destes e orientando-os através de indagações incentivadoras, podendo incutir-lhes o gosto pela descoberta e pelo raciocínio independente. Assim, um caminho bastante razoável é preparar o aluno para lidar com situações novas, quaisquer que sejam elas. O trabalho está organizado em três capítulos. No primeiro capítulo intitulado A Resolução de Problemas no ensino da Matemática busca-se uma fundamentação teórica sobre a Didática da Resolução de Problemas no autor húngaro-americano George Polya e Luiz Roberto Dante e, também, são apresentados alguns aspectos da teoria da aprendizagem proposta por Vygotsky. No segundo capítulo intitulado conceitos de aritmética são tratados os temas: Máximo Divisor Comum (mdc), Algoritmo de Euclides, Teorema de Bèzout e Equações Diofantinas Lineares. No terceiro e último capítulo intitulado experimentação pedagógica é apresentada a experimentação supracitada numa turma de nono ano do Ensino Fundamental. Tal experimentação é baseada na metodologia Engenharia Didática, compreendendo os seguintes momentos: tema e campo de ação; análises prévias associadas às dimensões: epistemológica, didática e cognitiva; análise a priori; experimentação; análise a posteriori e validação da Engenharia Didática.

This thesis introduces a new mathematical object: collection of arithmetic progressions with elements satisfying the inverse property, \j-th terms of i-th and (i+1)-th progressions are multiplicative inverses of each other modulo (j+1)-th term of i-th progression". Such a collection is uniquely de ned for any pair (a; d) of co-prime integers. The progressions of the collection are ordered. Thus we call it a sequence rather than a collection. The results of the thesis are on the following number theoretic, computational and cryptographic aspects of the defined sequence and its generalizations. The sequence is closely connected to the classical Euclidean algorithm. Precisely, certain consecutive progressions of the sequence form \groupings". The difference between the common differences of any two consecutive progressions of a grouping is same. The number of progressions in a grouping is connected to the quotient sequence of the Euclidean algorithm on co-prime input pairs. The research community has studied extensively the behavior of the Euclidean algorithm. For the rst time in the literature, the connection (proven in the thesis) shows what the quotients of the algorithm signify. Further, the leading terms of progressions within groupings satisfy a mirror image symmetry property, called \symmetricity". The property is subject to the quotient sequence of the Euclidean algorithm and divisors of integers of the form x2 y2 falling in specific intervals. The integers a, d are the primary quantities of the defined sequence in a computational sense. Given the two, leading term and common difference of any progression of the sequence can be computed in time quadratic in the binary length of d. On the other hand, the inverse computational question of finding (a; d), given information on some terms of the sequence, is interesting. This problem turns out to be hard as it requires finding solutions to an nearly-determined system of multivariate polynomial equations. Two sub-problems arising in this context are shown to be equivalent to the problem of factoring integers. The reduction to the factoring problem, in both cases, is probabilistic. Utilizing the computational difficulty of solving the inverse problem, and the sub-problems (mentioned above), we propose a symmetric-key cryptographic scheme (SKCS), and a public key cryptographic scheme (PKCS). The PKCS is also based on the hardness of the problem of finding square-roots modulo composite integers. Our proposal uses the same algorithmic and computational primitives for effecting both the PKCS and SKCS. In addition, we use the notion of the sequence of arithmetic progressions to design an entity authentication scheme. The proof of equivalence between one of the inverse computational problems (mentioned above) and integer factoring led us to formulate and investigate an independent problem concerning the largest divisor of integer N bounded by the square-root of N. We present some algorithmic and combinatorial results. In the course of the above investigations, we are led to certain open questions of number theoretic, combinatorial and algorithmic nature. These pertain to the quotient sequence of the Euclidean algorithm, divisors of integers of the form x2 y2 p in specific intervals, and the largest divisor of integer N bounded by N.

Cryptographic protocols are implemented in hardware to ensure low-area, high speed and reduced power consumption especially for mobile devices. Elliptic Curve Cryptography (ECC) is the most commonly used public-key cryptosystem and its performance depends heavily on efficient finite field arithmetic hardware. Finding the multiplicative inverse (inversion) is the most expensive finite field operation in ECC. The two predominant algorithms for computing finite field inversion are Fermat’s Little Theorem (FLT) and Extended Euclidean Algorithm (EEA). EEA is reported to be the most efficient inversion algorithm in terms of performance and power consumption. This dissertation presents a new reformulation of EEA algorithm, which allows for speedup and optimization techniques such as concurrency and resource sharing. Modular arithmetic operations over GF(p) are introduced for small values of p, observing interesting figures, particularly for modular division. Whereas, polynomial arithmetic operations over GF(pm) are discussed adequately in order to examine the potential for processes concurrency. In particular, polynomial division and multiplication are revisited in order to derive their iterative equations, which are suitable for systolic array implementation. Consequently, several designs are proposed for each individual process and their complexities are analyzed and compared. Subsequently, a concurrent divider/multiplier-accumulator is developed, while the resulting systolic architecture is utilized to build the EEA-based inverter. The processing elements of our systolic architectures are created accordingly, and enhanced to accommodate data management throughout our reformulated EEA algorithm. Meanwhile, accurate models for the complexity analysis of the proposed inverters are developed. Finally, a novel, fast, and compact inverter over binary fields is proposed and implemented on FPGA. The proposed design outperforms the reported inverters in terms of area and speed. Correspondingly, an EEA-based inverter over ternary fields is built, showing the lowest area-time complexity among the reported inverters. / Graduate

Submitted by (lucia.rodrigues@ufrpe.br) on 2017-03-29T14:30:56Z No. of bitstreams: 1 Sidmar Bezerra dos Prazeres.pdf: 511759 bytes, checksum: cf327985c0961f16751448a107717241 (MD5) / Made available in DSpace on 2017-03-29T14:30:56Z (GMT). No. of bitstreams: 1 Sidmar Bezerra dos Prazeres.pdf: 511759 bytes, checksum: cf327985c0961f16751448a107717241 (MD5) Previous issue date: 2014-06-16 / This paper aims to show the reader the importance of some topics of Number Theory. Work here, and prerequisites (Euclid Algorithms, Divisibility, Maxim Common Divisor), content with Linear Diophantine equations, congruences, and the main theme, which is the mighty Chinese Remainder Theorem of presenting their theories, importance, applicability on the day and its usefulness in the Theory of Numbers. The main applicability of Chinese Remainder Theorem of this work is Sharing Passwords. Sharing of passwords is a security mechanism, where a certain amount of people take possession of a key to access the secret without the possibility of obtaining the secret with his own key. / Este trabalho tem como objetivo mostrar ao leitor a importância de alguns t ópicos da Teoria dos N úmeros. Trabalharemos aqui, al ém de pré-requisitos (Algoritmo de Euclides, Divisibilidade, M áximo Divisor Comum), conte údos como Equa ções Diofantinas Lineares, Congruências e o principal tema, que e o poderoso Teorema Chinês dos Restos, apresentando suas teorias, importâncias, aplicabilidade no dia a dia e sua a utilidade na Teoria dos N úmeros. A principal aplicabilidade do Teorema Chinês apresentada neste trabalho e a Partilha de Senhas. Esta partilha de senhas é um mecanismo de seguran ça, onde uma certa quantidade de pessoas tomam posse de uma chave de acesso sem a possibilidade de obter a senha principal com a sua pr ópria chave.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2014-11-24T11:32:03Z No. of bitstreams: 2 Mestrado - Amanda Melo do Nascimento - 2013.pdf: 1240146 bytes, checksum: 0126ba6aa1a69a061f1ffabfaf21e9be (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2014-11-24T14:00:24Z (GMT) No. of bitstreams: 2 Mestrado - Amanda Melo do Nascimento - 2013.pdf: 1240146 bytes, checksum: 0126ba6aa1a69a061f1ffabfaf21e9be (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2014-11-24T14:00:24Z (GMT). No. of bitstreams: 2 Mestrado - Amanda Melo do Nascimento - 2013.pdf: 1240146 bytes, checksum: 0126ba6aa1a69a061f1ffabfaf21e9be (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2013-03-15 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Continued Fractions and applications in High School begins with the historical context, the socially constructed over 2500 years, over which originated the study and training of numerical sets in order to substantiate the importance of irrational numbers and their peculiarities . Reintroducing some basic concepts of Numerical Sequences and their converging that are important for understanding the study of approaches from the study of continuous fraction. The discussion and centered on the study of continued fractions, exploring its historical part, basic concepts and their relation to the Euclidean algorithm. It is shown the importance of both approximations of rational numbers as irrational, in order to decrease the gap between finite and infinite for the construction of all the dollars. In the final chapter I present a mini-course for high school students, public school, looking for higher courses in the exact sciences and aim to achieve greater integration with this important segment. All matters discussed in this work will be developed in the course, showing their properties and applications. / Frações Contínuas e aplicações no Ensino Médio inicia-se com o contexto histórico, socialmente construído a mais de 2500 anos, sobre o qual se originou o estudo e formação dos conjuntos numéricos com o objetivo de fundamentar a importância dos números irracionais e suas peculiaridades. Retoma alguns conceitos básicos de Sequências Numéricas e seus convergentes que são importantes para a compreensão do estudo das aproximações a partir do estudo de Fração contínua. A discussão é centralizada no estudo das frações contínuas, explorando sua parte histórica, conceitos básicos e sua relação com o Algoritmo de Euclides. É mostrada a importância das aproximações tanto de números racionais como irracionais,afim de diminuir o abismo existente entre o finito e o infinito para a construção do conjunto dos Reais. No capítulo final apresento um minicurso para alunos do Ensino Médio, de escola pública, que buscam por cursos superiores na área de exatas e objetivam alcançar uma maior integração com este importante segmento. Todos os assuntos abordados neste Trabalho serão desenvolvidos no curso, mostrando suas propriedades e aplicações.

The work deals with the encoding and decoding of Reed-Solomon codes. There is generally described algebraic decoding of Reed-Solomon codes, and then described four methods of decoding, namely Massey-Berlekamp algorithm, Euclidean algoritus, Peterson-Gorenstein-Zierler algorithm and the direct method. These methods are then compared, and some of them are implemented in Matlab.