Week 2 Monday#

Screenshare notes#

Slide 1

Slide 2

Slide 3

Slide 4

Deepnote notebook#

import numpy as np
import pandas as pd
import altair as alt

from sympy.ntheory import isprime, nextprime, factorint, n_order

Why is discrete log so much harder to compute than ordinary logarithm?

help(np.emath.logn)

Help on function logn in module numpy.lib.scimath:

logn(n, x)
    Take log base n of x.
    
    If `x` contains negative inputs, the answer is computed and returned in the
    complex domain.
    
    Parameters
    ----------
    n : array_like
       The integer base(s) in which the log is taken.
    x : array_like
       The value(s) whose log base `n` is (are) required.
    
    Returns
    -------
    out : ndarray or scalar
       The log base `n` of the `x` value(s). If `x` was a scalar, so is
       `out`, otherwise an array is returned.
    
    Examples
    --------
    >>> np.set_printoptions(precision=4)
    
    >>> np.emath.logn(2, [4, 8])
    array([2., 3.])
    >>> np.emath.logn(2, [-4, -8, 8])
    array([2.+4.5324j, 3.+4.5324j, 3.+0.j    ])

# Easier to type
logn = np.emath.logn

logn(17, 324723874328247)

11.793674623824684

%%time
logn(17, 324723874328247)

CPU times: user 156 µs, sys: 0 ns, total: 156 µs
Wall time: 160 µs

11.793674623824684

%%time
logn(17, 324723874328247000)

CPU times: user 115 µs, sys: 41 µs, total: 156 µs
Wall time: 160 µs

14.23180915170056

x = np.linspace(0, 6, 500)

x[:5]

array([0.        , 0.01202405, 0.0240481 , 0.03607214, 0.04809619])

17**2

289

pow(17, 2)

289

pow(17, 0.012)

1.0345831170604813

# list comprehension
y = [pow(17, a) for a in x]

y[:5]

[1.0,
 1.034653609113816,
 1.0705080908522455,
 1.107605059785817,
 1.1459875725801196]

# for-loop way to make y
y = []
for a in x:
    y.append(pow(17, a))

y[:5]

[1.0,
 1.034653609113816,
 1.0705080908522455,
 1.107605059785817,
 1.1459875725801196]

df = pd.DataFrame({
    "x": x,
    "y": y
})

df[:5]
x y
0 0.000000 1.000000
1 0.012024 1.034654
2 0.024048 1.070508
3 0.036072 1.107605
4 0.048096 1.145988 
# Notice how regular this graph is
alt.Chart(df).mark_circle().encode(
    x = "x",
    y = "y"
)

nextprime(20)

23

p = nextprime(1000)
p

1009

Let’s try to find a primitive root modulo 1009.

# Is 2 a primitive root?
n_order(2, 1009)

504

n_order(3, 1009)

168

n_order(4, 1009)

252

n_order(5, p)

504

for g in range(1, p):
    if n_order(g,p) == p-1:
        break

g

11

x = range(p)
y = [pow(g, a, p) for a in x] # pow with three arguments is used for efficient modular exponentiation
# much more efficient for big values than pow(g,a)%p

df_discrete = pd.DataFrame({
    "x": x,
    "y": y
})

df_discrete[:5]
x y
0 0 1
1 1 11
2 2 121
3 3 322
4 4 515 
(11**3)%1009

322

# Notice how irregular this looks
alt.Chart(df_discrete).mark_circle().encode(
    x = "x",
    y = "y",
    tooltip = ["x", "y"]
)

Because this is so irregular (no obvious patterns), our intuition is that it’s difficult to invert this procedure, i.e., discrete logarithms are difficult to compute

p = 65537
x = range(5000)
y = [pow(2, a, p) for a in x]

df2 = pd.DataFrame(
    {
        "x": x,
        "y": y
    }
)

df2[:5]
x y
0 0 1
1 1 2
2 2 4
3 3 8
4 4 16 
alt.Chart(df2).mark_circle().encode(
    x = "x",
    y = "y",
    tooltip = ["x", "y"]
)

# What went wrong?  2 has a very small multiplicative order modulo p
n_order(2, p)

32

2**32

4294967296

2**16

65536

p

65537

pow(2, 16)

65536
Created in deepnote.com Created in Deepnote