# Tutorial for March 27, 1997.
# Distinct degree factorization and equal degree factorization.


# Distinct degree factorization, mod 5.

#f := sort(expand((x+1)*(x+2)*(2*x^4+2*x+1)*(x^2+1) mod p)) mod p;
#f := sort(expand((x+2)*(x^4+x+1)*(x+1) mod p)) mod p;
#f := sort(expand((x+2)*(x+4)*(x+1) mod p)) mod p;
#f := sort(expand((x+1)*(x^2+3))) mod p;

# This has one degree 1 irreducible factor, one degree 2 irreducible factor,
# and one degree 3 irreducible factor.
print(`Distinct Degree Factorization, example 1`);
p:=5;
f := sort(expand((x+1)*(x^2+3*x+4)*(x^3+2*x+1) mod p)) mod p;
f_prime := sort(expand(diff(f,x))) mod p;
print(`Gcd(f,f_prime) mod p is `, sort(expand(Gcd(f,f_prime) mod p)mod p),` so f is square-free`);

print(` f_1 := Gcd(f,x^p-x) mod p =`, Gcd(f,x^p-x) mod p);
f_1 := Gcd(f,x^p-x) mod p:
print(` f_rest := Quo(f,f_1,x) mod p = `,Quo(f,f_1,x) mod p);
f_rest := Quo(f,f_1,x) mod p:

print(` f_2 := Gcd(f_rest,x^(p^2)-x) mod p =`, Gcd(f_rest,x^(p^2)-x) mod p);
f_2 := Gcd(f_rest,x^(p^2)-x) mod p:
print(` f_rest := Quo(f_rest,f_2,x) mod p = `,Quo(f_rest,f_2,x) mod p);
f_rest := Quo(f_rest,f_2,x) mod p:

print(` f_3 := Gcd(f_rest,x^(p^3)-x) mod p =`, Gcd(f_rest,x^(p^3)-x) mod p);
f_3 := Gcd(f_rest,x^(p^3)-x) mod p:
print(` f_rest := Quo(f_rest,f_3,x) mod p = `,Quo(f_rest,f_3,x) mod p);
f_rest := Quo(f_rest,f_3,x) mod p:

print(`Maple says:  Factor(f) mod p is`, Factor(f) mod p);


print(`-----`);
print(`Distinct Degree Factorization, example 2`);
# This has three degree 1 irreducible factors, and one degree 2 irreducible
# factor.

p:=5;
f := sort(expand((x+2)*(x+4)*(x+3)*(x^2+2*x+3) mod p)) mod p;
f_prime := sort(expand(diff(f,x))) mod p;
print(`Gcd(f,f_prime) mod p is `, sort(expand(Gcd(f,f_prime) mod p)mod p),` so f is square-free`);

print(` f_1 := Gcd(f,x^p-x) mod p =`, Gcd(f,x^p-x) mod p);
f_1 := Gcd(f,x^p-x) mod p:
print(` f_rest := Quo(f,f_1,x) mod p = `,Quo(f,f_1,x) mod p);
f_rest := Quo(f,f_1,x) mod p:

print(` f_2 := Gcd(f_rest,x^(p^2)-x) mod p =`, Gcd(f_rest,x^(p^2)-x) mod p);
f_2 := Gcd(f_rest,x^(p^2)-x) mod p:
print(` f_rest := Quo(f_rest,f_2,x) mod p = `,Quo(f_rest,f_2,x) mod p);
f_rest := Quo(f_rest,f_2,x) mod p:


print(`Maple says:  Factor(f) mod p is`, Factor(f) mod p);


print(`-------`);
print(`Equal Degree Factorization of f_1`,f_1);

# Coefficients of the "random" polynomials are the successive digits of pi:
#      31415926
print(`A random polynomial:  v1 := 3*x+ 1`);
v1 := 3*x + 1:

print(` Gcd(f_1, v1) mod p is `, Gcd(f_1, v1) mod p);
print(` Gcd(f_1, v1^((p-1)/2)+1) mod p is `, Gcd(f_1, v1^((p-1)/2)+1) mod p);
print(` Gcd(f_1, v1^((p-1)/2)-1) mod p is `, Gcd(f_1, v1^((p-1)/2)-1) mod p);

print(`That was too good to be true!  Let's try another`);
print(`Another random polynomial:  v2 := 4*x+1`);
v2 := 4*x+1;

print(` Gcd(f_1, v2) mod p is `, Gcd(f_1, v2) mod p);
print(` Gcd(f_1, v2^((p-1)/2)+1) mod p is `, Gcd(f_1, v2^((p-1)/2)+1) mod p);
print(` Gcd(f_1, v2^((p-1)/2)-1) mod p is `, Gcd(f_1, v2^((p-1)/2)-1) mod p);

print(`That was too good to be true!  Let's try another`);
print(`Another random polynomial:  v2 := 5*x+9`);
v3 := 5*x+9 mod 5;

print(` Gcd(f_1, v3) mod p is `, Gcd(f_1, v3) mod p);
print(` Gcd(f_1, v3^((p-1)/2)+1) mod p is `, Gcd(f_1, v3^((p-1)/2)+1) mod p);
print(` Gcd(f_1, v3^((p-1)/2)-1) mod p is `, Gcd(f_1, v3^((p-1)/2)-1) mod p);

print(`That was awful!  Let's try another`);
print(`Another random polynomial:  v4 := 2*x+6`);
v4 := 2*x+6 mod 5;

print(` Gcd(f_1, v4) mod p is `, Gcd(f_1, v4) mod p);
print(` Gcd(f_1, v4^((p-1)/2)+1) mod p is `, Gcd(f_1, v4^((p-1)/2)+1) mod p);
print(` Gcd(f_1, v4^((p-1)/2)-1) mod p is `, Gcd(f_1, v4^((p-1)/2)-1) mod p);