18.310 Second Examination: due Monday November 25 20002

you may use notes; if stuck you may ask questions via email.

ask if you see what appear to be misprints.

1. State and prove the '5 color theorem' in your own words.

2. Suppose someone is using an RSA code with N=9060019 and encoding power z=1459141

a. encode the message 1234567

b. factor N (by the tortoise and hare)

c find the inverse power to use to decode

d decode back to 1234567 and decode the encoded message 1234567.

3. Set up 16fft spreadsheets mod 197 and mod 97 and use them to multiply numbers. Could you use these moduli for a 32fft?

Use them to multiply 12345678 by 987654321.

4. Here is a linear program:

x₁ - 2x₂ - 3x₃ + x₄ = -1

2x₁ + x₂ + x₃ + x₄ <= 3

x₁ + 2x₂ +x₃ - 2x₄ <=-1

Maximize x₁ + x₃ +x₄

All x variables non-negative.

a. state the dual problem

b. introduce a new variable to make the new origin feasible

c find a solution by pivoting

d deduce the dual solution from it.

5. Do one of the following:

a. set up a spreadsheet to do the magical determinant finding for 5 by 5 matrices. It should be capable of finding the determinant of any 5 by 5 matrix. (to avoid dividing by 0 you should add some tiny quantity to each matrix element-eg add (10^(-8))*sin(i+j) to the ij-th element.)

b. describe the quadratic sieve method of factoring in your own words

c describe the elliptic curve method of factoring in your own words

(in your own words means that the wording should not too closely resemble what appears in the notes or anywhere else.)

you may do more parts of 5 for extra credit.