$3\mathrm{.}16.$ Looking back at Exercise $3\mathrm{.}10,$ let's suppose that for a given $N,$ the magic box

can produce only one decryption exponent. Equivalently, suppose that an RSA key

pair has been compromised and that the private decryption exponent corresponding

to the public encryption exponent has been discovered. Show how the basic idea in

the Miller$-$Rabin primality test can be applied to use this information to factor $N.$

$3\mathrm{.}10$ for reference

$3\mathrm{.}10.$ A decryption exponent for an RSA public key $(N,e)$ is an integer $d$ with the

property that $a^{de}-=a(modN)$ for all integers a that are relatively prime to $N.$

$($a$)$ Suppose that Eve has a magic box that creates decryption exponents for $(N,e)$

for a fixed modulus $N$ and for a large number of different encryption expo$-$

nents $e.$ Explain how Eve can use her magic box to try to factor $N.$

$($b$)$ Let $N=38749709.$ Eve's magic box tells her that the encryption exponent

$e=10988423$ has decryption exponent $d=16784693$ and that the encryp$-$

tion exponent $e=25910155$ has decryption exponent $d=11514115.$ Use this

information to factor $N.$

$($c$)$ Let $N=225022969.$ Eve's magic box tells her the following three encryp$-$

tion$/$decryption pairs for $N$ :

$(70583995,4911157),(173111957,7346999),(180311381,29597249).$

Use this information to factor $N.$

$($d$)$ Let $N=1291233941.$ Eve's magic box tells her the following three encryp$-$

tion$/$decryption pairs for $N$ :

$(1103927639,76923209),(1022313977,106791263),(387632407,7764043).$

Use this information to factor $N.$