Algebraic Properties of Permutation Polynomials

Eiji OKAMOTO  Wayne AITKEN  George Robert BLAKLEY  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E79-A   No.4   pp.494-501
Publication Date: 1996/04/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
finite field,  permutation polynomial,  cryptography,  transposition,  cycle,  

Full Text: PDF>>
Buy this Article

Polynomials are called permutation polynomials if they induce bijective functions. This paper investigates algebraic properties of permutation polynomials over a finite field, especially properties associated with permutation cycles. A permutation polynomial has a simple structure but good randomness properties suitable for applications. The cycle structure of permutations are considered to be related to randomness. We investigate the algebraic structure from the viewpoint of randomness. First we show the relationship between polynomials and permutations using a matrix equation. Then, we give a general form of a permutation polynomial corresponding to a product C1C2・・・Ck of pairwise disjoint cycles. Finally, permutation polynomials with fixed points -or with 2, 3 and 4-cycles -and their compositions are given together with distribution of degree of the permutation polynomials.