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

Key predistribution scheme using finite fields and reed muller codes

Resource constraint sensors of a Wireless Sensor Network (WSN) cannot afford the use of costly encryption techniques like public key while dealing with sensitive data. So symmetric key encryption techniques are preferred where it is essential to have the same cryptographic key between communicating parties. To this end, keys are preloaded into the nodes before deployment and are to be established once they get deployed in the target area. This entire process is called key predistribution. In this paper we propose one such scheme using unique factorization of polynomials over Finite Fields. To the best of our knowledge such an elegant use of Algebra is being done for the first time in WSN literature. The best part of the scheme is large number of node support with very small and uniform key ring per node. However the resiliency is not good. For this reason we use a special technique based on Reed Muller codes proposed recently by Sarkar, Saha and Chowdhury in 2010. The combined scheme has good resiliency with huge node support using very less keys per node.

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

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.

Class Notes for Math 901/902: Abstract Algebra, Instructor Tom Marley

Topics include: Free groups and presentations; Automorphism groups; Semidirect products; Classification of groups of small order; Normal series: composition, derived, and solvable series; Algebraic field extensions, splitting fields, algebraic closures; Separable algebraic extensions, the Primitive Element Theorem; Inseparability, purely inseparable extensions; Finite fields; Cyclotomic field extensions; Galois theory; Norm and trace maps of an algebraic field extension; Solvability by radicals, Galois' theorem; Transcendence degree; Rings and modules: Examples and basic properties; Exact sequences, split short exact sequences; Free modules, projective modules; Localization of (commutative) rings and modules; The prime spectrum of a ring; Nakayama's lemma; Basic category theory; The Hom functors; Tensor products, adjointness; Left/right Noetherian and Artinian modules; Composition series, the Jordan-Holder Theorem; Semisimple rings; The Artin-Wedderburn Theorem; The Density Theorem; The Jacobson radical; Artinian rings; von Neumann regular rings; Wedderburn's theorem on finite division rings; Group representations, character theory; Integral ring extensions; Burnside's paqb Theorem; Injective modules.