Problem 5:   Number theory review

1. Express 1 as a linear combination of 2058 and 1019. What is 1019⁻¹ modulo 2058?
2. Calculate 2⁵⁴⁹ mod 29.
3. Compute gcd(6188,4709).
4. Show that 1234 and 357 are relatively prime. Find the multiplicative inverse of 357 in \Z₁₂₃₄.

Problem 6:   Number theory on computer

1. Use Erathostenes's Sieve to count the exact number of primes less than one million. What is the estimate given by the Prime Number Theorem for this number? What is the relative error of the estimate?
2. Get a ball-park figure of the time it takes to generate 1024-bit (308 decimal digits) and 2048-bit RSA keys on a modern PC by implementing RSA key generation using ln3 or any other big number package. Submit both the answer to this question and also the documented code that you wrote.

Problem 7:   RSA: Theory and Practice

1. (With pen) My toy RSA key is N=187, e=107. You observe a ciphertext c=5. What is the plaintext?
2. (With computer) Consider this RSA key
   

   N : 120457322460183418712065226069810172366048205604752299621042894 397706979004293595855337673954215374262637794524272045818217908 229478526584500478161639581465312338385782996541477205027111304 594623121868092711384962797824273219760781441239953781771300913 279928933475049007570476508440103847289002242478256388909. e : 108320892662862955596302357470782070713553067937889499942447147 355968656694359903462867764882012512073853365701549521606511348 714104172770325051335157387268754815037274565436944534867153132 292684133742464029214648540750182171588972138378036750055446438 698076297078027248274182711872974326076429438507794270951.

   Suppose you manage to obtain the decryption key
   

   d : 870778041505896784929057064247111975431088041103712624121674096 250991494449208495397081617394569729997785285908978755792242047 951504608606471891232362973145723219036260087876400092012690445 506827289066083911176383869641400399764707038140971639114758576 80395636175986539382761142627308502128595895319836883991.

   Factor N. (These numbers will be placed in the file /c/cs467/assignments/ps2/rsakeys.txt on the Zoo so that you don't need to copy them by hand.)