test(a)=
{ local(x, y, z);
  for (i=1, 10000,
    z = eval(Str("T", a, "_", i));
    if (poldegree(z) == 1, break); \\ undefined
    x = polgalois(z);
    y = polgalois(poltschirnhaus( poltschirnhaus(z) ));
    print(x, x==y)
  )
}

{
T1_1 = x;

T2_1 = x^2+x+1;

T3_1 = x^3+x^2-2*x-1;
T3_2 = x^3+2;

T4_1 = x^4+x^3+x^2+x+1;
T4_2 = x^4+1;
T4_3 = x^4-2;
T4_4 = x^4+8*x+12;
T4_5 = x^4+x+1;

T5_1 = x^5+x^4-4*x^3-3*x^2+3*x+1;
T5_2 = x^5-5*x+12;
T5_3 = x^5+2;
T5_4 = x^5+20*x+16;
T5_5 = x^5-x+1;

T6_1 = x^6+x^5+x^4+x^3+x^2+x+1;
T6_2 = x^6+108;
T6_3 = x^6+2;
T6_4 = x^6-3*x^2-1;
T6_5 = x^6+3*x^3+3;
T6_6 = x^6-3*x^2+1;
T6_7 = x^6-4*x^2-1;
T6_8 = x^6-3*x^5+6*x^4-7*x^3+2*x^2+x-4;
T6_9 = x^6+2*x^3-2;
T6_10= x^6+6*x^4+2*x^3+9*x^2+6*x-4;
T6_11= x^6+2*x^2+2;
T6_12= x^6-2*x^5-5*x^2-2*x-1;
T6_13= x^6+2*x^4+2*x^3+x^2+2*x+2;
T6_14= x^6-x^5-10*x^4+30*x^3-31*x^2+7*x+9;
T6_15= x^6+24*x-20;
T6_16= x^6+x+1;

T7_1 = x^7+x^6-12*x^5-7*x^4+28*x^3+14*x^2-9*x+1;
T7_2 = x^7+7*x^3+7*x^2+7*x-1;
T7_3 = x^7-14*x^5+56*x^3-56*x+22;
T7_4 = x^7+2;
T7_5 = x^7-7*x^3+14*x^2-7*x+1;
T7_6 = x^7+7*x^4+14*x+3;
T7_7 = x^7+x+1;

T8_50 = x^8-x-1;
T8_49 = x^8-2*x^6-2*x^5-x^4-x^3+4*x^2+4*x-2;
T8_48 = x^8-2*x^6-2*x^5+2*x^4+4*x^2+2;
T8_47 = x^8+x^2+2*x+1;
T8_46 = x^8-4*x^5-9*x^4-16*x^2-12*x+9;
T8_45 = x^8-2*x^6-2*x^5+4*x^3+2*x^2+2;
T8_44 = x^8+x^2-1;
T8_43 = x^8-x^7+7*x^2-x+1;
T8_42 = x^8-2*x^6+2*x^5+3*x^4-2*x^3+x^2+4*x+2;
T8_41 = x^8-4*x^5+3*x^4+16*x^2+12*x+9;
T8_40 = x^8+8*x^6+18*x^4-1;
T8_39 = x^8+x^2+1;
T8_38 = x^8-4*x^6+28;
T8_37 = x^8-4*x^7+28*x^5-21*x^4-70*x^3+189*x^2-173*x+69;
T8_36 = x^8-4*x^7+112*x^4+224*x^3-112*x^2-736*x+536;
T8_35 = x^8+4*x^2-1;
T8_34 = x^8+4*x^7+5*x^6+x^5+x^4-2*x^3-x^2+3*x+2;
T8_33 = x^8-8*x^6+18*x^4-16*x^3-40*x^2+8*x+23;
T8_32 = x^8-8*x^6+18*x^4+4;
T8_31 = x^8+2*x^6+x^4+14;
T8_30 = x^8+4*x^6+4*x^4-2;
T8_29 = x^8+x^4+2*x^2+1;
T8_28 = x^8+4*x^6+2;
T8_27 = x^8+5*x^6+3*x^4-6*x^2-4;
T8_26 = x^8+2*x^4-2;
T8_25 = x^8-x^7+29*x^2+29;
T8_24 = x^8-4*x^2+4;
T8_23 = x^8-8*x^6+12*x^4-12;
T8_22 = x^8+x^4+4;
T8_21 = x^8+2*x^4+4*x^2+2;
T8_20 = x^8+x^6-6*x^4-x^2+1;
T8_19 = x^8+4*x^4+4*x^2+1;
T8_18 = x^8+2*x^6+2*x^2+1;
T8_17 = x^8+2*x^4+2;
T8_16 = x^8+4*x^4+2;
T8_15 = x^8+3;
T8_14 = x^8+2*x^7+4*x^6-2*x^5+2*x^4-2*x^3+4*x^2+2*x+1;
T8_13 = x^8+4*x^6+8*x^4+4;
T8_12 = x^8-22*x^6+135*x^4-150*x^2+1;
T8_11 = x^8+9;
T8_10 = x^8+2*x^6+4*x^4+3*x^2+1;
T8_9  = x^8+4*x^4+1;
T8_8  = x^8-2;
T8_7  = x^8+x^7-28*x^6-7*x^5+70*x^4+7*x^3-28*x^2-x+1;
T8_6  = x^8+2;
T8_5  = x^8-12*x^6+36*x^4-36*x^2+9;
T8_4  = x^8+3*x^4+1;
T8_3  = x^8-x^4+1;
T8_2  = x^8+1;
T8_1  = x^8+x^7-7*x^6-6*x^5+15*x^4+10*x^3-10*x^2-4*x+1;

T9_34 = x^9-x-1;
T9_33 = x^9+27*x-24;
T9_32 = x^9+x^7+2*x^5+4*x^3-x^2+x+1;
T9_31 = x^9-2*x^7-2*x^6-x^5-x^4+4*x^3+5*x^2+4*x+1;
T9_30 = x^9+2*x^5+4*x^4+4*x^3+4*x^2+x+1;
T9_29 = x^9-6*x^6-18*x^5+36*x^4-36*x^3+108*x^2-144*x+48;
T9_28 = x^9-2*x^7-2*x^6-x^5-2*x^4+3*x^2+3*x+1;
T9_27 = x^9-36*x^6-54*x^5+432*x^3+324*x^2-243*x-1152;
T9_26 = x^9-x^7+5*x^6+x^5-2*x^4+4*x^3+3*x^2-x-1;
T9_25 = x^9-9*x^6-9*x^4+24*x^3+9*x^2-9*x+1;
T9_24 = x^9-2*x^6-2*x^3-2;
T9_23 = x^9+9*x^7-60*x^6+72*x^5+354*x^3-495*x^2+2124*x-845;
T9_22 = x^9-12*x^6-27*x^5-18*x^4+9*x^3+36*x-8;
T9_21 = x^9+3*x^6+3*x^3-2;
T9_20 = x^9-2*x^7-2*x^6-2*x^5+x^4+4*x^3+3*x^2+3*x+1;
T9_19 = x^9-3*x^8-24*x^5-24*x^4-48*x+16;
T9_18 = x^9-2*x^6-2*x^3-1;
T9_17 = x^9-17*x^7-6*x^6+87*x^5+47*x^4-143*x^3-69*x^2+72*x+27;
T9_16 = x^9-2*x^7+3*x^6+x^5-x^4-2*x^3+x+1;
T9_15 = x^9-9*x^7-21*x^6+72*x^5+99*x^4-99*x^3-585*x^2+549*x+166;
T9_14 = x^9-30*x^6+45*x^5+126*x^4-240*x^3-90*x^2+405*x+80;
T9_13 = x^9-2*x^6-x^3+1;
T9_12 = x^9+x^8+x^7+4*x^6-2*x^5-x^4+3*x^3+x^2-1;
T9_11 = x^9-x^6+5*x^3+1;
T9_10 = x^9-2;
T9_9  = x^9-3*x^8+3*x^7-15*x^6+33*x^5-3*x^4+24*x^3+6*x^2-4;
T9_8  = x^9-6*x^6+8*x^3-8;
T9_7  = x^9-232*x^7-9*x^6+7485*x^5+8631*x^4-3097*x^3-738*x^2+325*x-27;
T9_6  = x^9+x^8-32*x^7-84*x^6-14*x^5+112*x^4+84*x^3+4*x^2-8*x-1;
T9_5  = x^9+3*x^6+3*x^3-1;
T9_4  = x^9+4*x^6+3*x^3-1;
T9_3  = x^9+9*x^7-6*x^6+27*x^5-36*x^4+27*x^3-54*x^2-32;
T9_2  = x^9-15*x^7+4*x^6+54*x^5-12*x^4-38*x^3+9*x^2+6*x-1;
T9_1  = x^9-9*x^7+27*x^5-30*x^3+9*x-1;

T10_45 = x^10-x-1;
T10_44 = x^10-2*x^8-2*x^7-2*x^3+2*x^2+x-1;
T10_43 = x^10-2*x^8-2*x^7-2*x^6-2*x^5-x^4-2*x^3+3*x^2-2*x+1;
T10_42 = x^10-32*x^5-200*x^2+256;
T10_41 = x^10+2*x^9+4*x^8-x^6+x^4-2*x-1;
T10_40 = x^10+x^9-x^8-x^7-2*x^6+2*x^3+3*x^2+x+1;
T10_39 = x^10-2*x^8-2*x^7-2*x^6-2*x^5+2*x^4-2*x^3+2*x^2-1;
T10_38 = x^10-2*x^8-x^6-2*x^4+2*x^2-2;
T10_37 = x^10-2*x^8-2*x^7-x^6-x^5-x^4-2*x^3-2*x^2+1;
T10_36 = x^10-2*x^8-x^6+3*x^4-x^2+2;
T10_35 = x^10+300*x^6-18*x^5+10000*x^2-200*x+81;
T10_34 = x^10-x^8-2*x^6-x^4+x^2-1;
T10_33 = x^10-2*x^9+12*x^8-20*x^7+66*x^6-20*x^5+228*x^4+84*x^3+276*x^2+120*x+100;
T10_32 = x^10-9*x^8+27*x^6+2*x^5-27*x^4-9*x^3+8*x+1;
T10_31 = x^10-1800*x^8-24000*x^7+1422000*x^6+30960000*x^5-462480000*x^4-14500800000*x^3+12996000000*x^2+2414368000000*x-12197187420489;
T10_30 = x^10+90*x^6-648*x^5+1080*x^4-2160*x^3+3645*x^2+5400*x+12960;
T10_29 = x^10+2*x^8-2*x^6-x^2+2;
T10_28 = x^10-10*x^7+10*x^6+36*x^5+50*x^4-10*x^3-1;
T10_27 = x^10+3*x^6-2*x^5+x^2+2*x+1;
T10_26 = x^10-15*x^8-75*x^6-6*x^5-165*x^4-30*x^3-180*x^2-50*x-90;
T10_25 = x^10-2*x^8-2*x^6-x^2-2;
T10_24 = x^10+x^8-x^4+3*x^2-1;
T10_23 = x^10-2*x^8-x^7+3*x^6+2*x^5-2*x^4-2*x^3+2*x^2+3*x+1;
T10_22 = x^10-2*x^8-2*x^7-x^6+x^4-2*x^3+2*x^2-1;
T10_21 = x^10+x^6-2*x^5-x^4+3*x^2-2*x+1;
T10_20 = x^10-3*x^9+x^8+36*x^7-39*x^6-105*x^5+99*x^4+180*x^3-45*x^2-135*x-45;
T10_19 = x^10-10*x^8+35*x^6-2*x^5-50*x^4+10*x^3+25*x^2-10*x+2;
T10_18 = x^10+60*x^6-240*x^5+850*x^2-5440*x-1088;
T10_17 = x^10-2*x^5-2;
T10_16 = x^10+7*x^8+17*x^6-31*x^4-40*x^2+127;
T10_15 = x^10-x^8-2*x^6+x^4+3*x^2-1;
T10_14 = x^10+x^8-4*x^6-3*x^4+3*x^2+1;
T10_13 = x^10-2*x^8-x^7-2*x^6+x^5+3*x^4-2*x^3-x^2+x+1;
T10_12 = x^10+2*x^9+3*x^8-x^6-2*x^5-x^4+3*x^2+2*x+1;
T10_11 = x^10+10*x^6+25*x^2-8;
T10_10 = x^10-2*x^5-4;
T10_9  = x^10-50*x^8-100*x^7+865*x^6+4036*x^5+4100*x^4+16400*x^2+13120*x+2624;
T10_8  = x^10-4*x^8+2*x^6+5*x^4-2*x^2-1;
T10_7  = x^10-2*x^5-15*x^4-10*x^3-15*x^2-5;
T10_6  = x^10+5*x^8-33*x^7-67*x^6+132*x^5-375*x^4+1551*x^3+5505*x^2-8987*x+4291;
T10_5  = x^10-2;
T10_4  = x^10-x^5-1;
T10_3  = x^10-x^8-x^6+3*x^4+2*x^2+1;
T10_2  = x^10-35*x^6+130*x^4+160;
T10_1  = x^10-x^9+x^8-x^7+x^6-x^5+x^4-x^3+x^2-x+1;

T11_8 = x^11-x-1;
T11_7 = x^11+x^10+2*x^9+2*x^8+x^6-x^5+2*x^4+2*x^3+x^2-1;
T11_6 = x^11-x^10-121*x^9+65*x^8+5345*x^7-481*x^6-96739*x^5-23689*x^4+413690*x^3-493810*x^2+26910*x-856170;
T11_5 = x^11-898*x^9-3080*x^8+293480*x^7+4185984*x^6-145552352*x^5+1474999680*x^4-16923164544*x^3+177410331648*x^2-709199732736*x+63589515264;
T11_4 = x^11-2;
T11_3 = x^11-33*x^9+396*x^7-2079*x^5+4455*x^3-2673*x-243;
T11_2 = x^11-x^10+5*x^8+8*x^5+6*x^4-x^3+x^2+3*x+1;
T11_1 = x^11+x^10-10*x^9-9*x^8+36*x^7+28*x^6-56*x^5-35*x^4+35*x^3+15*x^2-6*x-1;
}

default(realprecision, 38);
default(new_galois_format, 1)
gettime();
for (i = 1, 11, test(i))

default(new_galois_format, 0)
for (i = 1, 7, test(i))

\\ miscellaneous tests
setrand(3);polgalois(x^8-24447832222819253258096747170722821932737551721814653244372785289945042560370884249414339208601850*x^4+24447832222819253258096747170722821932737551721825709426404304862673539625219608619381278993545125*x^2+24447832222819253258096747170722821932737551721825709426404304862673539625219608619381278993545125)

polgalois(polzagier(11,0)/polzagier(1,0))

polgalois(x^8-1864259299553450972214799899167226732549697977945716*x^6+331143259018657601105207922631212331088735421305543663274125986698777318014979969*x^4-2225286541902342283500014249183311190477390*x^2+5)

polgalois(x^8+162644002617632464507038884216211529274267271168000002)

polgalois(x^8+2^2^12)

setrand(5);polgalois(x^8-3911867303938246274330482940384509030446487325649036998411199166662010711465575565062431210085563041214249877058238647352476889609806751307308111079477582030570450*x^4-3911867303938246274330482940384509030446487325649036998411199166662010711465575569485025077906938222890835591100732814736005780908137290944485033156820540880540405*x^2+3911867303938246274330482940384509030446487325649036998411199166662010711465575569485025077906938222890835591100732814736005780908137290944485033156820540880540405)

setrand(15);polgalois(x^8-1642492255488433999638100059165477791152530*x^4-1642492255488433999640965798385546876573045*x^2+1642492255488433999640965798385546876573045)

print("Total time spent: ",gettime);
\q