on a class of pseudorandom sequences from elliptic curves over finite fields

Following the idea of Xing et al., we investigate a general method for constructing families of pseudorandom sequences with low correlation and large linear complexity from elliptic curves over finite fields in this correspondence. With the help of the tool of exponential sums on elliptic curves, we study their periods, linear complexities, linear complexity profiles, distributions of r-patterns, periodic correlation, partial period distributions, and aperiodic correlation in detail. The results show that they have nice randomness.

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.

Distributed Function Computation over Fields and Rings via Linear Compression of Sources

The setting considered in this paper is one of distributed function computation. More specifically, there is a collection of N sources possessing correlated information and a destination that would like to acquire a specific linear combination of the N sources. We address both the case when the common alphabet of the sources is a finite field and the case when it is a finite, commutative principal ideal ring with identity. The goal is to minimize the total amount of information needed to be transmitted by the N sources while enabling reliable recovery at the destination of the linear combination sought. One means of achieving this goal is for each of the sources to compress all the information it possesses and transmit this to the receiver. The Slepian-Wolf theorem of information theory governs the minimum rate at which each source must transmit while enabling all data to be reliably recovered at the receiver. However, recovering all the data at the destination is often wasteful of resources since the destination is only interested in computing a specific linear combination. An alternative explored here is one in which each source is compressed using a common linear mapping and then transmitted to the destination which then proceeds to use linearity to directly recover the needed linear combination. The article is part review and presents in part, new results. The portion of the paper that deals with finite fields is previously known material, while that dealing with rings is mostly new.Attempting to find the best linear map that will enable function computation forces us to consider the linear compression of source. While in the finite field case, it is known that a source can be linearly compressed down to its entropy, it turns out that the same does not hold in the case of rings. An explanation for this curious interplay between algebra and information theory is also provided in this paper.

Information sets and partial permutation decoding for codes from finite geometries

Mavron, Vassili; McDonough, T.P.; Key, J.D., (2006) 'Information sets and partial permutation decoding for codes from finite geometries', Finite Fields and their applications 12(2) pp.232-247 RAE2008