9
\$\begingroup\$

Objective

Given a prime number \$p\$ and an integer \$n \geq 2\$, find a degree-\$n\$ primitive polynomial modulo \$p\$.

Mathematical explanation

When we perform "modular arithmetic" over some prime number \$p\$, addition, subtraction, and multiplication are well-defined. Here, every pair \$a, b\$ of integers is considered to be equal if and only if there exists an integer \$N\$ such that \$a - b = Np\$ holds. So for example, when \$p = 11\$, it holds that \$4 \times 6 = 24 = 24 - 2 \times 11 = 2\$.

We can perform modular arithmetic over the set of polynomials over \$x\$ with integer coefficients as well, by considering modulo up to some prime number \$p\$ and some irreducible polynomial \$P\$ over \$x\$ with degree \$2\$ or more.

It should be noted that the irreducibility of \$P\$ depends on \$p\$. For example, though \$x^2 + 1\$ is irreducible over integers, it is reducible modulo \$2\$ because \$x^2 + 1 = x^2 + 2x + 1 = (x + 1)^2\$.

Finally, the degree-\$n\$ polynomial \$P\$ over \$x\$ is said to be primitive modulo \$p\$ if, up to modulo \$p\$ and \$P(x)\$, \$x^m\$ equals to \$1\$ only when the integer \$m\$ equals to \$0\$ up to modulo \$p^n - 1\$. It should be noted that the existence of such \$P\$ isn't unique for the given \$n\$.

I/O format

The outputted polynomial \$P\$ shall have integer coefficients that are at least \$0\$ and less than \$p\$. It's not required to have leading coefficient of \$1\$.

Otherwise flexible.

Examples

Input p, Input n, possible Output

2, 2, x^2 + x + 1
2, 3, x^3 + x + 1
2, 4, x^4 + x + 1
3, 2, x^2 + x + 2
3, 3, x^3 + 2x + 1

Notable non-example

Though \$x^2 + 1\$ is irreducible modulo \$3\$, it is not primitive because: $$ x^4 = x^4 + x^2 + 1 = x^2(x^2 + 1) + 1 = 1 $$ and \$4 \neq 0\$ up to modulo \$3^2 - 1 = 8\$.

Improve this question
\$\endgroup\$
2
  • \$\begingroup\$ Related. \$\endgroup\$ Commented Nov 11, 2025 at 6:22
  • \$\begingroup\$ For the last example, can't you write \$ x^4 = x^4 + x^2+1 = x^2(x^2 + 1) + 1 = 1 \$? \$\endgroup\$ Commented Nov 11, 2025 at 8:35

4 Answers 4

Reset to default
7
\$\begingroup\$

Wolfram Language (Mathematica), 46 20 bytes

Thanks to att for pointing out a huge bytes savings!

#2&@@FiniteField@##&

The inevitable builtin (not implemented in tio.run unfortunately). In Mathematica, FiniteField[p,n] is the setting in which the described arithmetic modulo p and a primitive degree-n polynomial takes place. Mathematica computes a primitive polynomial of degree n internally to implement this setting, so we just have to coax it into revealing the polynomial’s identity using #2&@@ (which returns the second part of the field’s internal representation).

Previous code, obtaining the polynomial the way the language intended (but way longer):

FiniteField@##~Information~"FieldIrreducible"&
Improve this answer
\$\endgroup\$
1
  • 3
    \$\begingroup\$ I believe #2&@@FiniteField@##& should work \$\endgroup\$ Commented Nov 13, 2025 at 7:33
4
\$\begingroup\$

Wolfram Language (Mathematica), 123 bytes

(While[Count[PolynomialMod[x^#,P,Modulus->p]&/@Divisors[(p=#)^#2-1],1]!=1,P=x^#2+RandomInteger[p-1,#2].x^Range[0,#2-1]];P)&

Try it online!

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

PARI/GP, 46 bytes

f(p,n)=minpoly(ffprimroot(ffgen(ffinit(p,n))))

Attempt This Online!

Using built-ins related to finite fields.

PARI/GP, 82 bytes

f(p,n,i)=while(sumdiv(p^n-1,d,Mod(x,q=Mod(Pol(digits(p^n+i,p)),p))^d==1)!=1,i++);q

Attempt This Online!

Without built-ins.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Maple, 227 bytes

proc(p,n)N:=Q->Nextprime(Q,x)mod p;P:=x^n;e:=N(P);G:=GF(p,n,e);r:=G:-ConvertOut~(select(G:-isPrimitiveElement,{seq(G:-input(i),i=0..p^n-1)}));do P:=N(P);R:=RootOf(e);until map2(op,1,{subs(R=x,Roots(P,R)mod p)[]})subset r;P;end;

proc(p,n)
N:=Q->Nextprime(Q,x)mod p; # function to find next irreducible poly mod p
P:=x^n;                    # start with degree n polynomials
e:=N(P);                   # find an irred degree n polynomial
G:=GF(p,n,e);              # to use as field extension in defining the field
R:=RootOf(e);              # field extension form for Roots command below
# next line goes through all field elements and finds the primitive elements
r:=G:-ConvertOut~(select(G:-isPrimitiveElement,{seq(G:-input(i),i=0..p^n-1)}));
do
  P:=N(P);                 # find next irreducible polynomial
  # next line tests if the roots of P are primitive elements
until map2(op,1,{subs(R=x,Roots(P,R)mod p)[]})subset r;
P;                         # output polynomial
end;

Searches through the irreducible polynomials of degree n for one whose roots are primitive elements.

Unfortunately Maple has two ways of representing finite fields, the GF module form has a test for primitive elements but doesn't find polynomial roots; the other form does roots but doesn't test for primitive elements. So many bytes are wasted converting between the two forms.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Unlike Mathematica, the polynomial extension used is irreducible but not necessarily primitive, otherwise (p,n)->GF(p,n):-extension would work. \$\endgroup\$ Commented Nov 13, 2025 at 5:44

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.