关于算法:MACM-401MATH

MACM 401/MATH 701/MATH 801
Assignment 4, Spring 2019.
Michael Monagan
Due Friday March 8th by 4pm. Hand in to dropoff box 1a outide AQ 4100.
For problems involving Maple calculations and Maple programming, you should submit a printout
of a Maple worksheet of your Maple session.
Late Penalty: 20% for up to 72 hours late. Zero after that.
Note, you may use Maple for all calculations unless asked to do the question by hand.
Question 1: P-adic Lifting (25 marks)
Reference: Section 6.2 and 6.3.
(a) By hand, determine the p-adic representation of the integer u = 116 for p = 5, first using the
positive representation, then using the symmetric representation for Z5.
(b) Theorem 2: Let u, p ∈ Z with p > 2. For simplicity assume p is odd.
there exist unique integers u0, u1, . . . , un?1 such that u = u0 + u1p
Prove uniqueness.
(c) Determine the cube-root, if it exists, of the following polynomials
a(x) = x
6 531x
5 + 94137x
4 5598333x
3 + 4706850x
2 1327500x + 125000,
b(x) = x
6 406 x
5 + 94262 x
4 5598208 x
3 + 4706975 x
2 1327375 x + 125125
using reduction mod 5 and linear p-adic lifting. You will need to derivive the update formula
by modifying the update formula for computing the p
a(x).
Factor the polynomials so you know what the answers are. Express your the answer in the
p-adic representation. To calculate the initial solution u0 =
√3 a mod 5 use any method. Use
Maple to do all the calculations.
Question 2: Hensel lifting (15 marks)
Reference: Section 6.4 and 6.5.
(a) Given
a(x) = x
4 2 x
3 233 x
2 214 x + 85
and image polynomials
u0(x) = x
2 3 x 2 and w0(x) = x
2 + x + 3,
satisfying a ≡ u0 w0 (mod 7), lift the image polynomials using Hensel lifting to find (if there
exist) u and w in Z[x] such that a = uw.
1
(b) Given
b(x) = 48 x
4 22 x
3 + 47 x
2 + 144
and an image polynomials
u0(x) = x
2 + 4 x + 2 and w0 = x
2 + 4 x + 5
satisfying b ≡ 6 u0 w0 (mod 7), lift the image polynomials using Hensel lifting to find (if
there exist) u and w in Z[x] such that b = uw.
Question 3: Determinants (25 marks)
Consider the following 3 by 3 matrix A of polynomials in Z[x] and its determinant d.

P := () -> randpoly(x,degree=2,dense):
A := Matrix(3,3,P);
55 7 x
2 + 22 x 56 94 x
2 + 87 x 97 62 x
2 4 x 82 10 x
2 + 62 x 71 + 80 x
2 75 x 42 7 x
2 40 x 75 50 x
2 + 23 x
d := LinearAlgebraDeterminant;
d := 224262 455486 x
2 + 55203 x 539985 x
4 + 937816 x
3 + 463520 x
6 75964 x
(a) (15 marks) Let A by an n by n matrix of polynomials in Z[x] and let d = det(A). Develop a
modular algorithm for computing d = det(A) ∈ Z[x]. Your algorithm will compute determinants
of A modulo a sequence of primes and apply the CRT. For each prime p it will compute
the determinant in Zp[x] by evaluation and interpolation. In this way we reduce computation
of a determinant of a matrix over Z[x] to many computations of determinants of matrices over
Zp, a field, for which ordinary Gaussian elimination, which does O(n3) arithmetic operations
in Zp, may be used.
You will need bounds for deg d and ||d||∞. Use primes p = [101, 103, 107, …] and use Maple
to do Chinese remaindering. Use x = 1, 2, 3, … for the evaluation points and use Maple for
interpolation. Implement your algorithm in Maple and test it on the above example.
To reduce the coefficients of the polynomials in A modulo p = 7 in Maple use
B := A mod p;
To evaluate the polynomials in B at x = α modulo p in Maple use
C := eval(B,x=alpha) mod p;
To compute the determinant of a matrix C over Zp in Maple use
Det(C) mod p;
2
(b) (10 marks) Suppose A is an n by n matrix over Z[x] and Ai,j =
Pd
k=0 ai,j,kx
k and |ai,j,k| < Bm.
That is A is an n by n matrix of polynomials of degree at most d with coefficients at most m
base B digits long. Assume the primes satisfy B < p < 2B and that arithmetic in Zp costs
O(1). Estimate the time complexity of your algorithm in big O notation as a function of n,
m and d. Make reasonable simplifying assumptions such as n < B and d < B as necessary.
State your assumptions. Also helpful is
ln n! < n ln n for n > 1.
Question 4: A linear x-adic Newton iteration (15 marks).
Let p be an odd prime and let a(x) = a0 +a1x+…+anx
n ∈ Zp[x] with a0 6= 0 and an 6= 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 =p
a(x) ∈ Zp[x] and if so computes u.
(a) Let
u = u0 + u1x + … + uk1x
k1 + ukx k + …
Derive the Newton update formula for uk. Show your working.
(b) Now test your update formula 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, … as you compute them.
Note, one of the polynomials has a √ in Zp[x], the other does not. So you will need to work
out when the algorithm should stop lifting.
Do all calculations in Maple.
a1 = 81 x
6 + 16 x
5 + 24 x
4 + 89 x
3 + 72 x
2 + 41 x + 25
a2 = 81 x
6 + 46 x
5 + 34 x
4 + 19 x
3 + 72 x
2 + 41 x + 25
(c) The update formula requires u0 6= 0. Explain briefly what you should you do if a0 = 0 and
you want to compute p
a(x) ∈ Zp[x] if it exists.