How do I find primitive polynomials for n > 16?

I use matlabs primpoly(n,'all') to find masks for Galois LFSR random number generators. But the primpoly function tops out at n=16. Is there an equivalent function for arbitrarily large n?

Answer 1

[Sam Chak]

Hi @arthur

The documentation for the function primpoly() indicates that the max degree is 16. You may consider using another function, gfprimfd(), although I have encountered difficulties generating all the primitive polynomials in the forum, even when n is 16. It is possible that my machine is inefficient for generating the entire possible sequence ().

However, I doubt whether any computational software can effectively generate primitive polynomials for arbitrarily large values of n. Even the well-known Mersenne Twister (aka MT19937) is limited to generating up to . You can find the algorithm shared by @Peter Perkins in the File Exchange.

n       = 5;                    % primitive polynomial degree
pr_all1 = primpoly(n, "all")    % primitive polynomial for Galois field(2^n)

 
Primitive polynomial(s) = 
 
D^5+D^2+1
D^5+D^3+1
D^5+D^3+D^2+D^1+1
D^5+D^4+D^2+D^1+1
D^5+D^4+D^3+D^1+1
D^5+D^4+D^3+D^2+1

pr_all1 = 6×1

37 41 47 55 59 61

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

p       = 2;                    % prime number
pr_all2 = gfprimfd(n, "all", p) % primitive polynomial for Galois field(p^n)

pr_all2 = 6×6

1 0 1 0 0 1 1 0 0 1 0 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>