Math 310: Problem set 10

Instructions: This problem set is due Tuesday, November 28, 2006. Your goal is not only to give correct answers but to communicate your ideas well. Make sure you use good English.
  1. The number 708714834137 is the product pq of two primes p and q, with phi(pq)=(p-1)(q-1)=708713126820.
  2. Consider the cubic equation x3-3ax-b=0 in the case that a=2 and b=6. Cardano's solution is to use the identity (u+v)3-3uv(u+v)-(u3+v3) = 0. If you can find u and v such that uv = a and u3+v3 = b, then x=u+v is a solution to the cubic.
  3. Cardano's solution for x3-3ax-b=0 using the identity (u+v)3-3uv(u+v)-(u3+v3) = 0 can be used to solve any cubic. Consider the cubic x3+cx2+dx+e=0. If you substitute x=y-c/3 in for x and simplify, you get an equation of the form y3+fy+g=0 in which the squared term has been eliminated, and which you can thus solve using Cardano's method. If y = n is a solution to y3+fy+g=0, then from x = y - c/3 we get that x = n - c/3 is a solution to the original equation, x3+cx2+dx+e=0.
  4. Here is a message encrypted using the RSA method with a modulus of m = 10 and an encryption exponent of e = 3. Find the decryption exponent d (explain and show how you find it), and decipher the message: 020116168500800201141019030988091403. (Hint: Letters were converted into strings of digits by converting A to 01, B to 02, etc. However, I'm not telling you the block size. What is the biggest possible block size if m = 10? What block size must have been used?)
  5. Answer: Since m=10 and blocks must give distinct elements of Z/mZ, we can't take blocks giving numbers bigger than 9. Thus the block size must be 1. Since phi(10) = phi(2)phi(5) = 1*4 = 4, and since de == 1 (mod phi(m)), we find that d = 3. Thus the string decrypts as follows:
    ciphertext 020116168500800201141019030988091403
    plaintext  080116162500200801141019070922091407, giving numeral encoded letters
    08 01 16 16 25 00 20 08 01 14 10 19 07 09 22 09 14 07 or
    H  A  P  P  Y     T  H  A  N  J  S  G  I  V  I  N  G
    
    (The J instead of a K is a typo on my part...)