189-346 / 377B: Number Theory

Assignment 2

Due: Friday, January 29.

1-3. Section 2.1, Problem 1, 8, 12.

4. Honors problem: Show that the constant 2.88 of problem 12 can be improved to 1/log((1+sqrt(5))/2) = 2.07808...

5. Section 2.1, Problem 13.

6. Section 3.1, Problem 2. Formulate a similar test using 11 instead of nine.

7. Honors problem: The decimal expansion of the fraction a/b is periodic. Show that the length of this period divides phi(b). Show that there are infinitely many n such that 1/n has a period of length strictly less than phi(n). The question: "Do there exist infinitely many n such that 1/n has a period of length exactly phi(n)?" is related to a famous unsolved problem of number theory. Which one?

8-10. Section 3.2, Problem 10, 11, 24.

11-13. Section 4.1, Problem 2, 6, 11.

14. Section 4.2, Problem 2.

15. According to the RSA cryptography scheme, a message M - described as a string of digits, with the convention that "a" correspond to "01", "b" to "02", ... "z" to "26", and a blank space to "00" - is replaced by its coded version
C = M^b mod n,
where b and n are publicly available, but the factorization of n is kept secret.
Consider the coded message

C = 14572353050570834605889731500015117386453891958889990

encoded with the RSA public key

n = 17025863870545887144908490224619062098783164408077639, b = 5.

Knowing that the prime factorization of N is pq, where

p= 14732265321145317331353282383,

q = 1155685395246619182673033,

find the secret message M.
Caveat: In the course of your calculation, you will need to compute x^y mod z, where x, y and z are all very large. This calculation, done properly, should take a fraction of a second on a PC. If your calculation takes longer than this, it is likely that your machine is first computing the number x^y, (an impossibly huge number, with more digits than could be stored in a computer the size of the universe...) and only then reducing mod z (if it ever gets to that stage, which of course it won't...).