代做MACM 401/MATH 701、代写R设计、R程序语言代做、代写Maple programming

日期：2019-02-26 09:23

MACM 401/MATH 701/MATH 801

Assignment 3, Spring 2019.

Michael Monagan

Due Monday February 25th at 4pm. Hand in to Dropoff box 1b outside AQ 4100.

Late Penalty: ?20% for up to 48 hours late. Zero after that.

For problems involving Maple calculations and Maple programming, you should submit a printout

of a Maple worksheet of your Maple session.

MATH 801 students should do both questions 4 and 5.

MACM 401 students may do either question 4 or 5. For a 15 mark bonus, you may do both.

Question 1: The Fast Fourier Transform (30 marks)

(a) Let n = 2m and let ω be a primitive n’th root of unity. To apply the FFT recursively, we use

the fact that ω

2

is a primitive m’th root of unity. Prove this.

Also, for p = 97 = 3 × 2

5 + 1, find a primitve 8’th root of unity in Zp. Use the method in

Section 4.8 which first finds a primitive element 1 < α < p ? 1 of Zp.

(b) What is the Fourier Transform for the polynomial a(x) = 1 + x + x

2 + · · · + xn1, i.e., what

is the vector [a(1), a(ω), a(ω2), . . . , a(ωn1)]

(c) Let M(n) be the number of multiplications that the FFT does. A naive implementation of

the algorithm leads to this recurrence:

M(n) = 2M(n/2) + n + 1 for n > 1

with initial value M(1) = 0. In class we said that if we pre-compute the powers ωi for 0 ≤ i ≤ n/2 and store them in an array W, we can save half the multiplications in the FFT

so that

M(n) = 2M(n/2) + n2 for n > 1.

By hand, solve this recurrence and show that M(n) = 12n log2 n.

(d) Using Maple’s rsolve command, solve the following recurrences. Please simplify the output

from rsolve.

(i) T(1) = d, T(n) = 3T(n/2) + cn for n > 1 (Karatsuba),

(ii) M(1) = 0, M(n) = 2M(n/2) + n/2 for n > 1 (optimized FFT) and

(iii) T(1) = 0, T(n) = T(n 1) + (n 1)2

for n > 1 (Gaussian elimination).

(e) Program the FFT in Maple as a recursive procedure. Your Maple procedure should take as

input (n, A, p, ω) where n is a power of 2, A is an array of size n storing the input coefficients

a0, a1, . . . , an1, a prime p and ω a primitive n’th root of unity in Zp. If you want to precompute

an array W = [1, ω, ω2

, . . . , ωn/21

] of the powers of ω to save multiplications you may

do so.

Test your procedure on the following input. Let A = [1, 2, 3, 4, 3, 2, 1, 0], p = 97 and w

be the primitive 8’th root of unity. To check that your output B is correct, verify that

F F T(n, B, p, ω1

) = nA mod p.

1

(f) Let a(x) = x

3 + 3x + 1 and b(x) = 2x

2 + x + 1 be polynomials in Z97[x].

Calculate the product of c(x) = a(x)b(x) using the FFT.

If you could not get your FFT procedure from part (c) to work, use the following one which

computes [a(1), a(ω), . . . , a(ωn1)] using ordinary evaluation.

FourierTransform := proc(n,A,p,omega)

local f,x,i,C,wi;

f := add(A[i]*x^i, i=0..n-1);

C := Array(0..n-1);

wi := 1;

for i from 0 to n-1 do

C[i] := Eval(f,x=wi) mod p;

wi := wi*omega mod p;

od;

return C;

end:

Question 2: The Modular GCD Algorithm (15 marks)

Consider the following pairs of polynomials in Z[x].

a1 = 58 x

4 415 x

3 111 x + 213

b1 = 69 x

3 112 x

2 + 413 x + 113

a2 = x

5 111 x

4 + 112 x

3 + 8 x

2 888 x + 896

b2 = x

5 114 x

4 + 448 x

3 672 x

2 + 669 x 336

a3 = 396 x

5 36 x

4 + 3498 x

3 2532 x

2 + 2844 x 1870

b3 = 156 x

5 + 69 x

4 + 1371 x

3 332 x

2 + 593 x 697

Compute the GCD(ai

, bi) using the modular GCD algorithm. Use primes p = 23, 29, 31, 37, 43, ....

Identify which primes are bad primes and which are unlucky primes.

To compute gcd(φp(a), φp(b)) in Maple, use Gcd(a,b) mod p . Use the Maple commands chrem

for Chinese remaindering, mods to put the coefficients in the symmetric range, and any other Maple

commands that you need.

PLEASE make sure you input the polynomials correctly!

Question 3: Resultants (15 marks)

(a) Calculate the resultant of A = 3x

2 + 3 and B = (x 2)(x + 5) by hand.

Also, calculate the resultant using Maple. See resultant

(b) Let A, B, C be non-constant polynomials in R[x].

Show that res(A, BC) = res(A, B) · res(A, C).

2

(c) Let A, B be two non-zero polynomials in Z[x]. Let A = GAˉ and B = GBˉ where G = gcd(A, B).

Recall that a prime p in the modular gcd algorithm is unlucky iff p|R where R = res(A, ˉ Bˉ) ∈ Z.

Consider the following pair of polynomials from question 2.

Aˉ = 58 x

4 415 x

3 111 x + 213

Bˉ = 69 x

3 112 x

2 + 413 x + 113

Using Maple, compute the resultant R and identify all unlucky primes. For each unlucky

prime p compute Gcd(A, ˉ Bˉ) mod p in Maple to verify that the primes are indeed unlucky.

Question 4: The Chinese remainder theorem in F[y] (15 marks).

Consider the problem of computing GCDs in Zq[y][x], q a prime. If q is large then we can use

evaluation and interpolation for y, i.e., we can evaluate at y = 0, 1, 2, ... and interpolate the coeffi-

cients of the GCD in Zq[y]. If q is small, e.g. q = 2, this will not work as there will be insufficient

evaluation points in Zq. Moreover, y = 0 and y = 1 may be bad or unlucky.

But Zq[y] is a Euclidean domain and there are an infinite number of primes (irreducibles) in

Zq[y] which can play the role of integer primes in the modular GCD algorithm for computing GCDs

in Z[x]. For example, here are the irreducibles in Z2[y] up to degree 4.

y, y + 1, y2 + y + 1, y3 + y + 1, y3 + y

2 + 1, y4 + y + 1, y4 + y

3 + 1, y4 + y

3 + y

2 + y + 1.

To do this we need to solve the Chinese remainder problem in Zq[y].

Theorem: Let F be any field (e.g. Zq) and let m1, m2, . . . , mn and u1, u2, . . . , un be polynomials

in F[y] with deg(mi) > 0 for 1 ≤ i ≤ n. If gcd(mi

, mj ) = 1 for 1 ≤ i < j ≤ n then there

exists a unique polynomial u in F[y] s.t.

(i) u ≡ ui (mod mi) for 1 ≤ i ≤ n and

(ii) u = 0 or deg u < Pn

i=1 deg mi

.

Prove the theorem by modifying the proof of the Chinese remainder theorem for Z to work for

F[y]. Now solve the following Chinese remainder problem: find u ∈ Z2[y] such that

u ≡ y

2

(mod y

3 + y + 1) and u ≡ y

2 + y + 1 (mod y

3 + y

2 + 1).

Note, in the statement of the theorem the congruence relation u ≡ ui (mod mi) means mi

|(u ui)

in F[y]. For the extended Euclidean algorithm in Zq[y], use Maple’s Gcdex(...) mod q command

to compute the required inverse.

Question 5: Multivariate Polynomial Division (15 marks)

In assignment 2 question 2 we were given two polynomials A, B ∈ Z[x1, x2, . . . , xn] with B 6= 0, and

I asked you to give pseudo code for the multivariate division algorithm for dividing A by B. I said

the pseudo code should begin like this

Algorithm DIVIDE(A,B)

Inputs A, B ∈ Z[x1, x2, . . . , xn] satisfying B 6= 0 and n ≥ 0.

Output Q ∈ Z[x1, x2, . . . , xn] s.t. A = BQ or FAIL meaning B does not divide A.

3

For this assignment implement your multivariate division algorithm in Maple as the Maple

procedure DIVIDE(A,B) to divide A by B. Test you program on the following inputs

> A := (6*y^2-5*y*z+z^2)*x^2+(7*y^2*z-3*y*z^2)*x+2*y^2*z^2;

> B := (2*y-z)*x+y*z;

> Q := DIVIDE(A,B);

> Q := DIVIDE(A+x,B);

> Q := DIVIDE(A+2,B);

> C := expand(A*B);

> Q := DIVIDE(C,B);

The following operations will be helpful.

> X := indets(A) union indets(B); # set of all variables

X := {x, y, z}

> var := X[1];

var := x

> degree(B,var);

2

> lcoeff(B,var); # leading coefficient

2y z

I suggest that you get your procedure working with zero variables first, then one variable, then

two variables then three variables. If your procedure is not working you may insert a print(...);

command anywhere in your procedure to print out any value. Also, you may trace the execution

of your procedure by using

> trace(DIVIDE);

Maple will display everything that is computed. To turn tracing off use

> untrace(DIVIDE);