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

In [14]:
p = next_prime(200); M = Integers(p); p
Out[14]:
211
In [15]:
mod(313,5)
Out[15]:
3
In [16]:
M(217 * 12)
Out[16]:
72
In [17]:
primroot = M.multiplicative_generator(); primroot
Out[17]:
2

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

In [18]:
def dlog(h): 
 INDEX = 1;
 POWER = primroot;
 while POWER <> h:
   INDEX = INDEX + 1
   POWER = M(POWER * primroot);
 return INDEX
In [19]:
dlog(3)
Out[19]:
43

Check this against the sage builtin function

In [20]:
M(3).log(primroot)
Out[20]:
43

We will graph the discrete log function.

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

In [21]:
plot(point([(i+1,dlog(i+1)) for i in range(p-2)], pointsize = 30))
Out[21]:
In [0]: