In 1980, L. Adleman, C. Pomerance, and R. Rumely invented the first cyclotomicprimality test, and shortly after, in 1981, a simplified and more efficient versionwas presented by H.W. Lenstra for the Bourbaki Seminar. Later, in 2008, ReneSchoof presented an updated version of Lenstra's primality test. This thesis presents adetailed description of the cyclotomic primality test as described by Schoof, along withsuggestions for implementation. The cornerstone of the test is a prime congruencerelation similar to Fermat's little theorem" that involves Gauss or Jacobi sumscalculated over cyclotomic fields. The algorithm runs in very nearly polynomial time.This primality test is currently one of the most computationally efficient tests and isused by default for primality proving by the open source mathematics systems Sageand PARI/GP. It can quickly test numbers with thousands of decimal digits.

Thesis (MSc)--University of Stellenbosch, 2008. / Bibliography. Also available via the Internet.

Orientador: Trajano Pires da Nóbrega Neto / Banca: André Luíz Flores / Banca: José Othon Dantas Lopes / Resumo: O principal objetivo deste trabalho é calcular a densidade de centro da representação geométrica do ideal totalmente ramificado em corpos de condutor primo. Primeiro, fazemos a caracterização dos subcorpos do p-ésimo corpo ciclotômico e dos elementos do ideal, também calculamos a norma desse ideal. Em seguida, é apresentada uma forma quadrática e explicitado o seu mínimo para o cálculo do raio de empacotamento dessa representação geométrica. Finalizamos com o cálculo da densidade de centro. / Abstract: The main aim of this work is to calculate density of the center from the geometric representation of the totally ramified ideal in prime conductor fields. First of all, we make the characterization of the elements from subfields of the p-th cyclotomic field and from the ideal of the elements, we also calculate the norm of this ideal. After that, a quadratic form is presented and exhibit its minimun for the radius of packing calculation this geometric representation. Concluding with the center density calculation. / Mestre

Made available in DSpace on 2014-06-11T19:26:56Z (GMT). No. of bitstreams: 0 Previous issue date: 2005-12-16Bitstream added on 2014-06-13T18:06:54Z : No. of bitstreams: 1 melo_fd_me_sjrp.pdf: 346555 bytes, checksum: ff1f3651e3e5a108fe83b33dbae4e46b (MD5) / O principal objetivo deste trabalho é calcular a densidade de centro da representação geométrica do ideal totalmente ramificado em corpos de condutor primo. Primeiro, fazemos a caracterização dos subcorpos do p-ésimo corpo ciclotômico e dos elementos do ideal, também calculamos a norma desse ideal. Em seguida, é apresentada uma forma quadrática e explicitado o seu mínimo para o cálculo do raio de empacotamento dessa representação geométrica. Finalizamos com o cálculo da densidade de centro. / The main aim of this work is to calculate density of the center from the geometric representation of the totally ramified ideal in prime conductor fields. First of all, we make the characterization of the elements from subfields of the p-th cyclotomic field and from the ideal of the elements, we also calculate the norm of this ideal. After that, a quadratic form is presented and exhibit its minimun for the radius of packing calculation this geometric representation. Concluding with the center density calculation.

No description available.

Seja K/Q uma extensÃo abeliana de grau primo Ãmpar ρ e condutor n, onde ρ nÃo se ramifica em K/Q. As principais contribuiÃÃes deste trabalho sÃo: 1) caracterizaÃÃo de ideais Ok em cuja fatoraÃÃo constam apenas ideais primos ramificados K/Q; 2) cÃlculo da densidade de centro da representaÃÃo geomÃtrica de Z-mÃdulos em Ok caracterizados por uma equaÃÃo modular (para ρ = 3,5 e 7, parametriza-se o algoritmo que otimiza a densidade de centro destes reticulados). AlÃm disso, os seguintes resultados sÃo tambÃm descritos: 1) FamÃlias de reticulados associados a polinÃmios em Z[x] de grau dois e trÃs; 2) uma prova alternativa da finitude do grupo das classes de um corpo nÃmeros baseada somente em empacotamentos esfÃricos. / Let K/Q be an Abelian extension of ood degree ρ and conductor n, where ρ does not ramify in K/Q. The main contributions of this work are: 1) characterization of ideals of Ok whose factorization includes only prime ramified ideals K/Q; 2) calculation of the center density of the geometric representation of Z-modules in Ok characterized by a modular equation (for ρ = 3.5, and 7, the algorithm that is used to optimize the center density of those lattices is parametrized). Besides, the following results are also described: 1) Families of lattices associated to polynomials in Z[x] of degree two and three; 2) an alternative proof of the finiteness of the class group of a number field based solely on sphere packings.

Thesis (MSc (Mathematical Sciences))--Stellenbosch University, 2008. / Class field theory describes the abelian extensions of a given field K in terms of various class groups of K, and can be viewed as one of the great successes of 20th century number theory. However, the main results in class field theory are pure existence results, and do not give explicit constructions of these abelian extensions. Such explicit constructions are possible for a variety of special cases, such as for the field Q of rational numbers, or for quadratic imaginary fields. When K is a global function field, however, there is a completely explicit description of the abelian extensions of K, utilising the theory of sign-normalised Drinfeld modules of rank one. In this thesis we give detailed survey of explicit class field theory for rational function fields over finite fields, and of the fundamental results needed to master this topic.

Neste projeto, propomos estudar a chamada \"Teoria de Corpos de Classe,\" que oferece uma descrição simples das extensões abelianas de corpos locais e globais, bem como algumas de suas aplicações, como os teoremas de Kronecker-Weber e Scholz-Reichardt / In this work, we study the so called \"Class Field Theory\", which give us a simple description of the abelian extension of local and global elds. We also study some applications, like the Kronecker-Weber and Scholz-Reichardt theorems

In this digital age, cryptography is largely built in computer hardware or software as discrete structures. One of the most useful of these structures is finite fields. In this thesis, we explore a variety of applications of the theory and applications of arithmetic and computation in finite fields in both the areas of cryptography and cryptanalysis. First, multiplication algorithms in finite extensions of prime fields are explored. A new algebraic description of implementing the subquadratic Karatsuba algorithm and its variants for extension field multiplication are presented. The use of cy- clotomic fields and Gauss periods in constructing suitable extensions of virtually all sizes for efficient arithmetic are described. These multiplication techniques are then applied on some previously proposed public key cryptosystem based on exten- sion fields. These include the trace-based cryptosystems such as XTR, and torus- based cryptosystems such as CEILIDH. Improvements to the cost of arithmetic were achieved in some constructions due to the capability of thorough optimisation using the algebraic description. Then, for symmetric key systems, the focus is on algebraic analysis and attacks of stream ciphers. Different techniques of computing solutions to an arbitrary system of boolean equations were considered, and a method of analysing and simplifying the system using truth tables and graph theory have been investigated. Algebraic analyses were performed on stream ciphers based on linear feedback shift registers where clock control mechanisms are employed, a category of ciphers that have not been previously analysed before using this method. The results are successful algebraic attacks on various clock-controlled generators and cascade generators, and a full algebraic analyses for the eSTREAM cipher candidate Pomaranch. Some weaknesses in the filter functions used in Pomaranch have also been found. Finally, some non-traditional algebraic analysis of stream ciphers are presented. An algebraic analysis on the word-based RC4 family of stream ciphers is performed by constructing algebraic expressions for each of the operations involved, and it is concluded that each of these operations are significant in contributing to the overall security of the system. As far as we know, this is the first algebraic analysis on a stream cipher that is not based on linear feedback shift registers. The possibility of using binary extension fields and quotient rings for algebraic analysis of stream ciphers based on linear feedback shift registers are then investigated. Feasible algebraic attacks for generators with nonlinear filters are obtained and algebraic analyses for more complicated generators with multiple registers are presented. This new form of algebraic analysis may prove useful and thereby complement the traditional algebraic attacks. This thesis concludes with some future directions that can be taken and some open questions. Arithmetic and computation in finite fields will certainly be an important area for ongoing research as we are confronted with new developments in theory and exponentially growing computer power.

Made available in DSpace on 2014-06-11T19:26:55Z (GMT). No. of bitstreams: 0 Previous issue date: 2009-02-27Bitstream added on 2014-06-13T20:08:06Z : No. of bitstreams: 1 rayzaro_os_me_sjrp.pdf: 628267 bytes, checksum: 09181fbba2d539fd6135f0b473b3b345 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Neste trabalho vemos que a imagem de um ideal do anel dos inteiros dos corpos de números, via o homomorfismo de Minkowski, é um reticulado, chamado de reticulado algébrico. Assim, o principal objetivo deste trabalho é a construção de reticulados algébricos de dimensão 2; 4; 6 e 8, com densidade de centro ótimo. / In this work, we see that the image of an ideal from the algebraic integer ring of the numbers ¯elds by the Minkowski homomorphism is a lattice, named algebraic lattice. In this way, the main aim of this work is the construction of algebraic lattices of dimensions 2,4,6 and 8, with the center density excellent.