@Carl Love aLGORITHM 14.8 EQUAL-DEGREE SPLITTING :
INPUT A SQUAREFREE MONIC POLYNOMIAL F BELONG TO F_q[x] of degree n>0, where q is an odd prime power, and a divisor d<n of n, so that all irreducible factors of f have degree d.
output: a proper monic factor g belong to F_q[x] of f,or "failure".
1. choose a belong to F_q[x] with deg a<n at radom
if a belong to F_q[x] then return "failure"
2, g_1←gcd(a,f) , if g_1 not equal 1 then return g_1
3. call the repeated squaring in R=F_q[x]/<f> to compute b= a^((q^d-1)/2) rem f
4. g_2←gcd(b-1,f) if (g_2 not euqal 1) and g_2 not euqal f then return g_2 else return "failure".
1. if n=d then return f
2 call the equal-degree splitting algorithm 14.8 with input f and d repeatedly until it return a proper factor g belong to F_q[x] of f
3 call the algorithm recursively with input g and with input f/g return the results of the two recursive calls.