Kozen D.C. Theory of Computation

Подождите немного. Документ загружается.

Chinese Remaindering 87

Note that each pair in Z

× Z

occurs exactly once. This is because 3 and

5 are relatively prime. Arithmetic is preserved as well: for example, 4 and

7correspondtothepairs(1, 4) and (1, 2), respectively; multiplying these

pairwise gives the pair (1, 3) (modulo 3 and 5, respectively), which occurs

under 13; and 4 × 7=28≡ 13 (mod 15).

Also, σ and σ

−1

are computable in polynomial time. To compute σ(x),

we just reduce x modulo n

,... ,n

. To compute σ

−1

,... ,x

), we ﬁrst

compute, for each 1 ≤ i ≤ k, positive integers s and t such that s(n/n

) −

= 1 and take u

def

= sn/n

. Because n

and n/n

are relatively prime,

the numbers s and t exist and are available as a byproduct of the Euclidean

algorithm (Miscellaneous Exercise 42). For each 1 ≤ i, j ≤ k, u

≡ 1(mod

)andu

≡ 0(modn

), i = j.Then

−1

,... ,x

)=x

+ ···+ x

(mod n).

For further details see [4, pp. 289ﬀ].

A Stronger Version

The Chinese remainder theorem actually holds in a much more general

form. We need this stronger form for Berlekamp’s factoring algorithm in

Lecture D.

Recall from algebra that an ideal of a commutative ring R is a set I

such that

• 0 ∈ I,

• if x, y ∈ I then x + y ∈ I,and

• if x ∈ I and y ∈ R,thenxy ∈ I.

Ideals are the kernels of ring homomorphisms (the set of elements mapped

to 0). It is easy to check that if h : R → R



is a ring homomorphism, then

{x ∈ R | h(x)=0} is an ideal; conversely, if I is an ideal, then there is

a homomorphism []

: R → R/I whose kernel is I. The ring R/I is the

quotient ring consisting of equivalence classes [x]

def

= {y ∈ R | x ≡

y},

where x ≡

y iﬀ x − y ∈ I.

Let us call two ideals relatively prime if the smallest ideal containing

them both is all of R.

For example, in Z, the set of multiples of n ≥ 1 forms an ideal, and it

is the kernel of the ring homomorphism x → x mod n. The quotient ring

is Z

. The ideals generated by m and n in this way are relatively prime as

ideals iﬀ m and n are relatively prime as integers in the usual sense.

88 Supplementary Lecture B

Theorem B.2 Let I

,... ,I

be pairwise relatively prime ideals of commutative ring R,

and let I =



i=1

. There is an isomorphism

R/I

∼

R/I

×···×R/I

given by the map

σ : R/I → R/I

×···×R/I

σ([x]

)

def

=([x]

,... ,[x]

Proof. We must ﬁrst argue that the map σ is well deﬁned on ≡

equivalence classes; that is, the action of σ on [x]

does not depend on

the choice of the representative x. But this is true, because if x ≡

y,then

x ≡

y for 1 ≤ i ≤ k by deﬁnition of I.

It is a routine matter to check that σ is a ring homomorphism. Also, σ

is one-to-one, because if x ≡

y,1≤ i ≤ k,thenx ≡

y. The only diﬃculty

is showing that σ is onto.

To show that σ is onto, by analogy with the proof of Theorem B.1, it

suﬃces to show that for each 1 ≤ i ≤ k there exists x ∈ R such that x ≡

and x ≡

0forj = i. Equivalently, we must show that there exists x ∈ R

such that x − 1 ∈ I

and x ∈



j=i

. Without loss of generality, assume

i =1.

By the assumption of relative primality, for each j ≥ 2 there exist

∈ I

and y

∈ I

such that 1 = x

+ y

(note that the smallest ideal

containing both I and J is the set of sums {x + y | x ∈ I and y ∈ J},

and this ideal is all of R iﬀ it contains 1). Now we proceed by induction.

Suppose we have constructed u

and v

such that

• u

∈ I

• v

∈



j=2

,and

• 1=u

+ v

Let

m+1

def

= x

m+1

+ y

m+1

def

= y

m+1

Then u

m+1

∈ I

, v

m+1

∈



m+1

j=1

,and

m+1

+ v

m+1

= x

m+1

+ y

m+1

+ y

m+1

= x

m+1

+ y

m+1

+ v

)

=1.

When done, we have v

∈



j=2

and v

− 1=u

∈ I

,thusv

is the

desired element. 2

Chinese Remaindering 89

In our application in Lecture D, R is a ring of polynomials over a ﬁnite

ﬁeld.

Supplementary Lecture C

Complexity of Primality Testing

Testing whether a given binary integer is prime was for a long time one of

the few known examples of a problem in NP ∩ co-NP that was not known

to be in P. For many years, this problem was known to be in P only

under the assumption of the extended Riemann hypothesis, an unproved

conjecture of analytic number theory [86]. It was known to be in co-RP via

the Miller–Rabin test [86, 100] (see [75]) and also known to be in RP by

results of Adleman and Huang [1]. In 2002, Agarwal, Kayal, and Saxena

showed that primality testing is in P unconditionally [3]. An improved

probabilistic primality test was given recently by Agrawal and Biswas [2].

For our applications in Lecture 16, it suﬃces to show that the problem

is in NP ∩ co-NP. This was ﬁrst shown by Pratt in 1975 [97]. We give

Pratt’s proof in this lecture (Theorem C.4).

Let PRIMES be the set of binary representations of primes. It is easy

to see that ∼PRIMES, the set of composite numbers,isinNP:guesstwo

nontrivial factors of the given number and multiply them. Thus PRIMES

is in co-NP. It is much harder to show that PRIMES is also in NP.

Pratt’s NP algorithm for primality is based on Fermat’s theorem.If

1 ≤ a ≤ n − 1andthereexistsanm ≥ 1 such that a

≡ 1(modn), then

we deﬁne the order of a modulo n to be the least such m. For example,

the ﬁrst few powers of 3 modulo 10 are 1, 3, 9, 7, 1, therefore the order of

3 modulo 10 is 4. If n is prime, then all numbers in the range 1,... ,n− 1

Complexity of Primality Testing 91

have an order modulo n, but not so if n is composite. For example, all

powers of 5 are 5 modulo 10.

In general, a positive integer a has an order modulo n iﬀ a is relatively

prime to n (that is, if gcd(a, n)=1)iﬀa is invertible modulo n;thatis,

if there exists b,1≤ b ≤ n − 1, such that ab ≡ 1(modn) (Miscellaneous

Exercise 43).

Lemma C.1 (Fermat’s Theorem) Anumberp ≥ 2 is prime if and only if some element

of {1,... ,p− 1} has order p −1 modulo p.

To prove Fermat’s theorem, we need a few basic facts of number theory

and ﬁnite ﬁelds.

Deﬁne

∗

def

= {a | 1 ≤ a ≤ n − 1, gcd(a, n)=1}.

For example, Z

∗

= {1, 3, 7, 9}. Because Z

∗

consists of the invertible el-

ements of Z

, it forms a group under multiplication modulo n.Thisis

known as the group of units modulo n.ThesizeofZ

∗

is denoted ϕ(n). The

function ϕ is known as the Euler ϕ function.

We can calculate ϕ(n) for any n if we know the prime factorization of n.

For a prime power p

, ϕ(p

)=p

k−1

(p −1), because a number is relatively

prime to p

iﬀ it is not a multiple of p,andtherearep

k−1

− 1 multiples

of p in {1,... ,p

−1}. By the Chinese remainder theorem (Theorem B.1),

if m and n are relatively prime, then the map x → (x mod m, x mod n)

is a ring isomorphism Z

→ Z

× Z

, therefore a group isomorphism

∗

→ Z

∗

× Z

∗

,thusϕ(mn)=ϕ(m)ϕ(n). Combining these facts, it

follows that if n = p

···p

is the prime factorization of n,then

ϕ(n)=



i=1

−1

− 1). (C.1)

We must show that for prime p, the group Z

∗

has an element of order

p−1. Because ϕ(p)=p−1 is the size of the whole group Z

∗

, that is the same

as saying that Z

∗

is cyclic; that is, {1, 2,... ,p− 1} = {1,a,a

,... ,a

p−2

}

(modulo p)forsome1≤ a ≤ p − 1.Suchanelementa is called a cyclic

generator of Z

∗

It is actually true that the multiplicative group of any ﬁnite ﬁeld is

cyclic. This is no harder to show for arbitrary ﬁnite ﬁelds than for the

ﬁelds Z

, so that is what we do.

Recall that the characteristic of a ﬁnite ﬁeld F is the smallest number

p such that 1 + ···+1



 

= 0. This must be a prime, because otherwise F

would contain zero divisors. The prime subﬁeld of F is the smallest subﬁeld

of F and is isomorphic to Z

,wherep is the characteristic. The number of

92 Supplementary Lecture C

elements in F must be p

for some k, because F is a vector space over its

prime subﬁeld of some dimension k, therefore is isomorphic (as a vector

space, not as a ﬁeld) to Z

In fact, up to isomorphism there is only one ﬁnite ﬁeld of cardinality

q for each prime power q, and it is called GF

(for the Galois ﬁeld on q

elements). It is not Z

if q is not prime, because Z

has zero divisors.

Write m | n if m divides n.

Lemma C.2 n =



m | n

ϕ(m).

Proof. By induction on the prime factorization of n.Ifn is a prime

power p

,then



m | n

ϕ(m)=



i=0

ϕ(p

)=1+



i=1

− p

i−1

)=p

If n = n

where n

and n

are relatively prime, then



m | n

ϕ(m)=



m | n

ϕ(m)=



ϕ(m



ϕ(m

)ϕ(m

)



ϕ(m

))(



ϕ(m

)) = n

The nonzero elements of GF

are all invertible and thus form a group

∗

of size q −1. Moreover, all elements of GF

∗

have order dividing q −1,

thus all are roots of the polynomial x

q−1

− 1. Because x

q−1

− 1canhave

at most q − 1 roots, that is all of them. Thus



a∈GF

∗

(x − a)=x

q−1

− 1. (C.2)

Let Φ

(x) be the polynomial whose roots are the elements of GF

∗

order k:

(x)

def



a∈GF

∗

order a=k

(x − a).

By (C.2),

q−1

− 1=



k | q−1

(x).

Lemma C.3 For k | q − 1, the degree of Φ

(x) is ϕ(k).

Complexity of Primality Testing 93

Proof. By induction. For k =1,Φ

(x)=x−1 and deg Φ

(x)=1=ϕ(1).

For k>1,

k = deg (x

− 1)

=deg



m | k

(x)



m |k

deg Φ

(x)

= deg Φ

(x)+



m | k

m<k

deg Φ

(x)

= deg Φ

(x)+



m | k

m<k

ϕ(m) induction hypothesis

= deg Φ

(x)+



m |k

ϕ(m) − ϕ(k)

= deg Φ

(x)+k −ϕ(k) Lemma C.2,

therefore deg Φ

(x)=ϕ(k). 2

ProofofLemmaC.1.For any prime power q,therootsofΦ

q−1

(x)are

the cyclic generators of GF

∗

. By Lemma C.3, there are exactly ϕ(q − 1) =

deg Φ

q−1

(x) of them. This number is nonzero for any prime power q ≥ 2,

therefore GF

∗

has a cyclic generator. In the special case q is prime, this

gives a number with order q −1 modulo q.

Conversely, unless n is prime, the number ϕ(n)asdeﬁnedin(C.1)is

strictly less than n − 1. Moreover, any element a ∈{1,... ,n − 1} that

has an order modulo n, being a member of the group Z

∗

,musthaveorder

dividing ϕ(n). 2

Primality Testing

Now we show how to use Fermat’s theorem to get an NP algorithm for

primality.

Theorem C.4 (Pratt [97]) PRIMES ∈ NP ∩ co-NP .

Proof. We have already observed that PRIMES is in co-NP.Toshow

that it is in NP, we perform the following nondeterministic computation

on input p ≥ 2.

1. If p = 2, accept. If p>2andp is even, reject.

94 Supplementary Lecture C

2. Guess the prime factorization of p −1, say p −1=p

···p

. Verify

by multiplication that this equation holds.

3. Guess a ∈{2,... ,p − 1} and verify by modular arithmetic that

p−1

≡ 1(modp).

4. Verify for each 1 ≤ i ≤ m that a

(p−1)/p

≡ 1(modp).

5. Recursively verify that p

,... ,p

are prime.

Steps 3 and 4 together imply that the order of a modulo p is p − 1. Once

we have veriﬁed 3, we know that the order of a exists and must divide

p − 1. This is because if a

≡ 1(modp)anda

≡ 1(modp), then

gcd(k,m)

≡ 1(modp), because by the Euclidean algorithm, there exist

s, t such that gcd(k, m)=sk −tm. Thus if the order of a were strictly less

than p −1, then it would divide (p −1)/q for some prime q dividing p −1,

in which case we would have a

(p−1)/q

≡ 1(modp). The check 4 veriﬁes

that this does not happen.

Step 1 is constant time. Step 2 takes time polynomial in log p.Steps3

and 4 can be performed in time polynomial in log p by repeated squaring

and reducing modulo p. Thus the time taken is polynomial in log p plus the

time taken by the recursive calls in step 5.

To analyze the total time taken by this recursive algorithm, rather than

solving a recurrence relation, it is easier just to look at the whole tree of

recursive calls. Each node in the tree is labeled with the parameter of the

recursive call represented by that node. If a node is labeled q and the

guessed prime factorization of q − 1isq

···q

, then that node has m

children labeled q

,... ,q

. The leaves of the tree are labeled 2. Because 2

is a prime factor of every q −1, every node has at least two children unless

its label is of the form 2

+ 1, in which case it has one child and that child

is a leaf.

One can show inductively that the product of the labels of all the leaves

of a subtree with root label q is at most q. Because the leaves are all

labeled 2, this says that the number of leaves of that subtree is at most

log

q. Moreover, because the tree is at least binary branching except at the

lowest level, one can show inductively that the total number of nodes in any

subtree is at most 3 − 1, where  is the number of leaves in that subtree.

Thus, if p is the label of the root of the entire tree, the total number of

nodes is at most 3 log

p − 1.

Thus the total amount of time taken by the algorithm is the time to per-

form steps 1–4 times the number of nodes in the tree, which is polynomial

in log p. 2

Supplementary Lecture D

Berlekamp’s Algorithm

Here is an eﬃcient probabilistic algorithm due to Berlekamp [13] for factor-

ing a given univariate polynomial over a ﬁnite ﬁeld of large characteristic.

No deterministic polynomial time algorithm is known. However, one can

give an eﬃcient deterministic irreducibility test, and the factorization prob-

lem can be reduced deterministically to the special case in which the given

polynomial is guaranteed to split into linear factors over the prime subﬁeld.

This is an example of a Las Vegas algorithm: the expected running time

is polynomial with a small probability that it may run for longer, but the

answer is guaranteed to be correct. There are also Monte Carlo probabilistic

algorithms, in which the answer is always produced quickly and is very

probably correct, but there is no absolute guarantee of correctness.

For this result, we need a few more basic facts about ﬁnite ﬁelds be-

yond those presented in Supplementary Lecture C. Recall that there exists

a ﬁnite ﬁeld GF

of q elements iﬀ q is a prime power q = p

. The ﬁeld

∼

is the smallest subﬁeld of GF

andiscalledtheprime sub-

ﬁeld of GF

,andp is called the characteristic of GF

. The ﬁeld GF

the unique ﬁeld of q elements, not just up to isomorphism, but absolutely

unique among subﬁelds of a given algebraic closure

of GF

.Thisis

because the elements of GF

are exactly the roots of the polynomial x

−x.

As we observed in Supplementary Lecture C, the nonzero elements all have

order dividing q − 1,thesizeofGF

∗

, thus they are all roots of x

q−1

− 1;

96 Supplementary Lecture D

andthrowingin0givesx

− x.Thus

= {a ∈ GF

| a

= a}.

The ﬁeld GF

is a subﬁeld of GF

iﬀ r is a power of q.Inparticular,GF

and GF

have the same characteristic. For ﬁnite extensions of GF

,thissays

that GF

⊆ GF

iﬀ m divides n. Thus the lattice of ﬁnite extensions

of GF

in GF

is isomorphic to the lattice of nonnegative integers under

divisibility.

The Galois group of the extension GF

: GF

(the group of auto-

morphisms of GF

ﬁxing GF

pointwise) is cyclic and generated by the

automorphism a → a

. Because GF

is unique, the extension is normal

(all automorphisms ﬁx GF

setwise).

Representation

For computational purposes, the ﬁeld GF

for q = p

is usually represented

as a quotient Z

[y]/h of the ring of univariate polynomials with coeﬃcients

in Z

modulo an irreducible polynomial h ∈ Z

[y] of degree k.Thusiff is a

polynomial of degree m with coeﬃcients in GF

, the coeﬃcients of f would

be represented as polynomials in Z

[y] modulo h.Thenf is represented

as an element of Z

[x, y]/h. This representation allows us to perform the

usual ring operations using polynomial arithmetic modulo h.

The Factorization Problem

Let f be a polynomial of degree m, not necessarily irreducible, with coef-

ﬁcients in a ﬁnite ﬁeld GF

of prime characteristic p. As described above,

f is represented as a polynomial in Z

[x, y]/h,whereh is an irreducible

polynomial in Z

[y].

We wish to ﬁnd the irreducible factors of f. We can assume that f

is squarefree (no multiple roots) by taking the gcd of f with its formal

derivative with respect to x, except when the formal derivative vanishes

identically. But in that case, all terms of f have degree a multiple of p,so

f has a nontrivial factorization

f(x)=

m/p



i=0

⎛

⎝

m/p



i=0

q/p

⎞

⎠

Suppose f factors into irreducible factors f

,... ,f

over GF

.Each

[x]/f

is a ﬁnite extension of GF

isomorphic to GF

,wherem

is the degree of f

. Because the f

are pairwise relatively prime, by the