Primitive Polynomial Generation Algorithms Implementation and Performance Analysis
N.R. Saxena, Edward J. McCluskey · 2004
Performance analysis of two algorithms, MatrixPower and FactorPowe r, that generate all ϕ (2 r -1)/ r degree- r primitive polynomials ( ϕ is the Euler’s totient function) is presented. MatrixPower generates each new degree- r primitive polynomial in O( r 4 ) ~ O( r 4 ln r ) time. FactorPower generates each new degree- r primitive polynomial in O( r 4 ) ~ O( k r 4 ln r ) time, where k is the number of distinct prime factors of 2 r -1. Both MatrixPower and FactorPower require O( r 2 ) storage. Complexity analysis of generating primitive polynomials is presented. This work augments previously published list of primitive polynomials and provides a fast computational framework to search for primitive polynomials with special properties.