Script started on Thu Mar 27 17:10:45 1997
bash$ maple
    |\^/|     Maple V Release 3 (University of Toronto)
._|\|   |/|_. Copyright (c) 1981-1994 by Waterloo Maple Software and the
 \  MAPLE  /  University of Waterloo. All rights reserved. Maple and Maple V
 <____ ____>  are registered trademarks of Waterloo Maple Software.
      |       Type ? for help.
> read(`ddfedf`);

                    Distinct Degree Factorization, example 1

                                     p := 5

                          6      5      4      3      2
                    f := x  + 4 x  + 4 x  + 3 x  + 3 x  + 4

                                     5    3      2
                         f_prime := x  + x  + 4 x  + x

               Gcd(f,f_prime) mod p is , 1,  so f is square-free

                       f_1 := Gcd(f,x^p-x) mod p =, x + 1

                                           5      4    3      2
         f_rest := Quo(f,f_1,x) mod p = , x  + 3 x  + x  + 2 x  + x + 4

                                                      2
               f_2 := Gcd(f_rest,x^(p^2)-x) mod p =, x  + 3 x + 4

                                                      3
               f_rest := Quo(f_rest,f_2,x) mod p = , x  + 2 x + 1

                                                      3
               f_3 := Gcd(f_rest,x^(p^3)-x) mod p =, x  + 2 x + 1

                     f_rest := Quo(f_rest,f_3,x) mod p = , 1

                                                2              3
     Maple says:  Factor(f) mod p is, (x + 1) (x  + 3 x + 4) (x  + 2 x + 1)

                                     -----

                    Distinct Degree Factorization, example 2

                                     p := 5

                             5    4      3      2
                       f := x  + x  + 2 x  + 3 x  + x + 2

                                        3    2
                          f_prime := 4 x  + x  + x + 1

               Gcd(f,f_prime) mod p is , 1,  so f is square-free

                                               3      2
                 f_1 := Gcd(f,x^p-x) mod p =, x  + 4 x  + x + 4

                                                    2
                  f_rest := Quo(f,f_1,x) mod p = , x  + 2 x + 3

                                                      2
               f_2 := Gcd(f_rest,x^(p^2)-x) mod p =, x  + 2 x + 3

                     f_rest := Quo(f_rest,f_2,x) mod p = , 1

                                                               2
    Maple says:  Factor(f) mod p is, (x + 2) (x + 4) (x + 3) (x  + 2 x + 3)

                                    -------

                                                  3      2
              Equal Degree Factorization of f_1, x  + 4 x  + x + 4

                       A random polynomial:  v1 := 3*x+ 1

                          Gcd(f_1, v1) mod p is , x + 2

                    Gcd(f_1, v1^((p-1)/2)+1) mod p is , x + 3

                    Gcd(f_1, v1^((p-1)/2)-1) mod p is , x + 4

                That was too good to be true!  Let's try another

                    Another random polynomial:  v2 := 4*x+1

                                 v2 := 4 x + 1

                          Gcd(f_1, v2) mod p is , x + 4

                    Gcd(f_1, v2^((p-1)/2)+1) mod p is , x + 2

                    Gcd(f_1, v2^((p-1)/2)-1) mod p is , x + 3

                That was too good to be true!  Let's try another

                    Another random polynomial:  v2 := 5*x+9

                                    v3 := 4

                            Gcd(f_1, v3) mod p is , 1

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

                                                   3      2
              Gcd(f_1, v3^((p-1)/2)-1) mod p is , x  + 4 x  + x + 4

                       That was awful!  Let's try another

                    Another random polynomial:  v4 := 2*x+6

                                 v4 := 2 x + 1

                          Gcd(f_1, v4) mod p is , x + 3

                                                      2
                 Gcd(f_1, v4^((p-1)/2)+1) mod p is , x  + x + 3

                      Gcd(f_1, v4^((p-1)/2)-1) mod p is , 1

> quit;
bytes used=582536, alloc=262096, time=0.32
bash$ exit
exit

script done on Thu Mar 27 17:10:55 1997