Problem Set 4
CSC507/CSC609
Mar 2016

Due: April 6

In the problem set we will use the number RSA-100 and its factors.
See the wiki page https://en.wikipedia.org/wiki/RSA_numbers
for more information on the RSA challenge.

1. p = 37975227936943673922808872755445627854565536638199
   
   In the field Z_p, p given above, use Pohlig-Helman to calculate
   as much as you can of the discrete log.

   I propose that 11 is a generator of Z_p^*. Verify. Show proof that
   11 generates.

   Factor p-1 (you can use Wolfram Alpha) and show what you need to do
   to find the discrete lot of:

   h = 9228088727554456278545655366

   Hint: if g^i = 1 (p) then i|(p-1) and g^{ij}=1 (p) for all j.
   So it suffices to test g^k for all k that are "just below" 
   p-1 in divisibility ordering. That is, all k  such that 
   k = (p-1)/r for a prime r dividing p-1.


2. Implement the extended euclidean algorithm. 

   Find the inverse of h in Z_p and Z_q, where h and p are as above 
   and q is:

   q = 40094690950920881030683735292761468389214899724061


3. Encrypt h (above) mod n, where n = p*q, when encryption is c = h^3 (n).
   Decrypt c by finding the decryption exponent d, and test that
   c^d = h (n).