{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math \n",
    "import numpy as np\n",
    "import time\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Affichage de A et B\n",
      "[[1 2 4]\n",
      " [5 6 7]]\n",
      "[[  10]\n",
      " [ 100]\n",
      " [1000]]\n",
      "Taille de A\n",
      "(2, 3)\n",
      "Récupérer l'élément de A sur la 1ère ligne et 2ème colonne\n",
      "2\n",
      "Multiplication de A et B\n",
      "[[4210]\n",
      " [7650]]\n",
      "[[4210]\n",
      " [7650]]\n",
      "Récupérer la première ligne de A\n",
      "[1 2 4]\n",
      "[1 2 4]\n",
      "Récupérer la 2ème colonne de A (sous forme de tableau-ligne)\n",
      "[2 6]\n",
      "Récupérer la 2ème colonne de A (sous forme de tableau-colonne)\n",
      "[[2]\n",
      " [6]]\n"
     ]
    }
   ],
   "source": [
    "### Rappel sur les matrices (vues comme tableau) ###\n",
    "\n",
    "A = np.array([[1,2,4],[5,6,7]]) # définition de la matrices\n",
    "B = np.array([[10],[100],[1000]])\n",
    "\n",
    "print(\"Affichage de A et B\")\n",
    "print(A), print(B)\n",
    "\n",
    "print(\"Taille de A\")\n",
    "print(A.shape) # renvoie la taille de la matrices, ici 2 x 3\n",
    "\n",
    "print(\"Récupérer l'élément de A sur la 1ère ligne et 2ème colonne\")\n",
    "print(A[0,1])  # Attention, la numérotation commence à 0\n",
    "\n",
    "print(\"Multiplication de A et B\")\n",
    "print(A@B)  # Mutliplication de A et B (attetion, ne PAS Utiliser A*B)\n",
    "print(np.dot(A,B)) # commande alternative pour faire la multiplication\n",
    "\n",
    "# Pour l'addition de matrices de même taille, utiliser simplement l'opération +\n",
    "\n",
    "print(\"Récupérer la première ligne de A\")\n",
    "print(A[0, :])\n",
    "print(A[-2, :])\n",
    "\n",
    "print(\"Récupérer la 2ème colonne de A (sous forme de tableau-ligne)\")\n",
    "print(A[:, 1])  # Attention, cela renvoie un tableau en ligne...\n",
    "\n",
    "print(\"Récupérer la 2ème colonne de A (sous forme de tableau-colonne)\")\n",
    "print(A[:, 1:2]) \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "# On renvoie un couple d, [u,v] où d=pgcd(a,b) et ua+bv = d\n",
    "\n",
    "def Euclide(a,b):\n",
    "    X=np.array([[a],[b]])          # vecteur colonne (a,b)\n",
    "    P=np.array([[1,0],[0,1]])      # Matrice identité\n",
    "    if a<b:  \n",
    "        X=np.array([[b],[a]])      # Si a et plus petit que b on les inverse\n",
    "        P=np.array([[0,1],[1,0]])  # Matrice pour inverser a et b par laquel il faudra multiplier\n",
    "    while X[1,0]!=0:               # On boucle tant qu'on n'a pas atteint le vecteur (d,0) (qui signifie la fin de l'algo)\n",
    "        Q=np.array([[0, 1], [1,-(X[0,0]//X[1,0])]])\n",
    "        X= Q@X                     # On remplace le vecteur (a,b) par (b,a-bq) où q est le quotient de a par b\n",
    "        P = Q@P                    # On garde en mémoire le produit matriciel pour pouvoir avoir les coeff de Bézout à la fin \n",
    "    return X[0,0], P[0,:]         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, array([ 3, -2]))"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Euclide(5,7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Version récursive de Euclide\n",
    "\n",
    "# On commence par définir une fonction intermédiaire\n",
    "# Entrée : vecteur X = (a,b) et matrice P\n",
    "# Sortie : renvoie Y=(b,r) (où r est le reste de la division de a par b) et P mise à jour\n",
    "\n",
    "def EuclideRecInter(X,P):\n",
    "    if X[1,0]==0:                 # On arrête l'algo quand X est de la forme (d,0)\n",
    "        return X[0,0],P[0,:]\n",
    "    else:\n",
    "        if X[0,0]<X[1,0]:        # Si a et plus petit que b on les inverse\n",
    "            P=np.array([[0,1],[1,0]])@P\n",
    "            X = P@X\n",
    "        Q=np.array([[0, 1], [1,-(X[0,0]//X[1,0])]])\n",
    "        return EuclideRecInter(Q@X, Q@P)\n",
    "\n",
    "def EuclideRec(a,b):\n",
    "    X=np.array([[a],[b]])          # vecteur colonne (a,b)\n",
    "    P=np.array([[1,0],[0,1]])      # On initialise P\n",
    "    return EuclideRecInter(X,P)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, array([ 3, -2]))"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "EuclideRec(5,7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ExpNaive(a,n,N): #Calcul naïf de a^n modulo N\n",
    "    p=1\n",
    "    i=0\n",
    "    while i<n:\n",
    "        p=(p*a)%N\n",
    "        i=i+1\n",
    "    return p  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Version récursive de ExpNaive\n",
    "\n",
    "def ExpNaiveRec(a,n,N): \n",
    "    if n==0:\n",
    "        return 1\n",
    "    else:\n",
    "        return a*ExpNaiveRec(a,n-1,N)%N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "print(ExpNaive(2,57,23))\n",
    "print(ExpNaiveRec(2,57,23))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Base(n,b): #Ecriture de n en base b\n",
    "    L=[]\n",
    "    while n>0:\n",
    "        L=L+[n%b]\n",
    "        n=n//b\n",
    "    return L   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Version récursive de Base\n",
    "\n",
    "def BaseRec(n,b):\n",
    "    if n==0:\n",
    "        return []\n",
    "    return [n%b]+BaseRec(n//b,b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 1]\n",
      "[1, 2, 1]\n"
     ]
    }
   ],
   "source": [
    "print(Base(16,3))\n",
    "print(BaseRec(16,3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ExpRapide(a,n,N): #Calcul de a^n modulo N par exponentiation rapide. \n",
    "    L=Base(n,2)       # On récupère l'écriture en base 2 de n\n",
    "    P=[a%N]           # On initialise en prenant a mod N\n",
    "    i=0\n",
    "    while i<len(L)-1: #Calcul des carrés itérés de a modulo N : [a, a², a⁴,a⁸,a¹⁶...]\n",
    "        b=(P[i]*P[i])%N\n",
    "        P=P+[b]\n",
    "        i=i+1\n",
    "    p=1\n",
    "    for i in range(len(L)): #Calcul le produit des carrés itérés de a associés aux coefficients non nuls de L\n",
    "        if L[i]!=0:\n",
    "            p=(p*P[i])%N\n",
    "    return p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ExpRapide(12,20,14)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Version récursive de l'exponentiation rapide\n",
    "def ExpRapideRec(a,n,N):\n",
    "    if n == 0:\n",
    "        return 1%N\n",
    "    x = ExpRapideRec(a,n//2,N)\n",
    "    if n%2 == 0:\n",
    "        return x*x%N\n",
    "    else:\n",
    "        return a*x*x%N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ExpRapideRec(12,20,14)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "Temps de calcul de ExpNaive\n",
      "0.4834597110748291\n"
     ]
    }
   ],
   "source": [
    "# Temps de calcul de ExpNaive\n",
    "\n",
    "start=time.time()\n",
    "print(ExpNaive(2,4967296,4967297))\n",
    "end=time.time()\n",
    "print(\"Temps de calcul de ExpNaive\")\n",
    "print(end-start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "Temps de calcul de ExpRapide\n",
      "0.0003752708435058594\n"
     ]
    }
   ],
   "source": [
    "# Temps de calcul de ExpRapide\n",
    "\n",
    "start=time.time()\n",
    "print(ExpRapide(2,4967296,4967297))\n",
    "end=time.time()\n",
    "print(\"Temps de calcul de ExpRapide\")\n",
    "print(end-start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "Temps de calcul de ExpRapideRec\n",
      "0.00042176246643066406\n"
     ]
    }
   ],
   "source": [
    "# Temps de calcul de ExpRapideRec\n",
    "\n",
    "start=time.time()\n",
    "print(ExpRapideRec(2,4967296,4967297))\n",
    "end=time.time()\n",
    "print(\"Temps de calcul de ExpRapideRec\")\n",
    "print(end-start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "65537 4294967297\n"
     ]
    }
   ],
   "source": [
    "F4=2**(2**4)+1\n",
    "F5=2**(2**5)+1\n",
    "print(F4,F5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2^(F4-1) mod F4\n",
      "1\n",
      "2^(F5-1) mod F5\n",
      "3029026160\n",
      "F5 n'est pas premier\n",
      "En effet, d'après le petit théorème de Fermat:\n",
      "Si p est premier alors a^(p-1) = 1 mod p pour tout a qui n'est pas un multiple de p\n"
     ]
    }
   ],
   "source": [
    "print(\"2^(F4-1) mod F4\")\n",
    "print(ExpRapide(2,F4-1,F4))\n",
    "print(\"2^(F5-1) mod F5\")\n",
    "print(ExpRapide(3,F5-1,F5))\n",
    "print(\"F5 n'est pas premier\")\n",
    "print(\"En effet, d'après le petit théorème de Fermat:\")\n",
    "print(\"Si p est premier alors a^(p-1) = 1 mod p pour tout a qui n'est pas un multiple de p\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}