Modular multiplication mixes well
Math 302 Advanced Cryptography
January 30, 2019

T. Ratliff, Wheaton College
ratliff_thomas@wheatoncollege.edu

Why the DLP is hard

Let’s use p=7919, the 1000th prime, and find a primitive root

p=Prime[1000]
g=PrimitiveRoot[p]

Build a table of the powers of g modulo p

gPowers = Table[ Mod[g^i, p], {i,1,p-1}];

Let’s plot the first 10 powers

gPowers[[1;;10]]
ListPlot[gPowers[[1;;10]]]

Now the first 100

ListPlot[gPowers[[1;;100]]]

Now the entire list

ListPlot[gPowers]

The punch line is that given a value h=(g^x)mod p, it is not obvious how to find x

p1=ListPlot[gPowers];
p2=Plot[4000,{x,0,p}, PlotStyle->Red];
Show[p1,p2]