Systematic Generation of An Irreducible Polynomial of an Arbitrary Degree m over Fp Such That p ≫ m
Hiroaki Nasu, Yasuyuki Nogami, Yoshitaka Morikawa, Shigeki Kobayashi, Tatsuo Sugimura · 2008
This paper proposes a method for generating an irreducible polynomial of an arbitrary degree m over an arbitrary prime field Fpsuch that p > m. The proposed method is closely related to the minimal polynomial determination and therefore it has the following features: its complexity has little dependency on the size of characteristic p, its calculation cost is explicitly given with degree m, and it can generate primitive polynomials when pm- 1 is factorized as the product of prime numbers. The restriction p > m comes from using Newtonpsilas formula.