Multiplicative Dynamics | Introduction to Cryptography and Coding Theory

Set $n$ to be the modulus. Set $a$ to be some integer. This will make an arrow diagram picture of $x \mapsto a x$ on the ring $Z / n Z$ , i.e. the elements modulo $n$ .

xxxxxxxxxx
 
n = 7
a = 2
R = IntegerModRing(n)
left=[' '+str(r)+' ' for r in R]
right=['  '+str(r)+'  ' for r in R]
pre_pos=graphs.CompleteBipartiteGraph(len(left),len(right)).get_pos()
G = DiGraph() 
pos={}
for (i,v) in enumerate(left+right):
    G.add_vertex(v)
    pos[v]=pre_pos[i]
for l in range(n):
    G.add_edge(left[l],right[lift(R(a*l))])
G.plot(pos=pos)

The next box plots the same function, but as a dynamical portrait. That means it will draw one vertex for each residue mod n and draw arrows for what the function does.

xxxxxxxxxx
 
n = 7
a = 2
R = IntegerModRing(n)
verts=[' '+str(r)+' ' for r in R]
H = DiGraph(loops=True) 
pos={}
for k in range(n):
    H.add_vertex(verts[k])
for l in range(n):
    H.add_edge(verts[l],verts[lift(R(a*l))])
H.plot(vertex_size=1000, vertex_color="lightblue")

Fall 2024 – Professor Katherine Stange