For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Algebraic Properties of Permutation Polynomials
Eiji OKAMOTO Wayne AITKEN George Robert BLAKLEY
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1996/04/25
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>>
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.