{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Modular arithmetic\n",
    "\n",
    "This Jupyter notebook provides an example of using the Python package [gravis](https://pypi.org/project/gravis). The .ipynb file can be found [here](https://github.com/robert-haas/gravis/tree/master/examples).\n",
    "\n",
    "It demonstrates how calculations with **modular arithmetic** can be visualized as a directed graph.\n",
    "\n",
    "\n",
    "## References\n",
    "\n",
    "- Wikipedia: [Modular arithmetic](https://en.wikipedia.org/wiki/Modular_arithmetic)\n",
    "- Vitalik Buterin: [STARKs / A Modular Math Interlude](https://vitalik.ca/general/2017/11/22/starks_part_2.html#a-modular-math-interlude)\n",
    "\n",
    "## Data generation\n",
    "\n",
    "Create a directed graph where\n",
    "\n",
    "- nodes represent integers modulo `p`, i.e. the members `x` of a finite field\n",
    "- 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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import gravis as gv\n",
    "import networkx as nx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_digraph(p, k):\n",
    "    # Generate the graph\n",
    "    graph = nx.DiGraph()\n",
    "    solutions = set()\n",
    "    for x in range(p):\n",
    "        y = (x ** k) % p\n",
    "        solutions.add(y)\n",
    "        graph.add_edge(x, y)\n",
    "    print('Finite field with {p} elements. Found a set of {n} unique solutions '\n",
    "          'for the function y = x^{k} % {p}.'.format(k=k, p=p, n=len(solutions)))\n",
    "\n",
    "    # Assign node properties: size and color by indegree\n",
    "    for i in graph.nodes:\n",
    "        node = graph.nodes[i]\n",
    "        node['size'] = 5 + graph.in_degree(i) * 3\n",
    "        node['color'] = 'red' if graph.in_degree[i] > 0 else 'black'\n",
    "        node['hover'] = ''\n",
    "    \n",
    "    # Assign edge properties: label and label color\n",
    "    for i, j in graph.edges:\n",
    "        edge = graph.edges[(i, j)]\n",
    "        node = graph.nodes[j]\n",
    "        division_text = '{x}^{k} % {p} = {y}'.format(x=i, y=j, k=k, p=p)\n",
    "        edge['label'] = division_text\n",
    "        node['hover'] += division_text + '\\n'\n",
    "        edge['label_color'] = 'green'\n",
    "    return graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Visualization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_digraph(digraph):\n",
    "    fig = gv.d3(\n",
    "        digraph,\n",
    "        node_hover_neighborhood=True,\n",
    "        show_edge_label=True,\n",
    "        edge_label_data_source='label',\n",
    "        edge_label_size_factor=0.8,\n",
    "    ) \n",
    "    return fig"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Integers modulo p=17\n",
    "\n",
    "- Formula used to determine edges: `y = x^2 % 17`\n",
    "- Source node: `x` (=any integer of the field as input)\n",
    "- Target node: `y` (=some integer of the field as output, due to closure under multiplication)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dg = generate_digraph(p=17, k=2)\n",
    "plot_digraph(dg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Integers modulo p=23"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dg = generate_digraph(p=23, k=2)\n",
    "plot_digraph(dg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Integers modulo p=71"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dg = generate_digraph(p=71, k=2)\n",
    "plot_digraph(dg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Integers modulo p=73"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dg = generate_digraph(p=73, k=2)\n",
    "plot_digraph(dg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Integers modulo p=321"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dg = generate_digraph(p=321, k=2)\n",
    "plot_digraph(dg)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}