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 = Integers(p); p
mod(313,5)
M(217 * 12)
primroot = M.multiplicative_generator(); primroot
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)
Check this against the sage builtin function
M(3).log(primroot)
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) ]
plot(point([(i+1,dlog(i+1)) for i in range(p-2)], pointsize = 30))