# Section 10.1 # # Thm 10.1: Some example of the polynomials x^p - x over Z/(p). # for i to 3 do p := ithprime(i); print(p,Factor(x^p-x) mod p); od: ######################################################################## # # Thm 10.2: An example of the polynomial x^(p^d) - x over Z/(p). # # Consider p = 3 and d = 4. # Factor(x^(3^4)-x) mod 3; # We know that x^(3^4) - x is the product of all irreducible of # degree 1, 2 and 4. From inspecting the factorization above we # can see that there are 18 irreducibles of degree 4 over Z/(3)[x]. ######################################################################## # # But note that we can directly enumerate the number of distinct # irreducibles of degree d over Z/(p), without factoring. # # Question: How many distinct irreducibles of degree i are there over Z/(3) # for i = 1,2,3,4? # # Derivation: # # Let ki be the number of distinct irreducibles of degree i over Z/(3). # Then we can set up a system of linear equations. # sys := {degree(x^3-x,x) = k1*1, # 1 divisible by 1 degree(x^(3^2)-x,x) = k1*1 + k2*2, # 2 divisible by 1, 2 degree(x^(3^3)-x,x) = k1*1 + k3*3, # 3 divisible by 1, 3 degree(x^(3^4)-x,x) = k1*1 + k2*2 + k4*4}: # 4 divisible by 1, 2, 4 vars := {k1,k2,k3,k4}; sys; solve(sys,vars); ######################################################################## # # As an aside, it is easy to derive the following function. In Maple, # "option remember" stores the results of previous function calls so they # don't need to be recomputed (or manually stored in a table like # dynamic programming). # # Input: p - a prime # d - an integer in Z_{>=1} # # Output: the number of distinct irreducibles of degree d over Z/(p)[x] # foo := proc(p,d) option remember; local i,c; if d=1 then return p fi; # the degree of x^p - x # compute sum of degrees of all irreducibles in x^(p^d) - x of deg < d c := 0; for i to d-1 do # degree i # no. of irred. of degree i if modp(d,i)=0 then c := c + i * foo(p,i) fi od; return iquo(p^d - c,d); end: foo(3,4); # # Some more checks that foo is correct: # degree(x^(5^4) - x,x) = foo(5,1)*1 + foo(5,2)*2 + foo(5,4)*4; degree(x^(17^26) - x,x) = foo(17,1)*1 + foo(17,2)*2 + foo(17,26)*26; ######################################################################## # # A key computational tool (for efficiency) that is used in the factoring # algorithm is binary powering modulo another polynomial. This is # algorithm "RepeatedSquaring" in the script. # # One possible implementation is in the posted example "mypowmod.mpl". # # This operation is important enough that Maple has a built-in function # for it, namely Powmod. # # Here is an example of an application of Powmod. # # Generate a rather large degree random polynomial with many factors # modulo 3. # f := mul(Randpoly(i,x)^i mod 3,i=1..60): f := Expand(f) mod 3: # # Let's not print out f! But do look at its degree. # degree(f,x); # # Compute the product of all irreducibles of degree 1 that divide f. # (One copy of each). # g1 := Gcd(x^3-x,f) mod 3; # # Check that f1 has only linear factors: # Factor(g1) mod 3; # # To obtain all irreducibles of f of degree 1 (with multiplicity) we # can compute the gcd of f with a high power of (x^3 - x). Since # a linear factor can divide f at most deg f times, it suffices to compute # g1_with_multiplicities := Gcd((x^3-x)^degree(f,x),f) mod 3: Factor(%) mod 3; # # Instead of first computing (x^3 - x)^degree(f,x) and then taking the # gcd, it is more efficient (polynomial time vs. exponential time!) to # compute Rem((x^3-x)^degree(f,x),f) using repeated squaring and then # take the gcd: # Gcd(Powmod((x^3-x),degree(f,x),f,x), f) mod 3: Factor(%) mod 3; # # The above idea is used in the posted example "DDFact.mpl" which gives # a function to compute the distinct degree factorization of the # the squarefree part of f (even if f itself is not squarefree). # Note: To improve the efficiency of that routine the computation # g^ceil(n/i) should be replaced with the appropriate call to Powmod. ######################################################################### # # Section 10.2 # # Let us first illustrate Thm 10.3. # # We know that R = Z/(p) for p a prime is finite field with p element, # in particular it is simply the set {0,1,...,p-1} with addition and # multiplication modulo p. # # The first part of Thm 10.3 states that if h is an irreducible of # degree d then R[x]/ is finite field with p^d elements. # # As an example, consider p = 3 (so R = Z/(3)) and d = 2. # h := x^2 + 1; # irred. of degree 2 over Z/(3) # # Then RR = R[x]/ is a finite field with p^d = 3^2 = 9 elements. # The elements of RR is all polynomials over R[x] of degree # strictly less than 2 (i.e., the distinct polynomials of R[x] modulo h). # RR := {seq(seq(i*x + j,i=0..2),j=0..2)}; # # Addition/subtraction in R is just addition/subtraction modulo 3. # Multiplication is done modulo h, e.g., the product of (x+2) * (2*x+1) is # Rem((x+2)*(2*x+1),h,x) mod 3; # # The second part of Thm 10.3 should be familiar from our study # of the Chinese remainder theorem, and algorithm such as multi-modular # reduction. ######################################################################### # # Now consider Thm 10.4. # # First consider a prime Z/(p). The theorem says that any nonzero # element of Z/(p), when raised to the power (p-1)/2, will be equal # to 1 or -1, with exactly half equal to 1. Some experimental # confirmation of the theorem. # for i to 5 do p := ithprime(i); S := [seq(a,a=1..p-1)]; # nonzero elements of Z/(p) R := map(a->mods(a^((p-1)/2),p),S); print(p,S,R); od: # # Obviously, if we select an element of {1,2,...,p-1} uniformly # at random, then with probably 1/2 it will be a quadratic residue # and with probability 1-1/2=1/2 it will not be a non-quadratic residue. # ######################################################################### # # Now let's give an illustration of the equal degree factorization # on page 4 of the script. Let R = Z/(p), p = 10000019. # p := 10000019; d := 2; h1 := x^2+2090578*x+4297752: # irred. of degree 2 h2 := x^2+4958404*x+3788058: # irred. of degree 2 f := Expand(h1*h2) mod p; # # Our goal is to factor f over R[x]. (Pretend we don't know h1 and h2.) # # The residue class ring # # R/ \equiv R/

x R/

(*) # # contains (p)^2 elements, of which (p-1)^2 are relatively prime to f. (Why?) # # Four of the elements that are relatively prime to f are # S = { (1,1),(1,-1),(-1,1),(-1,-1) }: our goal is to uniformly and randomly # select one of these four elements. # On the left hand side of (*) the elements of S corresond to {e1,e2,e2,e4}: # Gcdex(h1,h2,x,'s','t') mod p; e1 := Rem((1)*s*h1 + (1)*t*h2,f,x) mod p; e2 := Rem((-1)*s*h1 + (1)*t*h2,f,x) mod p; e3 := Rem((1)*s*h1 + (-1)*t*h2,f,x) mod p; e4 := Rem((-1)*s*h1 + (-1)*t*h2,f,x) mod p; # # Note that subtracting (1,1) from the elements in S gives the set # { (0,0), (0,-2), (-2,0), (-2,-2) }: some of these (in this case # two) have the nice property that they "split" the polynomial f: # Gcd(e1-1,f) mod p; # should give us f (useless) Gcd(e2-1,f) mod p; # should give us h1 (great!) Gcd(e3-1,f) mod p; # should give us h2 (great!) Gcd(e4-1,f) mod p; # should give us 1 (useless) # # Our goal is to select an element from {e1,e2,e2,e4) uniformly at random. # To do so, we make use of Thm 10.4. # First choose a random polynomial of degree < 4. # u := Randpoly(4,x) mod p; # returns a random polynomial of degree 4 u := u - lcoeff(u,x)*x^4; # now we have a random polynomial of degree < 4 # # We can check that u is relatively prime to f using Gcd. # Gcd(f,u) mod p; # # [Excercise: What is the chance that our u is not relatively prime to f?] # [Question: What if u is not realtively prime to f? Is this bad?] # # Assume now that u is relatively prime to f. # Use Powmod to raise u to the power (p^d-1)/2. # uu := Powmod(u,(p^2-1)/2,f,x) mod p; # # Then we must have uu in {e1,e2,e2,e4}. # Let's try to take the gdd of uu - 1 with f: # Gcd(uu-1,f) mod p; # # Unlucky! Try again. # uu := Powmod(u,(p^2-1)/2,f,x) mod p; Gcd(uu-1,f) mod p; # # Now we have split f.