91Ó°ÊÓ

Euler's phi function has many beautiful properties. (a) If \(p\) and \(q\) are distinct primes, how is \(\phi(p q)\) related to \(\phi(p)\) and \(\phi(q)\) ? (b) If \(p\) is prime, what is the value of \(\phi\left(p^{2}\right) ?\) How about \(\phi\left(p^{j}\right) ?\) Prove that your formula for \(\phi\left(p^{3}\right)\) is correct. (Hint. Among the numbers between 0 and \(p^{j}-1\), remove the ones that have a factor of \(p\). The ones that are left are relatively prime to \(p\).) (c) Let \(M\) and \(N\) be integers satisfying \(\operatorname{gcd}(M, N)=1\). Prove the multiplication formula $$ \phi(M N)=\phi(M) \phi(N) $$ (d) Let \(p_{1}, p_{2}, \ldots, p_{r}\) be the distinct primes that divide \(N\). Use your results from (b) and (c) to prove the following formula: (e) Use the formula in \((\mathrm{d})\) to compute the following values of \(\phi(N)\). (i) \(\phi(1728)\). (ii) \(\phi(1575)\). (iii) \(\phi(889056)\) (Hint. \(\left.889056=2^{5} \cdot 3^{4} \cdot 7^{3}\right)\)

Alice publishes her RSA public key: modulus \(N=2038667\) and exponent \(e=103\). (a) Bob wants to send Alice the message \(m=892383\). What ciphertext does Bob send to Alice? (b) Alice knows that her modulus factors into a product of two primes, one of which is \(p=1301\). Find a decryption exponent \(d\) for Alice. (c) Alice receives the ciphertext \(c=317730\) from Bob. Decrypt the message.

Bob's RSA public key has modulus \(N=12191\) and exponent \(e=37\). Alice sends Bob the ciphertext \(c=587\). Unfortunately, Bob has chosen too small a modulus. Help Eve by factoring \(N\) and decrypting Alice's message. (Hint. \(N\) has a factor smaller than 100.)

Use the Miller-Rabin test on each of the following numbers. In each case, either provide a Miller-Rabin witness for the compositeness of \(n\), or conclude that \(n\) is probably prime by providing 10 numbers that are not Miller-Rabin witnesses for \(n\). (a) \(n=1105\). (Yes, 5 divides \(n\), but this is just a warm-up exercise!) (b) \(n=294409\) (c) \(n=294409\) (d) \(n=118901509\) (e) \(n=118901521\) (f) \(n=118901527\) (g) \(n=118915387\)

Use Pollard's \(p-1\) method to factor each of the following numbers. (a) \(n=1739\) (b) \(n=220459\) (c) \(n=48356747\) Be sure to show your work and to indicate which prime factor \(p\) of \(n\) has the property that \(p-1\) is a product of small primes.

Perform the following encryptions and decryptions using the Goldwasser-Micali public key cryptosystem (Table 3.9). (a) Bob's public key is the pair \(N=1842338473\) and \(a=1532411781\). Alice encrypts three bits and sends Bob the ciphertext blocks \(1794677960, \quad 525734818, \quad\) and \(420526487 .\) Decrypt Alice's message using the factorization $$ N=p q=32411 \cdot 56843 . $$ (b) Bob's public key is \(N=3149\) and \(a=2013\). Alice encrypts three bits and sends Bob the ciphertext blocks 2322,719 , and 202 . Unfortunately, Bob used primes that are much too small. Factor \(N\) and decrypt Alice's message. (c) Bob's public key is \(N=781044643\) and \(a=568980706\). Encrypt the three bits \(1,1,0\) using, respectively, the three random values $$ r=705130839, \quad r=631364468, \quad r=67651321 . $$