What to expect

Cover Some Material

Show an Example

Describe an exercise

1. Solve the following equations:
   • $(192,105) + (17,56)$
   • $(47, 71) + (117,141)$
   • $(143, 98) + (76, 66)$
2. Write a unit test for the __add__ method

Use Jupyter to Solve

Do this again

Finite Fields

• Finite set of numbers
• Closed under $+, -, \times, \div$ except division by 0
• Used with Elliptic Curves for Cryptography
• Prime fields are the most interesting

Example

Addition and Subtraction

$F_{19}$

$11 + 6 = 17 \pmod{19}$

$17 - 6 = 11 \pmod{19}$

$18 + 14 = 3 \pmod{19}$

$4 - 12 = 11 \pmod{19}$

Example

print((11 + 6) % 19) # 17

print((17 - 6) % 19) # 11

print((18 + 14) % 19) # 3

print((4 - 12) % 19) # 11

Exercise 1, 2 and 3

1. Solve these equations in $F_{31}$
• $2 + 15 = ?$
• $17 + 21 = ?$
• $29 - 4 = ?$
• $15 - 30 = ?$
2. Write the __add__ method
3. Write the __sub__ method

Multiplication and Exponentiation

$F_{19}$

$2 \times 4 = 8 \pmod{19}$

$7 \times 3 = 2 \pmod{19}$

$11^{3} = 1 \pmod{19}$

Example

print(2 * 4 % 19) # 8

print(7 * 3 % 19) # 2

print(11 ** 3 % 19) # 1

print(pow(11, 3, 19)) # 1

Exercise 4, 5, 6, 7 and 8

4. Solve these equations in $F_{31}$
• $24 \times 19 = ?$
• $17^{3} = ?$
• $5^{5} \times 18 = ?$
5. Write a program to calculate $\{0 \cdot k, 1 \cdot k, 2 \cdot k, ..., 30 \cdot k\}$ in $F_{31}$ for some $k$. Notice anything?
6. Write the __mul__ method
7. Write the __pow__ method
8. Bonus: Write a program to calculate $i^{30}$ in $F_{31}$ for all $i > 0$. Notice anything?

Division

Defined as the inverse of multiplication

$2 \times 4 = 8 \pmod{19} \implies \frac{8}{2} = 4 \pmod{19}$

$7 \times 3 = 2 \pmod{19} \implies \frac{2}{3} = 7 \pmod{19}$

$15 \times 4 = 3 \pmod{19} \implies \frac{3}{4} = 15 \pmod{19}$

$11 \times 11 = 7 \pmod{19} \implies \frac{7}{11} = 11 \pmod{19}$

Fermat's Little Theorem

$n^{p-1} = 1 \pmod{p}$ for all $n$ if $p$ is prime

This means we can do division:

$1/n = n^{-1} = n^{-1} \cdot 1 = n^{-1} \cdot n^{p-1} = n^{p-2} \pmod{p}$

or $1/n = n^{p-2} \pmod{p}$

Division

$F_{19}$

$1/n = n^{p-2} \pmod{p}$

$2/3 = 2 \cdot 1/3 = 2 \cdot 3^{19-2} = 7 \pmod{19}$

$3/15 = 3 \cdot 1/15 = 3 \cdot 15^{19-2} = 4 \pmod{19}$

Example

print(2 * 3**17 % 19) # 7

print(2 * pow(3, 17, 19) % 19) # 7

print(3 * 15**17 % 19) # 4

print(3 * pow(15, -1, 19) % 19) # 4

Exercise 9 and 10

9. Solve these equations in $F_{31}$
• $3 / 24 = ?$
• $17^{-3} = ?$
• $4^{-4} \cdot 11 = ?$
10. Write the __truediv__ method

Elliptic Curves

• Equation
• Plotted over some set of numbers
• Useful because of something called point addition

Example

      
      x, y = -1, -1
      print(y**2 == x**3 + 5 * x + 7)  # True
      
    

Exercise 11 and 12

11. Which of these points are on the curve $y^2=x^3+5x+7$?
$(-2,4)$, $(3,7)$, $(18,77)$
12. Update the __init__ method to check that x and y are valid.

Point Addition

Vertical

Group Law for the point at $\infty$

$y^2=x^3+ax+b$

$(x_1,y_1) = (x_1, y_1) + (\infty, \infty)$

$(x_1,y_1) + (x_1, -y_1) = (\infty, \infty)$

$(\infty, \infty)$ is zero in point addition

Exercise 13

13. Update the __init__ and __add__ methods to handle $(\infty, \infty)$. (use x=None, y=None to represent the point)

Group Law for when $x_1 \neq x_2$

$y^2=x^3+ax+b$

$(x_3,y_3) = (x_1, y_1) + (x_2, y_2)$

$s = \frac{y_2-y_1}{x_2-x_1}$

$x_3 = s^2 - x_1 - x_2$

$y_3 = s(x_1-x_3) - y_1$

Example

$y^2=x^3+5x+7$

What is $(2,5)+(3,7)$?

$s = \frac{y_2-y_1}{x_2-x_1} = (7-5)/(3-2) = 2$

$x_3 = s^2 - x_1 - x_2 = 4 - 2 - 3 = -1$

$y_3 = s(x_1-x_3) - y_1 = 2(2-(-1)) - 5 = 1$

$(2,5)+(3,7)=(-1,1)$

Exercise 14 and 15

14. For the curve $y^2=x^3+5x+7$, what is $(2,5) + (-1,-1)$?
15. Update the __add__ method to handle when $x_1 \neq x_2$

Tangent

Group Law for when $P_1 = P_2$

$y^2=x^3+ax+b$

$(x_3,y_3) = (x_1, y_1) + (x_2, y_2)$

$s = \frac{3x_1^2+a}{2y_1}$

$x_3 = s^2 - 2x_1$

$y_3 = s(x_1-x_3) - y_1$

Example

$y^2=x^3+5x+7$

What is $(2,5)+(2,5)$?

$s = \frac{3x_1^2+a}{2y_1} = (3 \cdot 2^2 + 5)/(2 \cdot 5) = 1.7$

$x_3 = s^2 - 2x_1 = 1.72 - 2 \cdot 2 = -1.11$

$y_3 = s(x_1-x_3) - y_1 = 1.7 \cdot (2+1.11) - 5 = 0.287$

$(2,5)+(2,5)=(-1.11,0.287)$

Exercise 16 and 17

16. For the curve $y^2=x^3+5x+7$, what is $(-1,-1) + (-1,-1)$?
17. Update the __add__ method to handle when $P_1 = P_2$