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,
- 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 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.
- Show that from the two equations
uv = a
u3+v3 = b
you can obtain a single equation
(u3)2+c(u3)+d=0. What values
do you get for the coefficients c and d?
- Solve (u3)2+c(u3)+d=0
for u3, 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 x3-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 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,
- In the case of
x3+3x2-3x-11=0, what should you substitute in for x,
as described above, to eliminate the x2 term?
- After making your substitution, you should have a polynomial
in y with no y2 term. What is your polynomial?
[Hint: It should look familiar!]
- Give a solution to x3+3x2-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:
(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?)