In this work, the analysis of the computation of the greatest common divisor of univariate and bivariate polynomials is presented. The whole process is split into three stages. In the first stage, data preprocessing is explained and the resulting better numerical behavior is demonstrated. Next stage is concerned with the problem of the computation of the numerical rank of the Sylvester matrix, from which the degree of the greatest common divisor is obtained. The last stage is the actual algorithm for calculating the greatest common divisor of two polynomials. Furthermore, the underlying theory behind the computation of the greatest common divisor is explained and illustrated on many examples. 1

In this thesis we study the computation of the greatest common divisor of two polynomials. Firstly, properties of Sylvester matrices are considered as well as their role in computation. We then note, that this approach can be naturally generalized for several polynomials. In the penultimate section, Bézout matrices are studied as an analogy to the Sylvester ones, providing necessary comparison. Extension for more than polynomials is presented here as well. Algorithms corresponding to the individual approaches are presented as well. Finally, the algorithms are implemented in MATLAB and are compared in numerical experiments. Powered by TCPDF (www.tcpdf.org)

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.

Submitted by Jean Medeiros (jeanletras@uepb.edu.br) on 2017-07-20T17:14:06Z No. of bitstreams: 1 PDF - Erivan Sousa Valentim.pdf: 10186922 bytes, checksum: ffae32fb65fe99f5c16bf7b416d3008d (MD5) / Approved for entry into archive by Secta BC (secta.csu.bc@uepb.edu.br) on 2017-08-29T15:42:48Z (GMT) No. of bitstreams: 1 PDF - Erivan Sousa Valentim.pdf: 10186922 bytes, checksum: ffae32fb65fe99f5c16bf7b416d3008d (MD5) / Made available in DSpace on 2017-08-29T15:42:48Z (GMT). No. of bitstreams: 1 PDF - Erivan Sousa Valentim.pdf: 10186922 bytes, checksum: ffae32fb65fe99f5c16bf7b416d3008d (MD5) Previous issue date: 2017-06-09 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / The purpose of this work is to realize an approach about multiples and divisors, in- cluding the least common multiple and the greatest common divisor, owing to the difficulty that students feel when they faced with such content in basic education, aiming at a better understanding about it and an improvement in the learning of le- arners. The suggestion was applied in an 8th grade class at the Joaquim Limeira de Queiroz Agricultural Technical School, in the city of Puxinan˜ a - PB, in March 2017. They were addressed the definitions of multiples, divisors, prime numbers and the least common multiple and the greatest common divisor, and it was applied activities such as: bingo of the divisors, the sum of the magic square and the construction of the Sieve of Eratosthenes. Finally, we carried out an evaluation exercise with the objective of analyzing if the results regarding the content and the activities previously proposed were satisfactory. / A proposta deste trabalho é de realizar uma abordagem sobre os múltiplos e divisores, incluindo mínimo múltiplo comum e o máximo divisor comum, tendo em vista a dificuldade que os estudantes sentem ao se deparar com tal conteúdo na educação básica, objetivando um melhor entendimento a cerca do conteúdo e uma melhoria no que diz o respeito a aprendizagem dos educandos. A proposta foi aplicada em uma turma de 8 ano na Escola Técnica Agrícola Joaquim Limeira de Queiroz, na cidade de Puxinanã - PB, no mês de março de 2017. Foram abordados as definições de múltiplos, divisores, números primos e mínimo múltiplo comum e máximo divisor comum, e aplicadas atividades tais como: bingo dos divisores, a soma do quadrado mágico e a construção do Crivo de Eratóstenes. Por fim, realizamos um exercício avaliativo com o objetivo de analisar se os resultados a respeito do conteúdo e das atividades propostas anteriormente foram satisfatórias.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2015-10-08T11:31:38Z No. of bitstreams: 2 Dissertação - Luis Henrique Pereira da Silva - 2015.pdf: 1093576 bytes, checksum: 6d4e251c8d5464c6328fb953341355d9 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-10-08T12:56:48Z (GMT) No. of bitstreams: 2 Dissertação - Luis Henrique Pereira da Silva - 2015.pdf: 1093576 bytes, checksum: 6d4e251c8d5464c6328fb953341355d9 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-10-08T12:56:48Z (GMT). No. of bitstreams: 2 Dissertação - Luis Henrique Pereira da Silva - 2015.pdf: 1093576 bytes, checksum: 6d4e251c8d5464c6328fb953341355d9 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2015-03-27 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work aims to demonstrate in a practical way the divisibility criteria 2-97 in sieve Eratostenes with cutting the right and the left, based on the method of multiplication and division Egyptian. The entire process is demonstrated using the divisibility to whole numbers, greatest common divisor, prime numbers, decomposition in prime factors and matching. / Este trabalho tem como objetivo demonstrar de modo prático os critérios de divisibilidade de 2 a 97 no crivo de Eratóstenes com os corte a direita e a esquerda, baseando-se no método de multiplicação e divisão egípcia. Todo processo é demostrado utilizando a divisibilidade para números inteiros, máximo divisor comum, números primos, decomposi ção em fatores primos e congruência.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-05-10T13:29:13Z No. of bitstreams: 1 leticiavasconcellosdesouza.pdf: 334599 bytes, checksum: ecaf1358f31b66f2a2e8740f4db33535 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-06-15T13:12:10Z (GMT) No. of bitstreams: 1 leticiavasconcellosdesouza.pdf: 334599 bytes, checksum: ecaf1358f31b66f2a2e8740f4db33535 (MD5) / Made available in DSpace on 2016-06-15T13:12:10Z (GMT). No. of bitstreams: 1 leticiavasconcellosdesouza.pdf: 334599 bytes, checksum: ecaf1358f31b66f2a2e8740f4db33535 (MD5) Previous issue date: 2015-08-14 / Este trabalho é voltado para professores que atuam nas séries finais do Ensino Fundamental. Tem como objetivo mostrar que é possível introduzir o estudo de Congruência Modular nesse segmento de ensino, buscando facilitar a resolução de diversas situações-problema. A motivação para escolha desse tema é que há a possibilidade de tornar mais simples a resolução de muitos exercícios trabalhados nessa etapa de ensino e que são inclusive cobrados em provas de admissão à escolas militares e em olimpíadas de Matemática para esse nível de escolaridade. Inicialmente é feita uma breve síntese do conjunto dos Números Inteiros, com suas operações básicas, relembrando também o conceito de números primos, onde é apresentado o crivo de Eratóstenes; o mmc (mínimo múltiplo comum) e o mdc (máximo divisor comum), juntamente com o Algoritmo de Euclides. Apresenta-se alguns exemplos de situações-problema e exercícios resolvidos envolvendo restos deixados por uma divisão para então, em seguida, ser dada a definição de congruência modular. Finalmente, são apresentadas sugestões de exercícios para serem trabalhados em sala de aula, com uma breve resolução. / The aims of this work is teachers working in the final grades of elementary school. It aspires to show that it is possible to introduce the study of Modular congruence this educational segment, seeking to facilitate the resolution of numerous problem situations. The motivation for choosing this theme is that there is the possibility to make it simpler to solve many problems worked at this stage of education and are even requested for admittance exams to military schools and mathematical Olympiads for that level of education. We begin with a brief summary about integer numbers, their basic operations, also recalling the concept of prime numbers, where the sieve of Eratosthenes is presented; the lcm (least common multiple) and the gcd (greatest common divisor), along with the Euclidean algorithm. We present some examples of problem situations and solved exercises involving debris left by a division and then, we give the definition of modular congruence . Finally , we present suggestions for exercises to be worked in the classroom, with a short resolution.

L'analyse dynamique intègre des outils propres aux systèmes dynamiques (comme l'opérateur de transfert) au cadre de la combinatoire analytique, et permet ainsi l'analyse d'un grand nombre d'algorithmes et objets qu'on peut associer naturellement à un système dynamique. Dans ce manuscrit de thèse, nous présentons, dans la perspective de l'analyse dynamique, l'étude probabiliste de plusieurs problèmes qui semblent à priori bien différents : l'analyse probabiliste de la fonction de récurrence des mots de Sturm, et l'étude probabiliste de l'algorithme du “logarithme continu”. Les mots de Sturm constituent une famille omniprésente en combinatoire des mots. Ce sont, dans un sens précis, les mots les plus simples qui ne sont pas ultimement périodiques. Les mots de Sturm ont déjà été beaucoup étudiés, notamment par Morse et Hedlund (1940) qui en ont exhibé une caractérisation fondamentale comme des codages discrets de droites à pente irrationnelle. Ce résultat relie ainsi les mots de Sturm au système dynamique d'Euclide. Les mots de Sturm n'avaient jamais été étudiés d'un point de vue probabiliste. Ici nous introduisons deux modèles probabilistes naturels (et bien complémentaires) et y analysons le comportement probabiliste (et asymptotique) de la “fonction de récurrence” ; nous quantifions sa valeur moyenne et décrivons sa distribution sous chacun de ces deux modèles : l'un est naturel du point de vue algorithmique (mais original du point de vue de l'analyse dynamique), et l'autre permet naturellement de quantifier des classes de plus mauvais cas. Nous discutons la relation entre ces deux modèles et leurs méthodes respectives, en exhibant un lien potentiel qui utilise la transformée de Mellin. Nous avons aussi considéré (et c'est un travail en cours qui vise à unifier les approches) les mots associés à deux familles particulières de pentes : les pentes irrationnelles quadratiques, et les pentes rationnelles (qui donnent lieu aux mots de Christoffel). L'algorithme du logarithme continu est introduit par Gosper dans Hakmem (1978) comme une mutation de l'algorithme classique des fractions continues. Il calcule le plus grand commun diviseur de deux nombres naturels en utilisant uniquement des shifts binaires et des soustractions. Le pire des cas a été étudié récemment par Shallit (2016), qui a donné des bornes précises pour le nombre d'étapes et a exhibé une famille d'entrées sur laquelle l'algorithme atteint cette borne. Dans cette thèse, nous étudions le nombre moyen d'étapes, tout comme d'autres paramètres importants de l'algorithme. Grâce à des méthodes d'analyse dynamique, nous exhibons des constantes mathématiques précises. Le système dynamique ressemble à première vue à celui d'Euclide, et a été étudié d'abord par Chan (2005) avec des méthodes ergodiques. Cependant, la présence des puissances de 2 dans les quotients change la nature de l'algorithme et donne une nature dyadique aux principaux paramètres de l'algorithme, qui ne peuvent donc pas être simplement caractérisés dans le monde réel.C'est pourquoi nous introduisons un nouveau système dynamique, avec une nouvelle composante dyadique, et travaillons dans ce système à deux composantes, l'une réelle, et l'autre dyadique. Grâce à ce nouveau système mixte, nous obtenons l'analyse en moyenne de l'algorithme. / Dynamical Analysis incorporates tools from dynamical systems, namely theTransfer Operator, into the framework of Analytic Combinatorics, permitting the analysis of numerous algorithms and objects naturally associated with an underlying dynamical system.This dissertation presents, in the integrated framework of Dynamical Analysis, the probabilistic analysis of seemingly distinct problems in a unified way: the probabilistic study of the recurrence function of Sturmian words, and the probabilistic study of the Continued Logarithm algorithm.Sturmian words are a fundamental family of words in Word Combinatorics. They are in a precise sense the simplest infinite words that are not eventually periodic. Sturmian words have been well studied over the years, notably by Morse and Hedlund (1940) who demonstrated that they present a notable number theoretical characterization as discrete codings of lines with irrationalslope, relating them naturally to dynamical systems, in particular the Euclidean dynamical system. These words have never been studied from a probabilistic perspective. Here, we quantify the recurrence properties of a ``random'' Sturmian word, which are dictated by the so-called ``recurrence function''; we perform a complete asymptotic probabilistic study of this function, quantifying its mean and describing its distribution under two different probabilistic models, which present different virtues: one is a naturaly choice from an algorithmic point of view (but is innovative from the point of view of dynamical analysis), while the other allows a natural quantification of the worst-case growth of the recurrence function. We discuss the relation between these two distinct models and their respective techniques, explaining also how the two seemingly different techniques employed could be linked through the use of the Mellin transform. In this dissertation we also discuss our ongoing work regarding two special families of Sturmian words: those associated with a quadratic irrational slope, and those with a rational slope (not properly Sturmian). Our work seems to show the possibility of a unified study.The Continued Logarithm Algorithm, introduced by Gosper in Hakmem (1978) as a mutation of classical continued fractions, computes the greatest common divisor of two natural numbers by performing division-like steps involving only binary shifts and substractions. Its worst-case performance was studied recently by Shallit (2016), who showed a precise upper-bound for the number of steps and gave a family of inputs attaining this bound. In this dissertation we employ dynamical analysis to study the average running time of the algorithm, giving precise mathematical constants for the asymptotics, as well as other parameters of interest. The underlying dynamical system is akin to the Euclidean one, and was first studied by Chan (around 2005) from an ergodic, but the presence of powers of 2 in the quotients ingrains into the central parameters a dyadic flavour that cannot be grasped solely by studying this system. We thus introduce a dyadic component and deal with a two-component system. With this new mixed system at hand, we then provide a complete average-case analysis of the algorithm by Dynamical Analysis.