Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Math 5405, Exam 2

1. A shift key is created using the Diffie-Hellman method with primitive root g = 7 modulo p = 2011. The numbers exchanged over a public channel are X = 1323 and Y = 1307. Find the shift key k, where 1 ≤ k ≤ p _ 1.          Taking k mod 26, decipher

SVARFGNEG.

(The above was obtained by shifting k steps forward in the circle A i_→ B i_→ C i_→ ... i_→ Z i_→ A)

2. Which of the following are Miller-Rabin witnesses that 133 is composite?

(i) a = 10       (ii) a = 11       (iii) a = 12

3.  Set n = 1729 = 7 x 13 x 19, which is a Carmichael number. Using Fermat’s Little Theorem, prove that each element a e (Z/n)x satisfies

a(n_1)/2 三 1 mod n.

Find a Carmichael number that does not have this property.

4. Determine the number of elements of the group (Z/1729)x . Of these elements, how many are Solovay-Strassen witnesses that 1729 is composite?

5. Using the quadratic sieve method, factor n = 46698343. List only the congruences that you use to construct x2 三 y2 mod n.

An RSA cipher has modulus n and encryption key e = 17. Use your factorization to decode the message

29034923.

Express the final answer in terms of the nine letter alphabet from Savin’s notes, namely:

6. Consider the elliptic curve y2 = x3 + 1 over the rational numbers. Determine, by hand, the order of P = (0, 1) and of Q = (2, 3).

7. Using python, compute the order ofP = (2, 3) on y2 = x3 +7x _ 13 mod 101. Is this elliptic curve group cyclic?

8. In an elliptic curve Diffie-Hellman key exchange, Alice and Bob agree on the curve y2 = x3 + 7x _ 13 mod 101, and on the point P = (2, 3).

Alice chooses a secret integer x and sends the point xP = (17, 75) to Bob, while Bob chooses a secret integer y and sends the point yP = (50, 81) to Alice. Find x or y, and their shared secret, namely the point xyP.

9. The integer n = 618240007109027021 is a product of two primes. Determine these using elliptic curve factor-

ization with P = (8, _24) on y2 = x3 + x2 . State the smallest k such that computing k!P yields a factor. Explain (in a sentence or two) how this relates to HW 4, Problem 2.

10. The integer n = 34547647 is a product of two primes, p and q. Determine these using elliptic curve factorization with P = (2, 3) on y2 = x3 + 2x _ 3. State the smallest k such that computing k!P yields a factor of n.                Compute the order of P on the elliptic curve modulo p and modulo q.