{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction to PARI/GP\n",
    "\n",
    "- PARI is a C library, allowing fast computations.\n",
    "- GP is the name of the scripting language giving access to the PARI functions.\n",
    "\n",
    "There are many ways to use PARI/GP:\n",
    "\n",
    "- [Jupyter interface](https://github.com/jdemeyer/pari_jupyter) to GP (the application that you are currently using)\n",
    "- [In your browser](https://pari.math.u-bordeaux.fr/gp.html) using JavaScript\n",
    "- GP interactive shell (command-line application)\n",
    "- Python package [cypari2](https://github.com/sagemath/cypari2)\n",
    "- C code calling the PARI functions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Basic objects"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "40526919504877216755680601905432322134980384796226602145184481280000000000000"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "57!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1/3"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2 / 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2*I"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(1+I)^2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1/(x^2 + 2*x + 1)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(x+1)^(-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Mod(3, 5)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Mod(2,5)^3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Mod(1, x^2 + x + 1)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Mod(x, x^2+x+1)^3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2*a^4 + 2*a^3 + 2"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = ffgen([3,5],'a) \n",
    "a^12  \\\\ in F_3^5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.1415926535897932384626433832795028842"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Pi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.69314718055994530941723212145817656807"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "log(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "   realprecision = 115 significant digits (100 digits displayed)\n"
     ]
    }
   ],
   "source": [
    "\\p100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.6931471805599453094172321214581765680755001343602552541206800094933936219696947156058633269964186875"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "log(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "exp(%)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x - 1/2*x^2 + 1/3*x^3 - 1/4*x^4 + 1/5*x^5 - 1/6*x^6 + 1/7*x^7 - 1/8*x^8 + 1/9*x^9 - 1/10*x^10 + 1/11*x^11 - 1/12*x^12 + 1/13*x^13 - 1/14*x^14 + 1/15*x^15 + O(x^16)"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "log(1+x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1 + x + O(x^16)"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "exp(%)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Help topics: for a list of relevant subtopics, type ?n for n in\n",
      "   0: user-defined functions (aliases, installed and user functions)\n",
      "   1: PROGRAMMING under GP\n",
      "   2: Standard monadic or dyadic OPERATORS\n",
      "   3: CONVERSIONS and similar elementary functions\n",
      "   4: functions related to COMBINATORICS\n",
      "   5: NUMBER THEORETICAL functions\n",
      "   6: POLYNOMIALS and power series\n",
      "   7: Vectors, matrices, LINEAR ALGEBRA and sets\n",
      "   8: TRANSCENDENTAL functions\n",
      "   9: SUMS, products, integrals and similar functions\n",
      "  10: General NUMBER FIELDS\n",
      "  11: Associative and central simple ALGEBRAS\n",
      "  12: ELLIPTIC CURVES\n",
      "  13: L-FUNCTIONS\n",
      "  14: MODULAR FORMS\n",
      "  15: MODULAR SYMBOLS\n",
      "  16: GRAPHIC functions\n",
      "  17: The PARI community\n",
      "Also:\n",
      "  ? functionname (short on-line help)\n",
      "  ?\\             (keyboard shortcuts)\n",
      "  ?.             (member functions)\n",
      "Extended help (if available):\n",
      "  ??             (opens the full user's manual in a dvi previewer)\n",
      "  ??  tutorial / refcard / libpari (tutorial/reference card/libpari manual)\n",
      "  ??  refcard-ell (or -lfun/-mf/-nf: specialized reference card)\n",
      "  ??  keyword    (long help text about \"keyword\" from the user's manual)\n",
      "  ??? keyword    (a propos: list of related functions).\n"
     ]
    }
   ],
   "source": [
    "?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Help"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "binomial      fibonacci     hammingweight numbpart      numtoperm\n",
      "partitions    permorder     permsign      permtonum     stirling\n",
      "\n"
     ]
    }
   ],
   "source": [
    "?4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "atan(x): arc tangent of x.\n",
      "\n"
     ]
    }
   ],
   "source": [
    "?atan"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "algdisc           bnfsunit          charker           charpoly\n",
      "ellheightmatrix   ellpadicregulator forsubgroup       matdet\n",
      "matdetint         matdetmod         mathnfmod         matrixqz\n",
      "mspolygon         nfdetint          nfhnfmod          polresultant\n",
      "rnfdet            \n",
      "\n",
      "See also:\n",
      "  Finite abelian groups\n",
      "  Pseudo-bases, determinant\n",
      "\u001b[0m\n"
     ]
    }
   ],
   "source": [
    "???determinant"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Vectors and matrices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "V = [1,2,3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 5, 6]~"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "W = [4,5,6]~"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\n",
       "[1 2 3]\n",
       "\n",
       "[4 5 6]\n"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M = [1,2,3;4,5,6]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "32"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "V*W"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[32, 77]~"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M*W"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U = [1..10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Components"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "V[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 5]~"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "W[1..2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M[2,2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3]"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M[1,]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 5]~"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M[,2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\n",
       "[1 2]\n",
       "\n",
       "[4 5]\n"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M[1..2,1..2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Polymorphism"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\n",
       "[ 7 1]\n",
       "\n",
       "[13 1]\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factor(91)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\n",
       "[      -1 1]\n",
       "\n",
       "[   1 + I 1]\n",
       "\n",
       "[ 4 + 5*I 1]\n",
       "\n",
       "[1 + 10*I 1]\n"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factor(91+I)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\n",
       "[x^2 - 2*x + 2 1]\n",
       "\n",
       "[x^2 + 2*x + 2 1]\n"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factor(x^4+4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\n",
       "[x + (-1 - I) 1]\n",
       "\n",
       "[ x + (1 - I) 1]\n",
       "\n",
       "[x + (-1 + I) 1]\n",
       "\n",
       "[ x + (1 + I) 1]\n"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factor((x^4+4)*I)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\n",
       "[x^2 + Mod(-y, y^2 - 2)*x + 1 1]\n",
       "\n",
       "[ x^2 + Mod(y, y^2 - 2)*x + 1 1]\n"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factor((x^4+1)*Mod(1,y^2-2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\n",
       "[Mod(1, 13)*x + Mod(4, 13) 1]\n",
       "\n",
       "[Mod(1, 13)*x + Mod(6, 13) 1]\n",
       "\n",
       "[Mod(1, 13)*x + Mod(7, 13) 1]\n",
       "\n",
       "[Mod(1, 13)*x + Mod(9, 13) 1]\n"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factor((x^4+4)*Mod(1,13))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Numerical integration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "   realprecision = 38 significant digits\n"
     ]
    }
   ],
   "source": [
    "\\p38"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.25000000000000000000000000000000000000"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "intnum(x=0,1,1/(1+x^2))/Pi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.16666666666666666666666666666666666667"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sumnum(n=1,1/n^2)/Pi^2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.22579135264472743236309761494744107198"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sumalt(n=1,(-1)^n*log(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.5707963267948966192313216916397514427"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "exp(2*%)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Comprehension"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[n^2|n<-[1..10]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 9, 25, 49]"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[n^2|n<-[1..10],isprime(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "[a,b] = [1,2];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a=1 b=2\n"
     ]
    }
   ],
   "source": [
    "print(\"a=\",a,\" b=\",b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Programming in GP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "dist(a,b) = sqrt(a^2+b^2);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.2360679774997896964091736687312762354"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dist(1,2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In a GP file, line ending terminates the line\n",
    "unless the they are preceded by `=` or `\\` or are in a section delimited by braces:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(a,b)->if(abs(a)>abs(b),print(a),print(b))"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cmpz(a,b) = if (abs(a)>abs(b), print(a), print(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(a,b)->if(abs(a)>abs(b),print(a),print(b))"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cmpz(a,b) =\n",
    "  if (abs(a)>abs(b), print(a), print(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(a,b)->if(abs(a)>abs(b),print(a),print(b))"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cmpz(a,b) = if (abs(a)>abs(b), \\\n",
    "              print(a), \\\n",
    "              print(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(a,b)->if(abs(a)>abs(b),print(a),print(b))"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cmpz(a,b) =\n",
    "{\n",
    "  if (abs(a)>abs(b),\n",
    "    print(a)\n",
    "   ,print(b))\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example of a function\n",
    "\n",
    "- Put the opening brace on the line after the `=` sign.\n",
    "- End the function by a semicolon.\n",
    "- Declare any local variables with `my()`.\n",
    "- Do not declare the loop index: it is local to the loop anyway.\n",
    "- The function return value is the last computed value.\n",
    "- Indent you code following the example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "fibo(n)=\n",
    "{\n",
    "  my(u0=0,u1=1);\n",
    "  for(i=2,n,\n",
    "    [u0,u1]=[u1,u0+u1]);\n",
    "  u1;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "354224848179261915075"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fibo(100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## While loop"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "rho(n)=\n",
    "{\n",
    "  my(x=2,y=5);\n",
    "  while(gcd(y-x,n)==1,\n",
    "      x=(x^2+1)%n;\n",
    "      y=(y^2+1)%n; y=(y^2+1)%n\n",
    "      );\n",
    "  gcd(n,y-x);\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "274177"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rho(2^64+1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Control flow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "wieferich(n)=\n",
    "{\n",
    "  forprime(p=2,n,\n",
    "    if(Mod(2,p^2)^(p-1)==1,\n",
    "      return(p)));\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "wieferich2(n)=\n",
    "{\n",
    "  my(r);\n",
    "  forprime(p=2,n,\n",
    "    if(Mod(2,p^2)^(p-1)==1,r=p;break));\n",
    "  r;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1093"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "wieferich(10000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1093"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "wieferich2(10000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Constructors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1/2, 1/3, 1/4, 1/5, 1/6, 1/7, 1/8, 1/9, 1/10]"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "V=vector(10,i,1/i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1/2, 1/3, 1/4, 1/5, 1/6, 1/7, 1/8, 1/9, 1/10]"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[1/i|i<-[1..10]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\n",
       "[1 2  3  4]\n",
       "\n",
       "[2 4  6  8]\n",
       "\n",
       "[3 6  9 12]\n",
       "\n",
       "[4 8 12 16]\n"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M=matrix(4,4,i,j,i*j)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## forvec\n",
    "\n",
    "Instead of"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 77, 80]"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s3(n)=\n",
    "{\n",
    "  my(m=sqrtint(n));\n",
    "  for (i=1,m,\n",
    "    for (j=1,m,\n",
    "      for (k=1,m,\n",
    "        if (i^2+j^2+k^2==n,\n",
    "          return([i,j,k])))));\n",
    "}\n",
    "s3(12345)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "use `forvec`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 77, 80]"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s3(n)=\n",
    "{\n",
    "  my(m=sqrtint(n));\n",
    "  forvec(v=vector(3,i,[1,m]),\n",
    "    if (v*v~==n,\n",
    "      return(v)));\n",
    "}\n",
    "s3(12345)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For a better algorithm, see `qfsolve`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Associative arrays"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "birthday(n)=\n",
    "{\n",
    "  my(M = Map());\n",
    "  for(i=1,oo,\n",
    "    my(x=random(n), j);\n",
    "    if(mapisdefined(M,x,&j),\n",
    "      return([i,j]));\n",
    "    mapput(M,x,i));\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[23001, 18881]"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "birthday(2^30)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Algebraic Number Theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Irreducibility\n",
    "\n",
    "In GP, we describe a number field $K$ as $K = Q[x]/f(x)$ where $f \\in \\mathbb{Z}[x]$\n",
    "is a monic irreducible polynomial."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x^4 - 2*x^3 + x^2 - 5"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f = x^4 - 2*x^3 + x^2 - 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "polisirreducible(f)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "GP knows cyclotomic polynomials:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x^8 + x^7 - x^5 - x^4 - x^3 + x + 1"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g = polcyclo(30)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Polmod\n",
    "\n",
    "To perform simple operations in $K = \\mathbb{Q}[x]/f(x) = \\mathbb{Q}(\\alpha)$ where $f(\\alpha) = 0$, we can use `Mod`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Mod(3*x^3 - 2*x^2 + 5*x + 10, x^4 - 2*x^3 + x^2 - 5)"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Mod(x,f)^5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Interpretation: $\\alpha^5 = 3 \\alpha^3 - 2 \\alpha^2 + 5 \\alpha + 10$.\n",
    "We check that the roots of $g$ are 30th roots of unity:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lift(Mod(x,g)^15)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We used lift to make the output more readable."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## polredbest\n",
    "\n",
    "Sometimes we can find a simpler defining polynomial for the same number field by using `polredbest`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [],
   "source": [
    "h = x^5 + 7*x^4 + 22550*x^3 - 281686*x^2 - 85911*x + 3821551;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x^5 - x^3 - 2*x^2 + 1"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "polredbest(h)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Interpretation: $\\mathbb{Q}[x]/h(x) \\cong \\mathbb{Q}[x]/(x^5 - x^3 - 2 x^2 + 1)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## nfinit and precomputed information\n",
    "\n",
    "Most operations on number fields require a precomputation, which is performed by the initialisation function `nfinit`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [],
   "source": [
    "K = nfinit(f);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`K` contains the precomputation of the number field `K = \\mathbb{Q}[x]/f(x)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x^4 - 2*x^3 + x^2 - 5"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    " K.pol"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 1]"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "K.sign"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`K` has signature `(2, 1)`: it has two real embeddings and one pair of conjugate complex embeddings."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1975"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "K.disc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1/2*x^2 - 1/2*x - 1/2, x, 1/2*x^3 - 1/2*x^2 - 1/2*x]"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "K.zk"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1/2*x^2 - 1/2*x - 1/2"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "w = K.zk[2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "K has discriminant $-1975$, and its ring of integers is\n",
    "$$\n",
    "\\mathbb{Z}_K = \\mathbb{Z} + \\mathbb{Z}\\frac{\\alpha^2 - \\alpha - 1}{2} + \\mathbb{Z}\\alpha + \\mathbb{Z}\\frac{\\alpha^3 -\\alpha^2 - \\alpha}{2}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "PARI/GP",
   "language": "gp",
   "name": "pari_jupyter"
  },
  "language_info": {
   "file_extension": "gp",
   "mimetype": "text/x-pari-gp",
   "name": "gp"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}