2737.sagews

This worksheet introduces Sage as it would be useful to someone reading Hoffstein Pipher and Silverman's  "An Introduction to Mathematical Cryptography"

The Section Numbers are those from the text.

Section 2.2  The Discrete Logarithms problem

We find a prime p and a primitive root modulo p: primroot

p = next_prime(200); M = IntegerModRing(p); p

211

primroot = M.multiplicative_generator(); primroot

2

We make a discrete log function. Just the brute force one.

def dlog(h): 
 INDEX = 1;
 POWER = primroot;
 while POWER <> h:
   INDEX = INDEX + 1
   POWER = M(POWER * primroot);
 return INDEX

dlog(3)

43

We get a list of the powers of primroot, and then use it to define the discrete log.

y = 1;
powers = [];
for i in range(p-1):
    y = M(y*primroot)
    powers.append(y)

def Dlog(h): return powers.index(h)+1

Look at the first 10 of them

powers[1:10]; Dlog(16); Dlog(5)

[4, 8, 16, 32, 64, 128, 45, 90, 180] 4 132

Plot the discrete log. The plot(point( )) function needs a list of points: [ (1,1), (2,4), (3,9) ]

plot(point([(i+1,Dlog(i+1)) for i in range(p-2)], pointsize = 30))