# Math 5405. Cryptography, Spring 2013

## Homework Assignments

1. Due Thursday, January 17.

Trappe and Washington, #4, 11, 13, 16, 18, 19, 20, 21, 24, 25 on Pages 104-108.

2. Due Thursday, January 24.

Savin, Page 138 # 1,2, Page 142 # 1,2,3, Page 145 # 1,3, Page 150 # 1,2,3.

3. Due Thursday, January 31.

Savin, Page 150 #4 (and factor these numbers using either the $p-1$ or $p+1$ method),

Page 154 #1, Page 156 #1,2.

4. Due Thursday, February 7.

Savin, Pages 159-60 #1-5.

Trappe-W, Pages 215-16 #4,8,10. Page 217 #4.

5. Due Thursday, February 14.

The next prime year is the year 2017.

5 is a primitive element (mod 2017).

I chose a mystery number x and computed 5^x (mod 2017) and got 1077.

Please find my number in three different ways.

(1) 2017 is not such a big prime, so use baby-step/giant-step to find x.

(2) 2016 has only small prime factors, so use Pohlig-Helmann to find x.

(3) Although it is a pain, use Index Calculus to find discrete logs of 2,3,5,7,11,13 and then find x.

6. Due Thursday, February 28.

Savin, Page 165 #1,2. Page 170 #1,2.`

7. Due Thursday, March 7.

Savin, Page 173 #1,2. Page 175 #1,2.`

8. Due Thursday, March 21.

Savin, Pages 180-181 #1-5.

9. Due Thursday, March 28.

Homework Number Nine

10. Due Thursday, April 18.

Trappe-Washington, Problems 1-3 on Pages 314-315.
Also the following two programming problems.

A. Given input of two integers n and m, return either:

(i) The gcd(m,n) if the gcd is different from 1, or:

(ii) The inverse of m (mod n) if the gcd is equal to 1.

Your output should make it clear which of the two has occurred.

B. Given input of three integers: (b,c,n)
and a pair of ordered pairs (x1,y1) and (x2,y2)

(i) Determine whether the two points are on the elliptic curve y^2 = x^3 + bx + c (mod n)

(ii) If they are on the elliptic curve, either:

(iia) Add them to get a third point, or else

(iib) Explain that they cannot be added and return the reason why.

11. Due at the Final Exam on May 1, 2013.

Trappe-Washington, Problems 2-4 on Page 446, and:

Programming Assignment.

Input a natural number n.

A. Check n for primality using the Miller-Rabin test.

If it is probably (99% sure) to be prime, return "Government Prime."
Otherwise.

B. Factor n using the Lenstra algorithm. Return the factors.

## Supplementary Notes

155 South 1400 East, Room 233, Salt Lake City, UT 84112-0090, T:+1 801 581 6851, F:+1 801 581 4148