For each of the given values of N = pq and (p 1)(q 1), use the method described in Remark 3.10 to determine p and q.

(a) N =pq=352717 and (p1)(q1)=351520.

(b) N = pq = 77083921 and (p 1)(q 1) = 77066212.

(c) N = pq = 109404161 and (p 1)(q 1) = 109380612.

(d) N = pq = 172205490419 and (p 1)(q 1) = 172204660344.

Remark 3.10. Bob's public key includes the number N pa, which is a product of two secret primes p and q. Proposition 3.4 says that if Eve knows the value of (p -1)(q -1), then she can solve ace E c (mod N), and thus can decrypt messages sent to Bob Expanding (p -1)(g 1 gives (p 1) (g-1) pg -p-g 1 N- (p q) 1 (3.5) Bob has published the value of N, so Eve already knows N. Thus if Eve can determine the value of the sum p+ q, then (3.5) gives her the value of (p-1)(q 10, which enables her to decrypt messages. In fact, if Eve knows the values of p q and pa, then it is easy for her to compute the values of p and g. She simply uses the quadratic formula to find the roots of the polynomial since this polynomial factors as (X p)(X-g), so its roots are p and q. Thus once Bob publishes the value of N pa, it is no easier for Eve to find the value of (p -1)(q -1) than it is for her to find p and q themselves. We illustrate with an example. Suppose that Eve knows that