MACM 401/MATH 801/CMPT 891 Assignment 5, Spring 2021.
Michael Monagan
Due Monday March 29th at 11pm.
Late Penalty: −20% for up to 48 hours late. Zero after that.
Question 1: Factorization in Zp[x] (20 marks)
(a) Factor the following polynomials over Z11 using the Cantor-Zassenhaus algorithm.
a1 =x4+8×2+6x+8,
a2 = x6 +3×5 −x4 +2×3 −3x+3,
a3 = x8 +x7 +x6 +2×4 +5×3 +2×2 +8.
Use Maple to do all polynomial arithmetic, that is, you can use the Gcd(…) mod p and Powmod(…) mod p commands etc., but not Factor(…) mod p.
(b) Compute the square-roots of the integers a = 3, 5, 7 in the integers modulo p, if they exist, for p = 1020 + 129 = 100000000000000000129 by factoring the polynomial x2 − a in Zp[x] using the Cantor-Zassenhaus algorithm. Show your working. You will have to use Powmod here.
Question 2: Factorization in Z[x] (25 marks) Factor the following polynomials in Z[x].
a1 =x10 −6×4 +3×2 +13
a2 =8×7 +12×6 +22×5 +25×4 +84×3 +110×2 +54x+9
a3 =9×7 +6×6 −12×5 +14×4 +15×3 +2×2 −3x+14
a4 =x11 +2×10 +3×9 −10×8 −x7 −2×6 +16×4 +26×3 +4×2 +51x−170
For each polynomial, first compute its square free factorization. You may use the Maple command gcd(…) to do this. Now factor each non-linear square-free factor as follows. Use the Maple command Factor(…) mod p to factor the square-free factors over Zp modulo the primes p = 13,17,19,23. From this information, determine whether each polynomial is irreducible over Z or not. If not irreducible, try to discover what the irreducible factors are by considering combinations of the modular factors and Chinese remaindering (if necessary) and trial division over Z.
Using Chinese remaindering here is not efficient in general. Why?
Thus for the polynomial a4, use Hensel lifting instead; using a prime of your choice from 13, 17, 19, 23, Hensel lift each factor mod p, then determine the irreducible factorization of a4 over Z.
1
Question 3: The linear x-adic Newton iteration (15 marks) Letpbeaprimeanda∈Zp[x]havedegreed≥0. Letu=√aandsupposeu∈Zp[x]. Thenfor
α ∈ Z we may write
u=u0 +u1(x−α)+···+uk(x−α)k +···+ud/2(x−α)d/2
where u0 = a(α). On assignment 4 you derived the following update formula for determining uk given u(k) = k−1 ui(x − α)i:
i=0
uk = ek (2u0)−1 mod(x−α)whereek =a−u(k)2.
(x−α)k
Ifa=d0aixi anda0 ̸=0thenwecanuseα=0sincea(0)=a0 sou0 =√a0 ̸=0. Thenthe update formula simplifies: the quantity ek/xk mod x is just the coefficient of xk of ek. Here is my Maple code for implementing the algorithm for a0 ̸= 0.
XadicSqrt := proc(a,x::name,p::prime)
# Input a(x) in Zp[x]
# Output sqrt(a) if it is in Zp[x] else FAIL
local a0,u0,u,i,k,d,m,e,uk;
if a=0 then return 0; fi;
d := degree(a,x);
if irem(d,2) <> 0 then return FAIL fi;
a0 := coeff(a,x,0);
if a0 = 0 then error “not implemented”; fi;
u0 := numtheory[msqrt](a0,p);
if u0 = FAIL then return FAIL; fi;
i := modp(1/2/u0,p);
u := u0;
e := Expand( a-u^2 ) mod p;
for k from 1 to d/2 do
uk := coeff(e,x,k)*i mod p;
u := u + uk*x^k;
e := Expand( a-u^2 ) mod p;
od;
if e = 0 then u else FAIL fi;
end:
The algorithm is correct but not efficient. Let us find out why and then fix it. Let deg a = d and let T(d) be the number of arithmetic operations algorithm XadicLift does in Zp. Assuming the polynomial multiplication u2 uses a classical quadratic algorithm, show that T(d) is cubic in d. You are to modify the computation of the error so that that T(d) ∈ O(d2). You must show that T(d) ∈ O(d2). Implement your modified algorithm in Maple – just modify my code appropriately. Finally make your Maple code work for inputs where a0 = 0. Test your code on the following inputs for p = 11.
a=(9×3 +3×2 +5x+6)2, a=x3 +(9×3 +3×2 +5x+6)2, a=(9×3 +3×2 +5x)2.
Hint: The error ek+1 = a − (u(k+1))2 = a − (u(k) + ukxk)2. Use the error ek = a − u(k)2 from the previous iteration to calculate ek+1 faster.
2
Question 4 (10 marks): Integration and Differentiation in Maple
(a) You were probably taught that the derivative of tan x is sec2 x. Differentiate tan x in Maple. Now use Maple to show that Maple’s answer equals sec2 x.
(b) Evaluate the following antiderivatives in Maple.
ln(x) 2−x
(2x+tanx)dx x dx xe dx.
(c) Evaluate the following definite integrals in Maple where the parameters r and λ are positive. π r2 2 ∞ −λx
sinxdx r −xdx and
0 −r 0
λe dx. You will need to tell Maple that r > 0 and λ > 0. See ?assume
Question 5 (15 marks): Symbolic Integration
Implement a Maple procedure INT (you may use Int if you prefer) that evaluates antiderivatives f(x)dx. For a constant c and positive integer n your Maple procedure should apply
cdx = cx.
cf(x) dx → c f(x) dx.
f (x) + g(x) dx → f (x) dx + −1 c
x
g(x) dx.
1 c+1
dx=lnx andforc̸=1 x dx=c+1x .
ex dx = ex and ln x dx = x ln x − x. n x n x n−1 x
x e dx → x e − nx e dx. n xn xn+1
x lnxdx=n+1lnx−(n+1)2.
You may ignore the constant of integration. NOTE: ex in Maple is exp(x), i.e. it’s a function not a power. HINT: use the diff command for differentiation to determine if a Maple expression is a constant wrt x. Test your program on the following.
> INT( x^2 + 2*x + 1, x );
> INT( x^(-1) + 2*x^(-2) + 3*x^(-1/2), x );
> INT( exp(x) + ln(x) + sin(x), x );
> INT( 2*f(x) + 3*y*x/2 + 3*ln(2), x );
> INT( x^2*exp(x) + 2*x*exp(x), x );
> INT( 4*x^3*ln(x), x );
> INT( 2*exp(-x) + ln(2*x+1), x );
3