Answering to that question, I posted several procedures finding minimal polynomials for the elements of finite fields. The best one was the following,

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

It works even with rather large powers of z,

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

DuncanA suggested an interesting idea in that thread that a minimal polynomial of an element b of F can be produced as a product of (x-b_i) where b_i are algebraic conjugates of b in F, which can be obtained in F by repeating usage of the Frobenius map.

The procedure for finding such conjugates can be written as

AConj:=proc(x) local A,i,y;
A:=Array(1..100);
A[1]:=x;
y:=F:-`^`(x,2);
for i from 2 while x<>y do
A[i]:=y;
y:=F:-`^`(y,2);
od;
A[1..i-1]
end:

It is efficient,

CodeTools:-Usage(seq(AConj(F:-`^`(z,k)),k=1..1000)):
memory used=221.40MiB, alloc change=0 bytes, cpu time=1.90s, real time=1.92s

However, expanding the product of (x-b_i) with b_i being such conjugates, takes a rather long time and uses a lot of memory,

minpolGF:=proc(x,y:=_X) 
local i;
Expand(mul(y-eval(F:-ConvertOut(i),_Z=a),i=AConj(x))) mod 2
end;

CodeTools:-Usage(seq(minpolGF(F:-`^`(z,k)),k=1..10)):
memory used=10.59GiB, alloc change=2.62MiB, cpu time=4.67m, real time=4.69m

_______________
Alec Mihailovs, PhD