Chapter 14 1. If n = 3713 = pq, and φ(n) = 3588, find p and q.
2. If n = 4386607 = pq, and φ(n) = 4382136, find p and q.
3. If n = 63573413 = pq, and φ(n) = 63557280, find p and q.
4. Can problems like 1, 2, and 3, above, still be easily solved (with technology), if the primes involved are over 100 digits long? Justify your answer. These problems are intended to illustrate why φ(n) must be kept secret.
5. If gcd(C,pq) 1 in RSA, show that you can factor n and hence find d. Show that the probability of gcd(C,pq) 1 is (p + q – 1)/n = 1/p + 1/q – 1/(pq).
6. Suppose Alice uses e = 3 and Bob uses e = 4 and both use the modulus n. If the message M is sent to both Alice and Bob, explain how Eve, having intercepted both copies, can read the message without factoring n.
7. Does your explanation for question 6 still work if Bob changes his e value to 5? Can you modify your answer, so that Eve may still recover the message?
8. The team that factored RSA-576 earned $10,000. Look up two values 1) the number of computing hours the team needed to accomplish this and 2) the minimum wage in 2003. Once you have these figures, multiply them. If the team had to pay the computers for their time, would they have any prize money left over for themselves?
9. Use the Sieve of Eratosthenes to find all primes less than 300.
10. Use Fermat’s method to factor 551.
11. Use Fermat’s method to factor 1617.
12. Use Fermat’s method to factor 12213.
13. Use the fact that 221 = 102 +112 = 142 + 52 to factor 221.
14. Use the fact that 1073 = 72 +322 = 172 + 282 to factor 1073.
15. Can any prime numbers be expressed as the sum of two positive numbers squared?
16. Can any prime numbers be expressed as the sum of two positive numbers squared in more than one way?
17. Fermat number’s were alluded to in this chapter. They are numbers of the form . Fermat incorrectly conjectured that they were all prime. He wasn’t often wrong! Can you determine which is the first Fermat number to be composite? Euler was the first to answer his question. He didn’t use a computer, but you may.
18. In the 1870s, William S. Jevons described in his book The Principles of Science: A Treatise on Logic and Scientific Method how multiplication is easy, but factorization is much harder. He went on to ask
“Can the reader say what two numbers multiplied together will produce the number 8,616,460,799? I think it is unlikely that anyone but myself will ever know.”
Use Fermat’s factorization method (along with a computer program or a spread sheet such as Microsoft Excel) to prove Jevons was wrong.
19. It took F. N. Cole “three years of Sundays” (ending in 1903) to prove that 267 – 1 is not prime by finding the factors.8 Use modern technology and one of the algorithms described above to find the factors yourself.
20. Factor 236273 using Dixon’s algorithm.