examples/logarithmfinding-short.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Ekerå–Håstad's algorithm for computing short discrete logarithms\n",
    "This notebook exemplifies using [Quaspy](https://github.com/ekera/quaspy) to simulate Ekerå–Håstads algorithm for computing short discrete logarithms [[EH17]](https://doi.org/10.1007/978-3-319-59879-6_20), with improvements from [[E20]](https://doi.org/10.1007/s10623-020-00783-2) and [[E23p]](https://doi.org/10.48550/arXiv.2309.01754), and the post-processing in [[E23p]](https://doi.org/10.48550/arXiv.2309.01754).\n",
    "\n",
    "To start off, let us define the MODP-3072 safe-prime group used in IKEv2, see [RFC 3526](https://datatracker.ietf.org/doc/html/rfc3526) and Tab. 25 on p. 133 in App. A of [NIST SP 800-56A Rev. 3](https://doi.org/10.6028/NIST.SP.800-56Ar3)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!pip3 install -q quaspy # Make sure that quaspy is installed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from quaspy.math.groups import IntegerModRingMulSubgroupElement;\n",
    "\n",
    "# Define the safe prime.\n",
    "p = 5809605995369958062791915965639201402176612226902900533702900882779736177890990861472094774477339581147373410185646378328043729800750470098210924487866935059164371588168047540943981644516632755067501626434556398193186628990071248660819361205119793693985433297036118232914410171876807536457391277857011849897410207519105333355801121109356897459426271845471397952675959440793493071628394122780510124618488232602464649876850458861245784240929258426287699705312584509625419513463605155428017165714465363094021609290561084025893662561222573202082865797821865270991145082200656978177192827024538990239969175546190770645685893438011714430426409338676314743571154537142031573004276428701433036381801705308659830751190352946025482059931306571004727362479688415574702596946457770284148435989129632853918392117997472632693078113129886487399347796982772784615865232621289656944284216824611318709764535152507354116344703769998514148343807;\n",
    "\n",
    "# Define the generator.\n",
    "g = IntegerModRingMulSubgroupElement(2, p);\n",
    "\n",
    "# Define the order of the generator.\n",
    "r = (p - 1) // 2;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For this group, the exponent $d$ is selected uniformly at random from $[0, 2^{256}) \\cap \\mathbb Z$.\n",
    "\n",
    "To this end, we use the [<code>sample_integer(B)</code>](../docs/math/random/sample_integer.md) convenience function provided by [Quaspy](https://github.com/ekera/quaspy)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sampled d = 39445834421792263746237187678251780871950636679959961948118792881895030241537\n",
      "\n",
      "Computed x = 2573093705292940932930082160482608801144545720558445293658719917259257738445843251451463028958822772287829203956821000799286681936920981759783608918634560964063185878287779082197865924858263647239721297517732474860039529321367128678263996680506875302664931782493305193691251362422379601387256311870229514004537727445783850302714966093160422239368392040848031758268750309508758501612128509168446566259177742723285929371476747197198788559974725965585744494618539879405444211902735634726515365959740365149104220510878173121657000941028948462504566665027296088127846839544408509608519136777482832743714301045226694504160629417843002196036990796405340498705825016197929059250992938384026867526072129752042583437287918172366969031310505583093412110339590493127412663757379273148838213316920732726663193503835999094271840436097570479302139848762380063645005385601457815909206937907150193277164879060729781531919086625465459189933034 (mod 5809605995369958062791915965639201402176612226902900533702900882779736177890990861472094774477339581147373410185646378328043729800750470098210924487866935059164371588168047540943981644516632755067501626434556398193186628990071248660819361205119793693985433297036118232914410171876807536457391277857011849897410207519105333355801121109356897459426271845471397952675959440793493071628394122780510124618488232602464649876850458861245784240929258426287699705312584509625419513463605155428017165714465363094021609290561084025893662561222573202082865797821865270991145082200656978177192827024538990239969175546190770645685893438011714430426409338676314743571154537142031573004276428701433036381801705308659830751190352946025482059931306571004727362479688415574702596946457770284148435989129632853918392117997472632693078113129886487399347796982772784615865232621289656944284216824611318709764535152507354116344703769998514148343807)\n"
     ]
    }
   ],
   "source": [
    "from quaspy.math.random import sample_integer;\n",
    "\n",
    "# Sample d.\n",
    "m = 256;\n",
    "d = sample_integer(2 ** m);\n",
    "\n",
    "print(\"Sampled d =\", d);\n",
    "\n",
    "# Compute x.\n",
    "x = g ** d;\n",
    "\n",
    "print(\"\\nComputed x =\", x);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Simulating the quantum part of Ekerå–Håstad's algorithm\n",
    "[Quaspy](https://github.com/ekera/quaspy) provides a function [<code>sample_j_k_given_d_r_tau(d, r, m, ell, tau, ..)</code>](../docs/logarithmfinding/short/sampling/sample_j_k_given_d_r_tau.md) for simulating the quantum part of Ekerå–Håstad's algorithm exactly (up to arbitrary precision) for a given logarithm $d$, order $r$, and parameters $m$, $\\ell$ and $\\tau$, where $\\tau$ is related to the sampling as explained in [[E23p]](https://doi.org/10.48550/arXiv.2309.01754).\n",
    "\n",
    "Below, we use this function to simulate running the algorithm for $d$ and $r$ with control registers of length $m + \\ell$ bits and $\\ell$ bits respectively.\n",
    "\n",
    "This yields a frequency pair $(j, k)$ sampled from the probability distribution induced by the algorithm:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sampled j = 63754213727702222666883247198583548998355626313743155351243894725606284027105701604734047720082414957777446139179437453027646826267342071542991574566367\n",
      "Sampled k = 66280279023355946965346584704632737288343734748410179600493537242010583098246\n"
     ]
    }
   ],
   "source": [
    "from quaspy.logarithmfinding.short.sampling import sample_j_k_given_d_r_tau;\n",
    "\n",
    "l = m;\n",
    "tau = 27;\n",
    "\n",
    "[j, k] = sample_j_k_given_d_r_tau(d, r, m, l, tau);\n",
    "\n",
    "print(\"Sampled j =\", j);\n",
    "print(\"Sampled k =\", k);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1. Solving the frequency pair $(j, k)$ for $d$\n",
    "We now proceed to solve the frequency pair $(j, k)$ for the logarithm $d$.\n",
    "\n",
    "To this end, we use the [<code>solve_j_k_for_d(j, k, m, l, g, x, tau, ..)</code>](../docs/logarithmfinding/short/postprocessing/solve_j_k_for_d.md) convenience function provided by [Quaspy](https://github.com/ekera/quaspy) to solve $(j, k)$ for $d$ using the lattice-based post-processing from [[E23p]](https://doi.org/10.48550/arXiv.2309.01754)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Recovered d = 39445834421792263746237187678251780871950636679959961948118792881895030241537\n",
      "\n",
      "[ OK ] Successfully recovered d.\n"
     ]
    }
   ],
   "source": [
    "from quaspy.logarithmfinding.short.postprocessing import solve_j_k_for_d;\n",
    "\n",
    "for [tau, t] in [[4, 2], [7, 2], [14, 2], [17, 2], [27, 2]]:\n",
    "  recovered_d = solve_j_k_for_d(j, k, m, l, g, x, tau = tau, t = t);\n",
    "  if recovered_d != None:\n",
    "    break;\n",
    "\n",
    "if (recovered_d == d):\n",
    "  print(\"Recovered d =\", d);\n",
    "\n",
    "  print(\"\\n[ OK ] Successfully recovered d.\");\n",
    "else:\n",
    "  print(\"[FAIL] Failed to recover d.\");"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "31f2aee4e71d21fbe5cf8b01ff0e069b9275f58929596ceb00d14d90e3e16cd6"
  },
  "kernelspec": {
   "display_name": "Python 3.8.9 64-bit",
   "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.9.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}