Exercise 18.19. State and re-work the analog of Exercise 3.38 for R[X],

assuming that R is a ¬eld of odd characteristic.

Exercise 18.20. State and re-work the analog of Exercise 3.40 for R[X].

Assume that 2R ∈ R— .

The next two exercises develop a useful technique known as Kronecker

substitution.

Exercise 18.21. Let E := R[X]. Let a, b ∈ E[Y] with a = m’1 ai Yi and

i=0

m’1 i , where each a and b is a polynomial in X of degree less

b= i=0 bi Y i i

than k. The product c := ab ∈ E[Y] may be written c = 2m’2 ci Yi , where

i=0

each ci is a polynomial in X. Show how to compute c, given a and b, using

O(M (km)) operations in R. Hint: for an appropriately chosen integer t > 0,

¬rst convert a, b to a, ˜ ∈ R[X], where a := m’1 ai Xti and ˜ := m’1 bi Xti ;

˜b ˜ b

i=0 i=0

next, compute c := a˜ ∈ R[X]; ¬nally, “read o¬” the values ci from the

˜ ˜b

coe¬cients of c.˜

Exercise 18.22. Assume that -bit integers can be multiplied in time

¯ ¯

M ( ), where M is a well-behaved complexity function. Let a, b ∈ Z[X] with

a = m’1 ai Xi and b = m’1 bi Xi , where each ai and bi is a non-negative

i=0 i=0

integer, strictly less than 2k . The product c := ab ∈ Z[X] may be written

c = 2m’2 ci Xi , where each ci is a non-negative integer. Show how to com-

i=0

¯

pute c, given a and b, using O(M ((k + len(m))m)) operations in R. Hint:

for an appropriately chosen integer t > 0, ¬rst convert a, b to a, ˜ ∈ Z, where

˜b

m’1 m’1

ti and ˜ := ti ; next, compute c := a˜ ∈ Z; ¬nally,

a := i=0 ai 2

˜ b i=0 bi 2 ˜ ˜b

“read o¬” the values ci from the bits of c. ˜

The following exercises develop an important algorithm for multiplying

polynomials in almost-linear time. For integer n ≥ 0, let us call ω ∈ R a

n’1

primitive 2n th root of unity if n ≥ 1 and ω 2 = ’1R , or n = 0 and

ω = 1R ; if 2R = 0R , then in particular, ω has multiplicative order 2n . For

n ≥ 0, and ω ∈ R a primitive 2n th root of unity, let us de¬ne the R-linear

n n

map En,ω : R—2 ’ R—2 that sends the vector (g0 , . . . , g2n ’1 ) to the vector

n

(g(1R ), g(ω), . . . , g(ω 2 ’1 )), where g := 2 ’1 gi Xi ∈ R[X].

n

i=0

Exercise 18.23. Suppose 2R ∈ R— and ω ∈ R is a primitive 2n th root of

unity.

(a) Let k be any integer, and consider gcd(k, 2n ), which must be of the

18.6 Faster polynomial arithmetic (—) 417

form 2m for some m = 0, . . . , n. Show that ω k is a primitive 2n’m th

root of unity.

(b) Show that if n ≥ 1, then ω ’ 1R ∈ R— .

(c) Show that ω k ’ 1R ∈ R— for all integers k ≡ 0 (mod 2n ).

(d) Show that for any integer k, we have

2n ’1

2n if k ≡ 0 (mod 2n ),

ki R

ω =

0R if k ≡ 0 (mod 2n ).

i=0

n

(e) Let M2 be the 2-multiplication map on R—2 , which is a bijective,

R-linear map. Show that

n

En,ω —¦ En,ω’1 = M2 = En,ω’1 —¦ En,ω ,

’n

and conclude that En,ω is bijective, with M2 —¦En,ω’1 being its inverse.

Hint: write down the matrices representing the maps En,ω and En,ω’1 .

Exercise 18.24. This exercise develops a fast algorithm, called the fast

Fourier transform or FFT, for computing the function En,ω . This is

a recursive algorithm FFT (n, ω; g0 , . . . , g2n ’1 ) that takes as inputs integer

n ≥ 0, a primitive 2n th root of unity ω ∈ R, and elements g0 , . . . , g2n ’1 ∈ R,

and runs as follows:

if n = 0 then

return g0

else

(±0 , . . . , ±2n’1 ’1 ) ← FFT (n ’ 1, ω 2 ; g0 , g2 , . . . , g2n ’2 )

(β0 , . . . , β2n’1 ’1 ) ← FFT (n ’ 1, ω 2 ; g1 , g3 , . . . , g2n ’1 )

for i ← 0 to 2n’1 ’ 1 do

γi ← ±i + βi ω i , γi+2n’1 ← ±i ’ βi ω i

return (γ0 , . . . , γ2n ’1 )

Show that this algorithm correctly computes En,ω (g0 , . . . , g2n ’1 ) using

O(2n n) operations in R.

Exercise 18.25. Assume 2R ∈ R— . Suppose that we are given two polyno-

mials a, b ∈ R[X] of length at most , along with a primitive 2n th root of unity

n

ω ∈ R, where 2 ¤ 2n < 4 . Let us “pad” a and b, writing a = 2 ’1 ai Xi i=0

n

and b = 2 ’1 bi Xi , where ai and bi are zero for i ≥ . Show that the follow-

i=0

ing algorithm correctly computes the product of a and b using O( len( ))

operations in R:

418 Polynomial arithmetic and applications

(±0 , . . . , ±2n ’1 ) ← FFT (n, ω; a0 , . . . , a2n ’1 )

(β0 , . . . , β2n ’1 ) ← FFT (n, ω; b0 , . . . , b2n ’1 )

(γ0 , . . . , γ2n ’1 ) ← (±0 β0 , . . . , ±2n ’1 β2n ’1 )

(c0 , . . . , c2n ’1 ) ← 2’n FFT (n, ω ’1 ; γ0 , . . . , γ2n ’1 )

R

2 ’2 i

output i=0 ci X

Also, argue more carefully that the algorithm performs O( len( )) addi-

tions/subtractions in R, O( len( )) multiplications in R by powers of ω,

and O( ) other multiplications in R.

Exercise 18.26. Assume 2R ∈ R— . In this exercise, we use the FFT to

develop an algorithm that multiplies polynomials over R of length at most

using O( len( )β ) operations in R, where β is a constant. Unlike as in

the previous exercise, we do not assume that R contains any particular

primitive roots of unity; rather, the algorithm will create them “out of thin

air.” Suppose that a, b ∈ R[X] are of length at most . Set k := /2 ,

m’1 m’1

ki and b = ki , where

m := /k . We may write a = i=0 ai X i=0 bi X

the ai and bi are polynomials of length at most k. Let n be the integer

n’1

determined by 2m ¤ 2n < 4m. Let f := X2 + 1R ∈ R[X], E := R[X]/(f ),

and ω := [X]f ∈ E.

(a) Show that ω is a primitive 2n th root of unity in E, and that given an

element δ ∈ E and an integer i between 0 and 2n ’1, we can compute

δω i ∈ E using O( 1/2 ) operations in R.

(b) Let a := m’1 [ai ]f Yi ∈ E[Y] and ¯ := m’1 [bi ]f Yi ∈ E[Y]. Using

¯ b

i=0 i=0

the FFT (over E), show how to compute c := a¯ ∈ E[Y] by computing

¯ ¯b

O( 1/2 ) products in R[X] of polynomials of length O( 1/2 ), along with

O( len( )) additional operations in R.

(c) Show how to compute the coe¬cients of c := ab ∈ R[X] from the

value c ∈ E[Y] computed in part (b), using O( ) operations in R.

¯

(d) Based on parts (a)“(c), we obtain a recursive multiplication algo-

rithm: on inputs of length at most , it performs at most ±0 len( )

operations in R, and calls itself recursively on at most ±1 1/2 sub-

problems, each of length at most ±2 1/2 ; here, ±0 , ±1 and ±2 are

constants. If we just perform one level of recursion, and immediately