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