Modular arithmetic¶

This Jupyter notebook provides an example of using the Python package gravis. The .ipynb file can be found here.

It demonstrates how calculations with modular arithmetic can be visualized as a directed graph.

References¶

Wikipedia: Modular arithmetic
Vitalik Buterin: STARKs / A Modular Math Interlude

Data generation¶

Create a directed graph where

nodes represent integers modulo p, i.e. the members x of a finite field
edges represent the relationship y = x^k (modulo p) where x is the source and y the target. This means the target is the k-th power of x.

[1]:

import gravis as gv
import networkx as nx

[2]:

def generate_digraph(p, k):
    # Generate the graph
    graph = nx.DiGraph()
    solutions = set()
    for x in range(p):
        y = (x ** k) % p
        solutions.add(y)
        graph.add_edge(x, y)
    print('Finite field with {p} elements. Found a set of {n} unique solutions '
          'for the function y = x^{k} % {p}.'.format(k=k, p=p, n=len(solutions)))

    # Assign node properties: size and color by indegree
    for i in graph.nodes:
        node = graph.nodes[i]
        node['size'] = 5 + graph.in_degree(i) * 3
        node['color'] = 'red' if graph.in_degree[i] > 0 else 'black'
        node['hover'] = ''

    # Assign edge properties: label and label color
    for i, j in graph.edges:
        edge = graph.edges[(i, j)]
        node = graph.nodes[j]
        division_text = '{x}^{k} % {p} = {y}'.format(x=i, y=j, k=k, p=p)
        edge['label'] = division_text
        node['hover'] += division_text + '\n'
        edge['label_color'] = 'green'
    return graph

Visualization¶

[3]:

def plot_digraph(digraph):
    fig = gv.d3(
        digraph,
        node_hover_neighborhood=True,
        show_edge_label=True,
        edge_label_data_source='label',
        edge_label_size_factor=0.8,
    )
    return fig