{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Trying out different libraries and algorithms\n",
    "\n",
    "Let's first import Python/Sage bindings to compute embeddings using different libraries and algorithms."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from ffisom import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lets define an extension finite field with different underlying libraries:\n",
    "* Sage uses PARI/GP by default;\n",
    "* we added a wrapper for FLINT implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "p = 7\n",
    "n = 237\n",
    "q = p**n\n",
    "k = GF(q, name='z')\n",
    "k_flint = GF_flint(p, k.modulus(), name='z')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here comes data of importance to the algorithms:\n",
    "* o is the degree of the auxiliary extension needed for cyclotomic Rains\n",
    "* c is the degree of the cyclotomic extension needed for Kummer type algorithms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 78\n"
     ]
    }
   ],
   "source": [
    "o, _ = find_root_order(p, [n, n], n, verbose=False)\n",
    "c = Mod(p,n).multiplicative_order()\n",
    "print o, c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Algebraic groups algorithms\n",
    "\n",
    "We cannot test Magma implementation of cyclotomic Rains here, but we can test ours."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* with the default PARI/GP implementation for finite field arithmetic:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 43 ms, sys: 2 ms, total: 45 ms\n",
      "Wall time: 43.3 ms\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "%time a, b = find_gens_cyclorains(k, k)\n",
    "print a.minpoly() == b.minpoly()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* or FLINT implementation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 34 ms, sys: 4 ms, total: 38 ms\n",
      "Wall time: 35.9 ms\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "%time a, b = find_gens_cyclorains(k_flint, k_flint)\n",
    "print a.minpoly() == b.minpoly()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As o == 2, the conic Rains algorithm does not apply here, but we can try the elliptic variation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* if PARI/GP is used for finite field arithmetic, then Sage is used for elliptic curve arithmetic:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1.44 s, sys: 1 ms, total: 1.44 s\n",
      "Wall time: 1.44 s\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "%time a, b = find_gens_ellrains(k, k)\n",
    "print a.minpoly() == b.minpoly()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* if FLINT is, then the C code from ellmul is used:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 391 ms, sys: 2 ms, total: 393 ms\n",
      "Wall time: 388 ms\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "%time a, b = find_gens_ellrains(k_flint, k_flint)\n",
    "print a.minpoly() == b.minpoly()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Kummer type algorithms\n",
    "\n",
    "Let's try PARI/GP implementation of Lenstra/Allombert:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 2.95 s, sys: 0 ns, total: 2.95 s\n",
      "Wall time: 2.95 s\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "%time a, b = find_gens_pari(k, k)\n",
    "print a.minpoly() == b.minpoly()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And finally our C++ implementations of variations on Lenstra/Allombert:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "LINALG_CYCLO\n",
      "CPU times: user 584 ms, sys: 0 ns, total: 584 ms\n",
      "Wall time: 583 ms\n",
      "True\n",
      "LINALG_ONLY\n",
      "CPU times: user 211 ms, sys: 0 ns, total: 211 ms\n",
      "Wall time: 211 ms\n",
      "True\n",
      "LINALG\n",
      "CPU times: user 217 ms, sys: 0 ns, total: 217 ms\n",
      "Wall time: 217 ms\n",
      "True\n",
      "MODCOMP\n",
      "CPU times: user 217 ms, sys: 0 ns, total: 217 ms\n",
      "Wall time: 217 ms\n",
      "True\n",
      "COFACTOR\n",
      "CPU times: user 190 ms, sys: 0 ns, total: 190 ms\n",
      "Wall time: 189 ms\n",
      "True\n",
      "ITERFROB\n",
      "CPU times: user 193 ms, sys: 0 ns, total: 193 ms\n",
      "Wall time: 193 ms\n",
      "True\n",
      "MPE\n",
      "CPU times: user 233 ms, sys: 0 ns, total: 233 ms\n",
      "Wall time: 233 ms\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "for i, algo in enumerate(kummer_algolist[2*(c==1):-2*(c==1)-1]):\n",
    "    print kummer_namelist[2*(c==1)+i]\n",
    "    %time a, b = find_gens_kummer(k_flint, k_flint, n, algo)\n",
    "    print a.minpoly() == b.minpoly()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Benchmarking\n",
    "\n",
    "All of the above can be automated to get performance data using functions from the benchmark module.\n",
    "The p, n, o, c stuff is as above and are repeated on the timing line where it is followed by timings for :\n",
    "* Magma version of cyclotomic Rains\n",
    "* our Sage/C version of cyclotomic Rains\n",
    "* our Sage/C version of conic Rains\n",
    "* our Sage/C version of elliptic Rains\n",
    "* PARI/GP version of Lenstra/Allombert\n",
    "* our C++ version of Lenstra/Allombert using linear algebra over the cyclotomic extension\n",
    "* our C++ version of Lenstra/Allombert using linear algebra even for Frobenius computation à la PARI/GP\n",
    "* our C++ version of Lenstra/Allombert using linear algebra for kernel elements but modular composition for Frobenius computation\n",
    "* our C++ version of Lenstra/Allombert using modular composition and a trace like formula for kernel elements\n",
    "* our C++ version of Lenstra/Allombert using modular composition and the cofactor trick for kernel elements\n",
    "* our C++ version of Lenstra/Allombert using naive iterated Frobenius with modular exponentiation\n",
    "* our C++ version of Lenstra/Allombert using iterated Frobenius with multipoint evaluation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "p = 3, n = 5, (o = 1, c = 4)                                                   \n",
      "3 5 (1, 4) 0 0.00104029178619 0 0 0.000214171409607 0.000252461433411 0.000206804275513 0.000239109992981 0.00023558139801 0.000199675559998 0.000184798240662 0.000219798088074\n",
      "p = 3, n = 7, (o = 4, c = 6)                                                   \n",
      "3 7 (4, 6) 0 0.0182385921478 0 0 0.000329279899597 0.000423884391785 0.000290179252625 0.00036346912384 0.000365328788757 0.000275325775146 0.000277233123779 0.000323891639709\n",
      "p = 5, n = 3, (o = 2, c = 2)                                                   \n",
      "5 3 (2, 2) 0 0.00926465988159 0.00410797595978 0.00565741062164 0.000153589248657 8.82625579834e-05 7.37428665161e-05 8.65697860718e-05 8.50915908813e-05 7.74383544922e-05 6.81638717651e-05 7.14063644409e-05\n",
      "p = 5, n = 7, (o = 2, c = 6)                                                   \n",
      "5 7 (2, 6) 0 0.0130973339081 0.00559575557709 0.00507645606995 0.00050151348114 0.000452399253845 0.000354504585266 0.000415539741516 0.000410485267639 0.000329875946045 0.000319623947144 0.000390458106995\n",
      "p = 7, n = 3, (o = 1, c = 1)                                                   \n",
      "7 3 (1, 1) 0 0.00118911266327 0 0.00498025417328 0.000131869316101 0 0 2.70128250122e-05 2.80618667603e-05 2.91109085083e-05 0 0\n",
      "p = 7, n = 5, (o = 2, c = 4)                                                   \n",
      "7 5 (2, 4) 0 0.0141561985016 0.00537779331207 0.005087018013 0.000209999084473 0.000223612785339 0.000172328948975 0.000203800201416 0.000200629234314 0.000172138214111 0.000155472755432 0.000178909301758\n"
     ]
    }
   ],
   "source": [
    "from benchmark import *\n",
    "benchmark(pbound=[3, 10], nbound=[3,10], prime=True, skip_magma=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 8.0",
   "language": "",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}