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
