MACM 401/MATH 701/MATH 801 Assignment 5, Spring 2023.
Michael Monagan
Due Monday March 27th at 11pm.
Late Penalty: −20% for up to 24 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.
程序代写 CS代考 加QQ: 749389476
Question 3: A linear x-adic Newton iteration (15 marks).
Let p be an odd prime and let a(x) = a0 +a1x+…+anxn ∈ Zp[x] with a0 ̸= 0 and an ̸= 0. Suppose √a0 = ±u0 mod p. The goal of this question is to design an x-adic Newton iteration algorithm that given u0, determines if u = a(x) ∈ Zp[x] and if so computes u. Let
u=u0 +u1x+…+uk−1xk−1 +…+un−1xn−1.
(a) Derive the Newton update formula for uk given u(k). Show your working.
(b) Now implement your algorithm in Maple and test it on the two polynomials a1(x) and a2(x) below using p = 101 and u0 = +5. Please print out the sequence of values of u0,u1,u2,… that your program computes. Note, one of the polynomials has a √ in Zp[x], the other does not.
a1 =81×6 +16×5 +24×4 +89×3 +72×2 +41x+25 a2 =81×6 +46×5 +34×4 +19×3 +72×2 +41x+25
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 constants a,b,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
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+1 xn+1
x lnxdx=n+1lnx−(n+1)2. ax+b 1ax+b 1
e dx= ae and ax+bdx=ln|ax+b|/a.
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(-2*x) + 2/(3*x+1), x );
CS Help, Email: tutorcs@163.com