Kumar's algorithm for solving Toeplitz systems of equations over finite fields

Adaptació de l'algorisme de Kumar per resoldre sistemes d'equacions amb matrius de Toeplitz sobre els reals a cossos finits en un temps 0 (n log n).

Volcanoes of l-isogenies of elliptic curves over finite fields: the case l=3

This paper is devoted to the study of the volcanoes of l-isogenies of elliptic curves over a finite field, focusing on their height as well as on the location of curves across its different levels. The core of the paper lies on the relationship between the l-Sylow subgroup of an elliptic curve and the level of the volcano where it is placed. The particular case l = 3 is studied in detail, giving an algorithm to determine the volcano of 3-isogenies of a given elliptic curve. Experimental results are also provided.

On Space-Time Trade-Off for Montgomery Multipliers over Finite Fields

La multiplication dans le corps de Galois à 2^m éléments (i.e. GF(2^m)) est une opérations très importante pour les applications de la théorie des correcteurs et de la cryptographie. Dans ce mémoire, nous nous intéressons aux réalisations parallèles de multiplicateurs dans GF(2^m) lorsque ce dernier est généré par des trinômes irréductibles. Notre point de départ est le multiplicateur de Montgomery qui calcule A(x)B(x)x^(-u) efficacement, étant donné A(x), B(x) in GF(2^m) pour u choisi judicieusement. Nous étudions ensuite l'algorithme diviser pour régner PCHS qui permet de partitionner les multiplicandes d'un produit dans GF(2^m) lorsque m est impair. Nous l'appliquons pour la partitionnement de A(x) et de B(x) dans la multiplication de Montgomery A(x)B(x)x^(-u) pour GF(2^m) même si m est pair. Basé sur cette nouvelle approche, nous construisons un multiplicateur dans GF(2^m) généré par des trinôme irréductibles. Une nouvelle astuce de réutilisation des résultats intermédiaires nous permet d'éliminer plusieurs portes XOR redondantes. Les complexités de temps (i.e. le délais) et d'espace (i.e. le nombre de portes logiques) du nouveau multiplicateur sont ensuite analysées: 1. Le nouveau multiplicateur demande environ 25% moins de portes logiques que les multiplicateurs de Montgomery et de Mastrovito lorsque GF(2^m) est généré par des trinômes irréductible et m est suffisamment grand. Le nombre de portes du nouveau multiplicateur est presque identique à celui du multiplicateur de Karatsuba proposé par Elia. 2. Le délai de calcul du nouveau multiplicateur excède celui des meilleurs multiplicateurs d'au plus deux évaluations de portes XOR. 3. Nous determinons le délai et le nombre de portes logiques du nouveau multiplicateur sur les deux corps de Galois recommandés par le National Institute of Standards and Technology (NIST). Nous montrons que notre multiplicateurs contient 15% moins de portes logiques que les multiplicateurs de Montgomery et de Mastrovito au coût d'un délai d'au plus une porte XOR supplémentaire. De plus, notre multiplicateur a un délai d'une porte XOR moindre que celui du multiplicateur d'Elia au coût d'une augmentation de moins de 1% du nombre total de portes logiques.

An improved sum-product estimate for general finite fields

An improved sum-product estimate for subsets of a finite field whose order is not prime is provided. It is shown, under certain conditions, that max{∣∣∣A+A∣∣∣,∣∣∣A⋅A∣∣∣}≫∣∣A∣∣12/11(log2∣∣A∣∣)5/11. This new estimate matches, up to a logarithmic factor, the current best known bound obtained over prime fields by Rudnev

Some classes of semisimple group (and loop) algebras over finite fields

We determine the structure of the semisimple group algebra of certain groups over the rationals and over those finite fields where the Wedderburn decompositions have the least number of simple components We apply our work to obtain similar information about the loop algebras of mdecomposable RA loops and to produce negative answers to the isomorphism problem over various fields (C) 2010 Elsevier Inc All rights reserved

Properties of sparse random matrices over finite fields

Typical properties of sparse random matrices over finite (Galois) fields are studied, in the limit of large matrices, using techniques from the physics of disordered systems. For the case of a finite field GF(q) with prime order q, we present results for the average kernel dimension, average dimension of the eigenvector spaces and the distribution of the eigenvalues. The number of matrices for a given distribution of entries is also calculated for the general case. The significance of these results to error-correcting codes and random graphs is also discussed.

Polynomial Automorphisms Over Finite Fields

It is shown that the invertible polynomial maps over a finite field Fq , if looked at as bijections Fn,q −→ Fn,q , give all possible bijections in the case q = 2, or q = p^r where p > 2. In the case q = 2^r where r > 1 it is shown that the tame subgroup of the invertible polynomial maps gives only the even bijections, i.e. only half the bijections. As a consequence it is shown that a set S ⊂ Fn,q can be a zero set of a coordinate if and only if #S = q^(n−1).

The Divisibility Modulo 4 of Kloosterman Sums over Finite Fields of Characteristic 3

Recently Garashuk and Lisonek evaluated Kloosterman sums K (a) modulo 4 over a finite field F3m in the case of even K (a). They posed it as an open problem to characterize elements a in F3m for which K (a) ≡ 1 (mod4) and K (a) ≡ 3 (mod4). In this paper, we will give an answer to this problem. The result allows us to count the number of elements a in F3m belonging to each of these two classes.

Polynomial automorphisms over finite fields: Mimicking tame maps by the Derksen group

2010 Mathematics Subject Classification: 14L99, 14R10, 20B27.

Whirlwind: a new cryptographic hash function

A new cryptographic hash function Whirlwind is presented. We give the full specification and explain the design rationale. We show how the hash function can be implemented efficiently in software and give first performance numbers. A detailed analysis of the security against state-of-the-art cryptanalysis methods is also provided. In comparison to the algorithms submitted to the SHA-3 competition, Whirlwind takes recent developments in cryptanalysis into account by design. Even though software performance is not outstanding, it compares favourably with the 512-bit versions of SHA-3 candidates such as LANE or the original CubeHash proposal and is about on par with ECHO and MD6.

A family of implementation-friendly BN elliptic curves

For the last decade, elliptic curve cryptography has gained increasing interest in industry and in the academic community. This is especially due to the high level of security it provides with relatively small keys and to its ability to create very efficient and multifunctional cryptographic schemes by means of bilinear pairings. Pairings require pairing-friendly elliptic curves and among the possible choices, Barreto-Naehrig (BN) curves arguably constitute one of the most versatile families. In this paper, we further expand the potential of the BN curve family. We describe BN curves that are not only computationally very simple to generate, but also specially suitable for efficient implementation on a very broad range of scenarios. We also present implementation results of the optimal ate pairing using such a curve defined over a 254-bit prime field. (C) 2001 Elsevier Inc. All rights reserved.

The number of rational points of a class of Artin-Schreier curves

We determine the number of F-q-rational points of a class of Artin-Schreier curves by using recent results concerning evaluations of some exponential sums. In particular, we determine infinitely many new examples of maximal and minimal plane curves in the context of the Hasse-Weil bound. (C) 2002 Elsevier Science (USA).

The Parity of the Number of Irreducible Factors for Some Pentanomials

It is well known that Stickelberger-Swan theorem is very important for determining reducibility of polynomials over a binary field. Using this theorem it was determined the parity of the number of irreducible factors for some kinds of polynomials over a binary field, for instance, trinomials, tetranomials, self-reciprocal polynomials and so on. We discuss this problem for type II pentanomials namely x^m +x^{n+2} +x^{n+1} +x^n +1 \in\ IF_2 [x]. Such pentanomials can be used for efficient implementing multiplication in finite fields of characteristic two. Based on the computation of discriminant of these pentanomials with integer coefficients, it will be characterized the parity of the number of irreducible factors over IF_2 and be established the necessary conditions for the existence of this kind of irreducible pentanomials.

Parity of the Number of Irreducible Factors for Composite Polynomials

Various results on parity of the number of irreducible factors of given polynomials over finite fields have been obtained in the recent literature. Those are mainly based on Swan’s theorem in which discriminants of polynomials over a finite field or the integral ring Z play an important role. In this paper we consider discriminants of the composition of some polynomials over finite fields. The relation between the discriminants of composed polynomial and the original ones will be established. We apply this to obtain some results concerning the parity of the number of irreducible factors for several special polynomials over finite fields.

Digit systems over commutative rings

Let epsilon be a commutative ring with identity and P is an element of epsilon[x] be a polynomial. In the present paper we consider digit representations in the residue class ring epsilon[x]/(P). In particular, we are interested in the question whether each A is an element of epsilon[x]/(P) can be represented modulo P in the form e(0)+ e(1)x + ... + e(h)x(h), where the e(i) is an element of epsilon[x]/(P) are taken from a fixed finite set of digits. This general concept generalizes both canonical number systems and digit systems over finite fields. Due to the fact that we do not assume that 0 is an element of the digit set and that P need not be monic, several new phenomena occur in this context.