## 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
^{3}-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)-(u^{3}+v^{3}) = 0.
If you can find u and v such that uv = a and
u^{3}+v^{3} = b, then x=u+v is a solution to the cubic.
- Show that from the two equations
uv = a
u^{3}+v^{3} = b

you can obtain a single equation
(u^{3})^{2}+c(u^{3})+d=0. What values
do you get for the coefficients c and d?
- Solve (u
^{3})^{2}+c(u^{3})+d=0
for u^{3}, 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^{3}-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
^{3}-3ax-b=0 using the identity
(u+v)^{3}-3uv(u+v)-(u^{3}+v^{3}) = 0 can be used to
solve *any* cubic. Consider the cubic
x^{3}+cx^{2}+dx+e=0. If you substitute
x=y-c/3 in for x and simplify, you get an equation of the form
y^{3}+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^{3}+fy+g=0, then from x = y - c/3 we get
that x = n - c/3 is a solution to the original equation,
x^{3}+cx^{2}+dx+e=0.
- In the case of
x
^{3}+3x^{2}-3x-11=0, what should you substitute in for x,
as described above, to eliminate the x^{2} term?
- After making your substitution, you should have a polynomial
in y with no y
^{2} term. What is your polynomial?
[Hint: It should look familiar!]
- Give a solution to x
^{3}+3x^{2}-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?)