In this example, minimal polynomials could be found as follows,

alias(a=RootOf(_Z^4+_Z+1)):
minpoly:=x->(Sqrfree(PolynomialTools:-MinimalPolynomial(Expand(x) mod 2,4)) mod 2)[2,1,1]:

For example,

minpoly(a^3);
2 3 4
1 + _X + _X + _X + _X
Expand(eval(%,_X=a^3)) mod 2;
0
minpoly(a^1000000);
2
1 + _X + _X
Expand(eval(%,_X=a^1000000)) mod 2;
0

A more efficient version is

Minpoly:=proc(x,y:=_X)

(Sqrfree(evala(Norm(Expand(y-x) mod 2))) mod 2)[2,1,1]

end:
CodeTools:-Usage(seq(Minpoly(a^k,x),k=1..15)):
memory used=0.91MiB, alloc change=0.69MiB, cpu time=0.03s, real time=0.05s
CodeTools:-Usage(seq(minpoly(a^k),k=1..15)):
memory used=3.09MiB, alloc change=2.75MiB, cpu time=0.06s, real time=0.11s
CodeTools:-Usage(seq(Expand(minpol(k)) mod 2,k=1..15)):
memory used=1.51MiB, alloc change=1.19MiB, cpu time=0.05s, real time=0.06s

It works as

Minpoly(a^2+a, x);
2
x + 1 + x

The following is more efficient,

MinPoly:=proc(x,y:=_X)
local A, i;
A:=Matrix(4,datatype=integer[4]);
for i to 4 do
A[i]:=frontend(PolynomialTools:-CoefficientVector,[Expand(x*a^(i-1)) mod 2,a]) od:
(Sqrfree(LinearAlgebra:-Modular:-CharacteristicPolynomial(2,A,y)) mod 2)[2,1,1]
end:
CodeTools:-Usage(seq(MinPoly(a^k,x),k=1..15));
memory used=369.42KiB, alloc change=255.95KiB, cpu time=0.00s, real time=0.00s

The difference can be seen better in larger examples,

alias(a=RootOf(T^100+T^97+T^96+T^93+T^91+T^89+T^87+T^86+T^82+T^81+T^71+T^70+T^67+T^61+
T^60+T^57+T^54+T^53+T^52+T^49+T^48+T^45+T^44+T^42+T^39+T^36+T^33+T^32+T^31+T^29+T^28+T^27+
T^26+T^24+T^23+T^22+T^18+T^17+T^16+T^14+T^13+T^12+T^10+T^8+T^7+T^6+T^3+T+1)):
MinPoly:=proc(x,y:=_X)
local A, i;
A:=Matrix(100,datatype=integer[4]);
for i to 100 do
A[i]:=frontend(PolynomialTools:-CoefficientVector,[Expand(x*a^(i-1)) mod 2,a]) od:
(Sqrfree(LinearAlgebra:-Modular:-CharacteristicPolynomial(2,A,y)) mod 2)[2,1,1]
end:
CodeTools:-Usage(seq(MinPoly(a^k,x),k=1..1000)):
memory used=1.15GiB, alloc change=28.56MiB, cpu time=50.78s, real time=51.30s
CodeTools:-Usage(seq(Minpoly(a^k,x),k=1..1000)):
memory used=9.21GiB, alloc change=0 bytes, cpu time=14.13m, real time=14.43m

minpoly is not good for such large degrees,

minpoly:=x->(Sqrfree(PolynomialTools:-MinimalPolynomial(Expand(x) mod 2,100)) mod 2)[2,1,1]:
minpoly(a);
18 16 13 8 4 2
_X + _X + _X + _X + _X + _X + _X

which is obviously wrong.

Now, minpol doesn't seem to run in this case, and a modified version of it which I wrote, was slower than MinPoly and used more memory.

Alec Mihailovs

PS MinPoly can be made even more efficient, working directly in GF,

alias(a=RootOf(T^100+T^97+T^96+T^93+T^91+T^89+T^87+T^86+T^82+T^81+T^71+T^70+T^67+T^61+
T^60+T^57+T^54+T^53+T^52+T^49+T^48+T^45+T^44+T^42+T^39+T^36+T^33+T^32+T^31+T^29+T^28+T^27+
T^26+T^24+T^23+T^22+T^18+T^17+T^16+T^14+T^13+T^12+T^10+T^8+T^7+T^6+T^3+T+1)):
F:=GF(2,100,op(a)):
z:=F:-input(2):
MinPolyGF:=proc(x,y:=_X)
local A, i;
A:=Matrix(100,[seq([op(F:-`*`(x,F:-`^`(z,i)))],i=0..99)],datatype=integer[4]);
(Sqrfree(LinearAlgebra:-Modular:-CharacteristicPolynomial(2,A,y)) mod 2)[2,1,1]
end:
CodeTools:-Usage(seq(MinPolyGF(F:-`^`(z,k),x),k=1..1000)):
memory used=0.79GiB, alloc change=27.81MiB, cpu time=19.10s, real time=19.23s

Another advantage in using MinPolyGF is that

n:=(2^100-1)/3:
use F in MinPolyGF(z^n,x) end;
2
x + x + 1

while

MinPoly(a^n,x);
Error, (in mod/Normal/algnum) modp1: degree too large

Alec