<jupyter_start><jupyter_text>Exercise 1Remember the % operator does the actual modulo operation. Also remember that `+` and `-` need to be in `()` because in the order of operations `%` comes before `+` and `-`. 1.1. Solve these equations in \\(F_{31}\\):```2+15=?17+21=?29-4=?15-30=?``` 1.2. Make [these tests](/edit/session1/ecc.py) pass:```ecc.py:FieldElementTest:test_addecc.py:FieldElementTest:test_sub```<jupyter_code># Exercise 1.1

# remember that % is the modulo operator
prime = 31
# 2+15=?
print((2+15) % prime)
# 17+21=?
print((17+21) % prime)
# 29-4=?
print((29-4) % prime)
# 15-30=?
print((15-30) % prime)
# Exercise 1.2

reload(ecc)
run_test(ecc.FieldElementTest('test_add'))
run_test(ecc.FieldElementTest('test_sub'))
# Multiplication/Exponentiation Example

print(2 * 4 % 19)
print(7 * 3 % 19)
print(11 ** 3 % 19)
print(pow(11, 3, 19))<jupyter_output>8
2
1
1<jupyter_text>Exercise 2 2.1. Solve these equations in \\(F_{31}\\):\\(24\cdot19=?\\)\\(17^3=?\\)\\(5^5\cdot18=?\\) 2.2. Write a program to calculate \\(0k, 1k, 2k, 3k, ... 30k\\) for some k in \\(F_{31}\\).  Notice anything about these sets? 2.3. Make [these tests](/edit/session1/ecc.py) pass:```ecc.py:FieldElementTest:test_mulecc.py:FieldElementTest:test_pow``` Bonus. Write a program to calculate \\(k^{30}\\) for all k in \\(F_{31}\\). Notice anything?<jupyter_code># Exercise 2.1

# remember that ** is the exponentiation operator
prime = 31
# 24*19=?
print(24*19 % prime)
# 17^3=?
print(17**3 % prime)
# 5^5*18=?
print(5**5*18 % prime)
# Exercise 2.2

from random import randint

prime = 31
k = randint(1,prime)

# use range(prime) to iterate over all numbers from 0 to 30 inclusive
print(sorted([i*k % prime for i in range(prime)]))
# Exercise 2.3

reload(ecc)
run_test(ecc.FieldElementTest('test_mul'))
run_test(ecc.FieldElementTest('test_pow'))
# Bonus

prime = 31

# use range(1, prime) to iterate over all numbers from 1 to 30 inclusive
print([i**30 % prime for i in range(1, prime)])
# Division Example

print(2 * 3**17 % 19)
print(2 * pow(3, 17, 19) % 19)
print(3 * 15**17 % 19)
print(3 * pow(15, 17, 19) % 19)<jupyter_output>7
7
4
4<jupyter_text>Exercise 3 3.1. Solve these equations in \\(F_{31}\\):\\(3/24 = ?\\)\\(17^{-3} = ?\\)\\(4^{-4}\cdot{11} = ?\\) 3.2. Make [these tests](/edit/session1/ecc.py) pass:```ecc.py:FieldElementTest:test_div```<jupyter_code># Exercise 3.1

# remember pow(x, p-2, p) is the same as 1/x in F_p
prime = 31
# 3/24 = ?
print(3*24**(prime-2) % prime)
# 17^(-3) = ?
print(pow(17, prime-4, prime))
# 4^(-4)*11 = ?
print(pow(4, prime-5, prime) * 11 % prime)
# Exercise 3.2

reload(ecc)
run_test(ecc.FieldElementTest('test_div'))

# Hint: the __pow__ method needs a positive number for the exponent.
# You can mod by p-1
# Elliptic Curve Example

x, y = -1, -1

print(y**2 == x**3 + 5*x + 7)<jupyter_output>True<jupyter_text>Exercise 4 4.1. For the curve \\(y^2 = x^3 + 5x + 7\\), which of these are on the curve?\\((-2,4), (3,7), (18,77)\\) 4.2. Make [this test](/edit/session1/ecc.py) pass```ecc.py:PointTest:test_on_curve```<jupyter_code># Exercise 4.1

# (-2,4), (3,7), (18,77)
# equation in python is: y**2 == x**3 + 5*x + 7

points = ((-2,4), (3,7), (18,77))

for x, y in points:
    # determine whether (x,y) is on the curve
    if y**2 == x**3 + 5*x + 7:
        print('({},{}) is on the curve'.format(x,y))
    else:
        print('({},{}) is not on the curve'.format(x,y))
# Exercise 4.2

reload(ecc)
run_test(ecc.PointTest('test_on_curve'))<jupyter_output>.
----------------------------------------------------------------------
Ran 1 test in 0.001s

OK<jupyter_text>Exercise 5 5.1. Make [this test](/edit/session1/ecc.py) pass```ecc.py:PointTest:test_add0```<jupyter_code># Exercise 5.1

reload(ecc)
run_test(ecc.PointTest('test_add0'))
# Point Addition where x1 != x2 Example

x1, y1 = (2, 5)
x2, y2 = (3, 7)
s = (y2-y1)/(x2-x1)
x3 = s**2 - x2 - x1
y3 = s*(x1-x3)-y1
print(x3, y3)<jupyter_output>-1.0 1.0<jupyter_text>Exercise 6 6.1. For the curve \\(y^2 = x^3 + 5x + 7\\), what is \\((2,5) + (-1,-1)\\)? 6.2. Make [this test](/edit/session1/ecc.py) pass```ecc.py:PointTest:test_add1```<jupyter_code># Exercise 6.1

x1, y1 = (2,5)
x2, y2 = (-1,-1)
# formula in python:
# s = (y2-y1)/(x2-x1)
s = (y2-y1)/(x2-x1)
# x3 = s**2 - x2 - x1
x3 = s**2 - x2 - x1
# y3 = s*(x1-x3)-y1
y3 = s*(x1-x3) - y1

print(x3, y3)
# Exercise 6.2

reload(ecc)
run_test(ecc.PointTest('test_add1'))
# Point Addition where x1 = x2 Example

a = 5
x1, y1 = (2, 5)
s = (3*x1**2+a)/(2*y1)
x3 = s**2 - 2*x1
y3 = s*(x1-x3) - y1
print(x3, y3)<jupyter_output>-1.1100000000000003 0.2870000000000008<jupyter_text>Exercise 7 7.1. For the curve \\(y^2 = x^3 + 5x + 7\\), what is \\((-1,1) + (-1,1)\\)? 7.2. Make [this test](/edit/session1/ecc.py) pass```ecc.py:PointTest:test_add2```<jupyter_code># Exercise 7.1

a, b = 5, 7
x1, y1 = -1, -1

# formula in python
# s = (3*x1**2+a)/(2*y1)
s = (3*x1**2+a)/(2*y1)
# x3 = s**2 - 2*x1
x3 = s**2 - 2*x1
# y3 = s*(x1-x3) - y1
y3 = s*(x1-x3) - y1

print(x3, y3)
# Exercise 7.2

reload(ecc)
run_test(ecc.PointTest('test_add2'))<jupyter_output>.
----------------------------------------------------------------------
Ran 1 test in 0.001s

OK
{'fraction_non_alphanumeric': 0.23588553750966745, 'fraction_numerical': 0.09667440061871617, 'mean_word_length': 3.463330457290768, 'pattern_counts': {'":': 0, '<': 22, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '43553', 'license': 'BSD-2-Clause', 'n_tokens_mistral': 2539, 'n_tokens_neox': 2267, 'n_words': 545, 'path': 'session1/complete/session1.ipynb', 'repo_name': 'casey-bowman/pb-exercises', 'size': '5172'}