Harbourne's Math 310 Problem set 10

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.

The number 708714834137 is the product pq of two primes p and q, with phi(pq)=(p-1)(q-1)=708713126820.
- Given pq and (p-1)(q-1), show how to find p+q, and determine p+q if pq and (p-1)(q-1) are as given above.
- Given pq and p+q, show how to find p and q, and thereby find a factorization of 708714834137.
Consider the cubic equation x³-3ax-b=0 in the case that a=2 and b=6. Cardano's solution is to use the identity (u+v)³-3uv(u+v)-(u³+v³) = 0. If you can find u and v such that uv = a and u³+v³ = b, then x=u+v is a solution to the cubic.
- Show that from the two equations
```
uv = a
u³+v³ = b
```
  you can obtain a single equation (u³)²+c(u³)+d=0. What values do you get for the coefficients c and d?
- Solve (u³)²+c(u³)+d=0 for u³, then get u by taking cube roots, and get v from uv = a. What solution x=u+v does this give you? Verify your solution by plugging it into x³-6x-6. What value do you get? (Due to round-off error, it shouldn't be zero, but it should be close.)
Cardano's solution for x³-3ax-b=0 using the identity (u+v)³-3uv(u+v)-(u³+v³) = 0 can be used to solve any cubic. Consider the cubic x³+cx²+dx+e=0. If you substitute x=y-c/3 in for x and simplify, you get an equation of the form y³+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 y³+fy+g=0, then from x = y - c/3 we get that x = n - c/3 is a solution to the original equation, x³+cx²+dx+e=0.
- In the case of x³+3x²-3x-11=0, what should you substitute in for x, as described above, to eliminate the x² term?
- After making your substitution, you should have a polynomial in y with no y² term. What is your polynomial? [Hint: It should look familiar!]
- Give a solution to x³+3x²-3x-11=0.
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?)