MATH 701/MATH 801代做、代写Java，c/c++语言、代做Maple programming

日期：2019-03-07 09:56

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 := LinearAlgebra[Determinant](A);

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.