Qualified difference sets are a class of combinatorial configuration. The sets are related to the residue difference sets that were first discussed in detail in 1953 by Emma Lehmer. Qualified difference sets consist of a set of residues modulo an integer v and they possess attractive properties that suggest potential applications in areas such as image formation, signal processing and aperture synthesis. This thesis outlines the theory behind qualified difference sets and gives conditions for the existence and nonexistence of these sets in various cases. A special case of the qualified difference sets is the qualified residue difference sets. These consist of the set of nth power residues of certain types of prime. Necessary and sufficient conditions for the existence of qualified residue difference sets are derived and the precise conditions for the existence of these sets are given for n = 2, 4 and 6. Qualified residue difference sets are proved nonexistent for n = 8, 10, 12, 14 and 18. A generalisation of the qualified residue difference sets is introduced. These are the qualified difference sets composed of unions of cyclotomic classes. A cyclotomic class is defined for an integer power n and the results of an exhaustive computer search are presented for n = 4, 6, 8, 10 and 12. Two new families of qualified difference set were discovered in the case n = 8 and some isolated systems were discovered for n = 6, 10 and 12. An explanation of how qualified difference sets may be implemented in physical applications is given and potential applications are discussed.

In this dissertation, we explore the nature of Schur rings over finite cyclic groups, both algebraically and combinatorially. We provide a survey of many fundamental properties and constructions of Schur rings over arbitrary finite groups. After specializing to the case of cyclic groups, we provide an extensive treatment of the idempotents of Schur rings and a description for the complete set of primitive idempotents. We also use Galois theory to provide a classification theorem of Schur rings over cyclic groups similar to a theorem of Leung and Man and use this classification to provide a formula for the number of Schur rings over cyclic p-groups.

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

Seja Cp um grupo cíclico de ordem p, onde p é um número primo tal que S = {1, , 1+\\theta, 1+\\theta+\\theta^2, · · · , 1 +\\theta + · · · + \\theta ^{p-3/2}} gera o grupo das unidades de Z[\\theta] e é uma raiz p-ésima primitiva da unidade sobre Q. No artigo \"Units of ZCp\" , Ferraz apresentou um modo simples de encontrar um conjunto de geradores independentes para o grupo das unidades do anel de grupo ZCp sobre os inteiros. Nós estendemos este resultado para ZCp^n , considerando que um conjunto similar a S gera o grupo das unidades de Z[\\theta]. Isto ocorre, por exemplo, quando \\phi(p^n)\\leq 66. Descrevemos o grupo das unidades de ZCp^n como o produto ±ker(\\pi_1) × Im(\\pi1), onde \\pi_1 é um homomorfismo de grupos. Além disso, explicitamos as bases de ker(\\pi_1) e Im(\\pi_1). / Let Cp be a cyclic group of order p, where p is a prime integer such that S = {1, , 1 + \\theta, 1 +\\theta +\\theta ^2 , · · · , 1 + \\theta + · · · +\\theta ^{p-3/2}} generates the group of units of Z[\\theta] and is a primitive pth root of 1 over Q. In the article \"Units of ZCp\" , Ferraz gave an easy way to nd a set of multiplicatively independent generators of the group of units of the integral group ring ZCp . We extended this result for ZCp^n , provided that a set similar to S generates the group of units of Z[\\theta]. This occurs, for example, when \\phi(p^n)\\leq 66. We described the group of units of ZCp^n as the product ±ker(\\pi_1) × Im(\\pi_1), where \\pi_1 is a group homomorphism. Moreover, we explicited a basis of ker(\\pi_1) and I m(\\pi_1).

In 1878, Lucas \cite{lucas} investigated the sequences $(\ell_n)_{n=0}^\infty$ where $$\ell_n=\frac{\alpha^n-\beta^n}{\alpha-\beta},$$ $\alpha \beta$ and $\alpha+\beta$ are coprime integers, and where $\beta/\alpha$ is not a root of unity. Lucas sequences are divisibility sequences; if $m|n$, then $\ell_m|\ell_n$, and more generally, $\gcd(\ell_m,\ell_n)=\ell_{\gcd(m,n)}$ for all positive integers $m$ and $n$. Matijasevic utilised this divisibility property of Lucas sequences in order to resolve Hilbert's 10th problem. \noindent In 1930, Lehmer \cite{lehmer} introduced the sequences $(u_n)_{n=0}^\infty$ where \begin{eqnarray*} u_n& = & \frac{\alpha^{n}-\beta^n}{\alpha^{\epsilon(n)}-\beta^{\epsilon(n)}},\\ \epsilon(n)&=&\left\{\begin{array}{ll} 1, \hspace{.1in}\mbox{if}\hspace{.1in}n\equiv 1 \pmod 2;\\ 2, \hspace{.1in}\mbox{if}\hspace{.1in}n\equiv 0\pmod 2;\end{array}\right. \end{eqnarray*} $\alpha \beta$ and $(\alpha +\beta)^2$ are coprime integers, and where $\beta/\alpha$ is not a root of unity. The sequences $(u_n)_{n=0}^\infty$ are known as Lehmer sequences, and the terms of these sequences are known as Lehmer numbers. Lehmer showed that his sequences had similar divisibility properties to those of Lucas sequences, and he used them to extend the Lucas test for primality. \noindent We define a prime divisor $p$ of $u_n$ to be a primitive divisor of $u_n$ if $p$ does not divide $$(\alpha^2-\beta^2)^2u_3\cdots u_{n-1}.$$ Note that in the list of prime factors of the first $n-1$ terms of the sequence $(u_n)_{n=0}^\infty$, a primitive divisor of $u_n$ is a new prime factor. \noindent We let \begin{eqnarray*} \kappa& = & k(\alpha \beta\max\{(\alpha-\beta)^2,(\alpha+\beta)^2\}),\\ \eta & = & \left\{\begin{array}{ll}1\hspace{.1in}\mbox{if}\hspace{.1in}\kappa\equiv 1\pmod 4,\\ 2\hspace{.1in}\mbox{otherwise},\end{array}\right. \end{eqnarray*} where $k(\alpha \beta \max\{(\alpha-\beta)^2,(\alpha+\beta)^2\})$ is the squarefree kernel of $\alpha \beta \max\{(\alpha-\beta)^2,(\alpha+\beta)^2\}$. On the one hand, building on the work of Schinzel \cite{schinzelI}, we prove that if $n>4$, $n\neq 6$, $n/(\eta \kappa)$ is an odd integer, and the triple $(n,\alpha,\beta)$, in case $(\alpha-\beta)^2>0$, is not equivalent to a triple $(n,\alpha,\beta)$ from an explicit table, then the $n$th Lehmer number $u_n$ has at least two primitive divisors. Moreover, we prove that if $n\geq 1.2\times 10^{10}$, and $n/(\eta \kappa)$ is an odd integer, then the $n$th Lehmer number $u_n$ has at least two primitive divisors. On the other hand, building on the work of Stewart \cite{stewart77}, we prove that there are only finitely many triples $(n,\alpha,\beta)$, where $n>6$, $n\neq 12$, and $n/(\eta \kappa)$ is an odd integer, such that the $n$th Lehmer number $u_n$ has less than two primitive divisors, and that these triples may be explicitly determined. We determine all of these triples $(n,\alpha,\beta)$ up to equivalence explicitly when $6<n\leq 30$, $n\neq 12$, and $n/(\eta \kappa)$ is an odd integer, and we tabulate the triples $(n,\alpha,\beta)$ we discovered, up to equivalence, for $30<n\leq 500$. Finally, we show that the conditions $n>6$, $n\neq 12$, are best possible, subject to the truth of two plausible conjectures.

In 1878, Lucas \cite{lucas} investigated the sequences $(\ell_n)_{n=0}^\infty$ where $$\ell_n=\frac{\alpha^n-\beta^n}{\alpha-\beta},$$ $\alpha \beta$ and $\alpha+\beta$ are coprime integers, and where $\beta/\alpha$ is not a root of unity. Lucas sequences are divisibility sequences; if $m|n$, then $\ell_m|\ell_n$, and more generally, $\gcd(\ell_m,\ell_n)=\ell_{\gcd(m,n)}$ for all positive integers $m$ and $n$. Matijasevic utilised this divisibility property of Lucas sequences in order to resolve Hilbert's 10th problem. \noindent In 1930, Lehmer \cite{lehmer} introduced the sequences $(u_n)_{n=0}^\infty$ where \begin{eqnarray*} u_n& = & \frac{\alpha^{n}-\beta^n}{\alpha^{\epsilon(n)}-\beta^{\epsilon(n)}},\\ \epsilon(n)&=&\left\{\begin{array}{ll} 1, \hspace{.1in}\mbox{if}\hspace{.1in}n\equiv 1 \pmod 2;\\ 2, \hspace{.1in}\mbox{if}\hspace{.1in}n\equiv 0\pmod 2;\end{array}\right. \end{eqnarray*} $\alpha \beta$ and $(\alpha +\beta)^2$ are coprime integers, and where $\beta/\alpha$ is not a root of unity. The sequences $(u_n)_{n=0}^\infty$ are known as Lehmer sequences, and the terms of these sequences are known as Lehmer numbers. Lehmer showed that his sequences had similar divisibility properties to those of Lucas sequences, and he used them to extend the Lucas test for primality. \noindent We define a prime divisor $p$ of $u_n$ to be a primitive divisor of $u_n$ if $p$ does not divide $$(\alpha^2-\beta^2)^2u_3\cdots u_{n-1}.$$ Note that in the list of prime factors of the first $n-1$ terms of the sequence $(u_n)_{n=0}^\infty$, a primitive divisor of $u_n$ is a new prime factor. \noindent We let \begin{eqnarray*} \kappa& = & k(\alpha \beta\max\{(\alpha-\beta)^2,(\alpha+\beta)^2\}),\\ \eta & = & \left\{\begin{array}{ll}1\hspace{.1in}\mbox{if}\hspace{.1in}\kappa\equiv 1\pmod 4,\\ 2\hspace{.1in}\mbox{otherwise},\end{array}\right. \end{eqnarray*} where $k(\alpha \beta \max\{(\alpha-\beta)^2,(\alpha+\beta)^2\})$ is the squarefree kernel of $\alpha \beta \max\{(\alpha-\beta)^2,(\alpha+\beta)^2\}$. On the one hand, building on the work of Schinzel \cite{schinzelI}, we prove that if $n>4$, $n\neq 6$, $n/(\eta \kappa)$ is an odd integer, and the triple $(n,\alpha,\beta)$, in case $(\alpha-\beta)^2>0$, is not equivalent to a triple $(n,\alpha,\beta)$ from an explicit table, then the $n$th Lehmer number $u_n$ has at least two primitive divisors. Moreover, we prove that if $n\geq 1.2\times 10^{10}$, and $n/(\eta \kappa)$ is an odd integer, then the $n$th Lehmer number $u_n$ has at least two primitive divisors. On the other hand, building on the work of Stewart \cite{stewart77}, we prove that there are only finitely many triples $(n,\alpha,\beta)$, where $n>6$, $n\neq 12$, and $n/(\eta \kappa)$ is an odd integer, such that the $n$th Lehmer number $u_n$ has less than two primitive divisors, and that these triples may be explicitly determined. We determine all of these triples $(n,\alpha,\beta)$ up to equivalence explicitly when $6<n\leq 30$, $n\neq 12$, and $n/(\eta \kappa)$ is an odd integer, and we tabulate the triples $(n,\alpha,\beta)$ we discovered, up to equivalence, for $30<n\leq 500$. Finally, we show that the conditions $n>6$, $n\neq 12$, are best possible, subject to the truth of two plausible conjectures.

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.

Made available in DSpace on 2014-06-11T19:26:55Z (GMT). No. of bitstreams: 0 Previous issue date: 2005-12-10Bitstream added on 2014-06-13T20:08:00Z : No. of bitstreams: 1 ramos_gm_me_sjrp.pdf: 353629 bytes, checksum: 1030312b97bd0bb7f95093162b227e48 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / O objetivo principal deste trabalho é estudar a densidade de centro de reticulados obtidos por meio do Método de Minkowski em subcorpos de Q(?pq), com p e q primos ímpares distintos e satisfazendo a condição oq(p) = op(q) = 1 (mod 2). O cálculo da densidade de centro é feito a partir do discriminante do corpo, da norma do ideal e da minimização da forma traço. / This work aims at studying the center density of the lattices got through the Minkowski's Method in subfields of Q(?pq), p and q prime number and oq(p) = op(q) = 1 (mod 2). The calcule of the center density is done using the discriminant of the field, the norm of the ideal and the minimization of trace form.