Constructions of algebraic lattices

In this work we present constructions of algebraic lattices in Euclidean space with optimal center density in dimensions 2, 3, 4, 6, 8 and 12, which are rotated versions of the lattices Λn, for n = 2,3,4,6,8 and K12. These algebraic lattices are constructed through twisted canonical homomorphism via ideals of a ring of algebraic integers. Mathematical subject classification: 18B35, 94A15, 20H10.

On the Optimality of Finite Constellations from Algebraic Lattices

A construction technique of finite point constellations in n-dimensional spaces from ideals in rings of algebraic integers is described. An algorithm is presented to find constellations with minimum average energy from a given lattice. For comparison, a numerical table of lattice constellations and group codes is computed for spaces of dimension two, three, and four. © 2001.

Sur la répartition des unités dans les corps quadratiques réels

Ce mémoire s'emploie à étudier les corps quadratiques réels ainsi qu'un élément particulier de tels corps quadratiques réels : l'unité fondamentale. Pour ce faire, le mémoire commence par présenter le plus clairement possible les connaissances sur différents sujets qui sont essentiels à la compréhension des calculs et des résultats de ma recherche. On introduit d'abord les corps quadratiques ainsi que l'anneau de ses entiers algébriques et on décrit ses unités. On parle ensuite des fractions continues puisqu'elles se retrouvent dans un algorithme de calcul de l'unité fondamentale. On traite ensuite des formes binaires quadratiques et de la formule du nombre de classes de Dirichlet, laquelle fait intervenir l'unité fondamentale en fonction d'autres variables. Une fois cette tâche accomplie, on présente nos calculs et nos résultats. Notre recherche concerne la répartition des unités fondamentales des corps quadratiques réels, la répartition des unités des corps quadratiques réels et les moments du logarithme de l'unité fondamentale. (Le logarithme de l'unité fondamentale est appelé le régulateur.)

Computing Generators of Free Modules over Orders in Group Algebras

Let E be a number field and G be a finite group. Let A be any O_E-order of full rank in the group algebra E[G] and X be a (left) A-lattice. We give a necessary and sufficient condition for X to be free of given rank d over A. In the case that the Wedderburn decomposition E[G] \cong \oplus_xM_x is explicitly computable and each M_x is in fact a matrix ring over a field, this leads to an algorithm that either gives elements \alpha_1,...,\alpha_d \in X such that X = A\alpha_1 \oplus ... \oplusA\alpha_d or determines that no such elements exist. Let L/K be a finite Galois extension of number fields with Galois group G such that E is a subfield of K and put d = [K : E]. The algorithm can be applied to certain Galois modules that arise naturally in this situation. For example, one can take X to be O_L, the ring of algebraic integers of L, and A to be the associated order A(E[G];O_L) \subseteq E[G]. The application of the algorithm to this special situation is implemented in Magma under certain extra hypotheses when K = E = \IQ.

Torres de extensões abelianas de grau primo ímpar não ramificado

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

On the Error-Free Computation of Fast Cosine Transform

We extend our previous work into error-free representations of transform basis functions by presenting a novel error-free encoding scheme for the fast implementation of a Linzer-Feig Fast Cosine Transform (FCT) and its inverse. We discuss an 8x8 L-F scaled Discrete Cosine Transform where the architecture uses a new algebraic integer quantization of the 1-D radix-8 DCT that allows the separable computation of a 2-D DCT without any intermediate number representation conversions. The resulting architecture is very regular and reduces latency by 50% compared to a previous error-free design, with virtually the same hardware cost.

Multiplierless DCT Algorithm for Image Compression Applications

This paper presents a novel error-free (infinite-precision) architecture for the fast implementation of 8x8 2-D Discrete Cosine Transform. The architecture uses a new algebraic integer encoding of a 1-D radix-8 DCT that allows the separable computation of a 2-D 8x8 DCT without any intermediate number representation conversions. This is a considerable improvement on previously introduced algebraic integer encoding techniques to compute both DCT and IDCT which eliminates the requirements to approximate the transformation matrix ele- ments by obtaining their exact representations and hence mapping the transcendental functions without any errors. Apart from the multiplication-free nature, this new mapping scheme fits to this algorithm, eliminating any computational or quantization errors and resulting short-word-length and high-speed-design.

Algebraic Cryptanalysis of CTRU Cryptosystem

CTRU, a public key cryptosystem was proposed by Gaborit, Ohler and Sole. It is analogue of NTRU, the ring of integers replaced by the ring of polynomials $\mathbb{F}_2[T]$ . It attracted attention as the attacks based on either LLL algorithm or the Chinese Remainder Theorem are avoided on it, which is most common on NTRU. In this paper we presents a polynomial-time algorithm that breaks CTRU for all recommended parameter choices that were derived to make CTRU secure against popov normal form attack. The paper shows if we ascertain the constraints for perfect decryption then either plaintext or private key can be achieved by polynomial time linear algebra attack.

Computations in Relative Algebraic K-Groups

Let G be finite group and K a number field or a p-adic field with ring of integers O_K. In the first part of the manuscript we present an algorithm that computes the relative algebraic K-group K_0(O_K[G],K) as an abstract abelian group. We solve the discrete logarithm problem, both in K_0(O_K[G],K) and the locally free class group cl(O_K[G]). All algorithms have been implemented in MAGMA for the case K = \IQ. In the second part of the manuscript we prove formulae for the torsion subgroup of K_0(\IZ[G],\IQ) for large classes of dihedral and quaternion groups.

The Distribution of the Irreducibles in an Algebraic Number Field

The objective of this thesis is to study the distribution of the number of principal ideals generated by an irreducible element in an algebraic number field, namely in the non-unique factorization ring of integers of such a field. In particular we are investigating the size of M(x), defined as M ( x ) =∑ (α) α irred.|N (α)|≤≠ 1, where x is any positive real number and N (α) is the norm of α. We finally obtain asymptotic results for hl(x).

Algebraic Analysis of LEX

LEX is a stream cipher that progressed to Phase 3 of the eSTREAM stream cipher project. In this paper, we show that the security of LEX against algebraic attacks relies on a small equation system not being solvable faster than exhaustive search. We use the byte leakage in LEX to construct a system of 21 equa- tions in 17 variables. This is very close to the require- ment for an efficient attack, i.e. a system containing 16 variables. The system requires only 36 bytes of keystream, which is very low.

Investigating functional thinking in the elementary classroom : foundations of early algebraic reasoning

This paper examines the development of student functional thinking during a teaching experiment that was conducted in two classrooms with a total of 45 children whose average age was nine years and six months. The teaching comprised four lessons taught by a researcher, with a second researcher and classroom teacher acting as participant observers. These lessons were designed to enable students to build mental representations in order to explore the use of function tables by focusing on the relationship between input and output numbers with the intention of extracting the algebraic nature of the arithmetic involved. All lessons were videotaped. The results indicate that elementary students are not only capable of developing functional thinking but also of communicating their thinking both verbally and symbolically.

Algebraic analysis of small scale LEX-BES

This paper examines the algebraic cryptanalysis of small scale variants of the LEX-BES. LEX-BES is a stream cipher based on the Advanced Encryption Standard (AES) block cipher. LEX is a generic method proposed for constructing a stream cipher from a block cipher, initially introduced by Biryukov at eSTREAM, the ECRYPT Stream Cipher project in 2005. The Big Encryption System (BES) is a block cipher introduced at CRYPTO 2002 which facilitates the algebraic analysis of the AES block cipher. In this paper, experiments were conducted to find solution of the equation system describing small scale LEX-BES using Gröbner Basis computations. This follows a similar approach to the work by Cid, Murphy and Robshaw at FSE 2005 that investigated algebraic cryptanalysis on small scale variants of the BES. The difference between LEX-BES and BES is that due to the way the keystream is extracted, the number of unknowns in LEX-BES equations is fewer than the number in BES. As far as the author knows, this attempt is the first at creating solvable equation systems for stream ciphers based on the LEX method using Gröbner Basis computations.