Week 3 Wednesday#

Screenshare notes#

Slide 1

Slide 2

Slide 3

Slide 4

Slide 5

Deepnote notebook#

# I learned we can use `from sympy` instead of `from sympy.ntheory`.
from sympy import n_order, nextprime, isprime

p = 23

n_order(7, p)

22

g = 7

from numpy import sqrt, floor

n = floor(sqrt(p-1)) + 1

type(n)

numpy.float64

# I'll eventually need an integer, convert to an integer using `int`
n = floor(sqrt(p-1)) + 1
n = int(n)

type(n)

int

a = 17
A = pow(g, a, p)
A

19

Goal: compute the discrete logarithm of A = 19 to the base g = 7.

n

5

# would be more efficient to just multiply by g at each step
baby_list = []
for i in range(n+1):
    baby_list.append(pow(g, i, p))

baby_list

[1, 7, 3, 21, 9, 17]

Want \([A, Ag^{-n}, Ag^{-2n}, ...]\)

# Mistake: we didn't reduce the giant list elements mod p after multiplying
giant_list = []
for j in range(n+1):
    giant_list.append(A*pow(g, -j*n, p))

giant_list

[19, 361, 304, 95, 57, 209]

giant_list = []
for j in range(n+1):
    giant_list.append((A*pow(g, -j*n, p))%p)

giant_list

[19, 16, 5, 3, 11, 2]

baby_list

[1, 7, 3, 21, 9, 17]

3 is the intersection (the collision). This corresponds to index 2 in baby_list and index 3 in giant_list.

j = giant_list.index(3)
j

3

i = baby_list.index(3)
i

2

In our notation from the collision algorithm description, \(i = 2\) and \(j = 3\).

x = i + n*j
x

17

a

17

# Efficient way to find an intersection/collision between these two lists
# Credit ChatGPT:
set(baby_list) & set(giant_list)

{3}
Created in deepnote.com Created in Deepnote