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...).