{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# **L3 Algèbre effective — TP 2  du mardi 1er octobre 2019**\n",
    " \n",
    "## **Factorisation d'entiers et cryptographie RSA**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "## I-Factorisation d'entiers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "La question de factorisation des entiers est au coeur de nombreux problèmes mathématiques. En sage, on dispose de la commande *factor*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2^3 * 7"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factor(56)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Le résultat est certes joli, mais en pratique on veut souvent réutiliser le résultat. Pour cela, on peut le convertir en liste."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(2, 3), (7, 1)]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f=factor(56);\n",
    "list(f)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Sage est très fort et sait factoriser rapidement de grands entiers. Faire quelques tests."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3^3 * 7 * 18617 * 25903 * 109718138717586334693746452264738879049551083759485526527666012559172300736346190914361603"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factor(10^100+17)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "**Exercice.** Pour voir que ce n'est pas si facile d'aller aussi vite, écrire vous même un algorithme de factorisation naïf (en testant les divisions successives). \n",
    "\n",
    "**N.B.** Naïf ne veut pas dire qu'on ne peut pas être malin. Pensez notamment aux bornes des diviseurs à tester!\n",
    "\n",
    "Pour alléger votre code, vous pouvez ne pas regrouper les facteurs multiples."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def factorise(n):\n",
    "    return []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Jusqu'à quelle taille d'entiers arrive t-on à factoriser?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# II- Nombres premiers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Une question liée à la précédente est celle du test de primalité. On a vu en cours que le critère de Fermat permet de montrer que certains entiers ne sont pas premiers sans avoir à exhiber une factorisation explicite. On se propose de tester cette méthode."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Avant de commencer: à votre avis, quelle différence fondamentale y a t-il entre les deux calculs suivants qui explique la différence de temps d'exécution?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 40 ms, sys: 0 ns, total: 40 ms\n",
      "Wall time: 40.8 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "40697"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "time(254^977821 %977821)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 4 ms, sys: 0 ns, total: 4 ms\n",
      "Wall time: 2.48 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "40697"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "time(Mod(254,977821)^977821)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Qu'en déduit-on sur 977821?\n",
    "\n",
    "Ecrire une fonction *Fermat(a,n)* qui renvoie vrai si $a$ vérifie la propriété de Fermat dans $\\mathbf Z/n\\mathbf Z$ et faux sinon."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def Fermat(a,n):\n",
    "    return true"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Fermat(4,97)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "On décide de procéder comme suit: pour décider si $n$ est pseudo-premier, on tire au hasard 5 éléments de $\\mathbf Z/n\\mathbf Z$ et on teste s'ils vérifient la propriété de Fermat. S'ils passent tous le test, on le déclare pseudopremier (avec une certaine probabilité)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "randint?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def pseudo_prem(n):\n",
    "    return true"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Faîtes quelques tests. Comparer par exemple la liste des nombres \"pseudo-premiers\"$\\leq 1000$ que vous trouvez ainsi avec la liste des nombres premiers que Sage peut vous donner."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "P=Primes()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "[P[i] for i in range (200) if P[i]<1000];"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "**N.B:** Au début des années 2000, 3 étudiants indiens de votre âge ont montré qu'il existe un algorithme polynomial permettant de tester si un entier est premier ou non. *\"Primes is in P.\"* "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# III- Fonction d'Euler"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "On note $\\varphi$ la fonction d'Euler. Ainsi $\\varphi(n)$ compte le nombre d'éléments inversibles de $\\mathbf Z/n\\mathbf Z$.\n",
    "\n",
    "Ecrire une fonction *phi* qui calcule cette valeur à partir d'une factorisation de $n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def phi(n):\n",
    "    f=factor(n)\n",
    "    return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Parfois, on peut être amené à avoir besoin de la liste de tous les éléments de $(\\mathbf Z/n \\mathbf Z)^\\times$. \n",
    "\n",
    "Ecrire une fonction *liste_inversibles(n)* qui renvoie la liste des inversibles de $\\mathbf Z/n \\mathbf Z$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def liste_inversibles(n):\n",
    "    return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# IV- Cryptographie RSA"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Pour coder un message avec RSA, il faut d'abord convenir d'une façon de représenter les messages par des nombres qu'on pourra ensuite crypter en utilisant RSA. Pour simplifier, on se limite à des messages n'utilisant que les lettres \"a\", \"b\",... \"z\" et \" \"(l'espace). Donc PAS DE MAJUSCULES, d'ACCENTS, etc...\n",
    "\n",
    "On a ainsi 27 caractères, qu'on associe aux entiers de 0 à 26 comme suit:\n",
    "a=1, b=2, .., z=26, \" \"=0. Il est alors naturel d'encoder une chaîne de caractères par l'entier correspond en base 27.\n",
    "Ainsi, le mot \"abc\" est encodé par l'entier $1\\times 27^2+2\\times 27+3$.\n",
    "\n",
    "En SAGE, une chaîne de caractères (*string*) est une liste de lettres auxquelles on peut accéder comme dans une liste. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "mot=\"a sjkg hdfjkg\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('g', ' ', 'a')"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mot[5], mot[1],mot[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "On peut renvoyer le code ascii de chaque lettre grâce à la fonction *ord()*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(97, 98, 32)"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ord('a'), ord(\"b\"), ord(' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "On donne donc les fonctions *Lettreanombre()* et *nombrealettre()* suivantes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def lettreanombre(l):\n",
    "    if l==' ':\n",
    "        return 0\n",
    "    else:\n",
    "        return ord(l)-96"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(5, 26)"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lettreanombre('e'), lettreanombre(\"z\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def nombrealettre(n):\n",
    "    if n==0:\n",
    "        return ' '\n",
    "    else:\n",
    "        return chr(n+96)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "' '"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nombrealettre(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Ecrire une fonction *encode()* qui prend une chaîne de caractère et l'encode selon le principe précédent."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def encode(s):\n",
    "    return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "encode(\"abc\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Ecrire une fonction *decode()* qui fait l'inverse. (N.B.:on peut concaténer des lettres grâce à +: 'a' +'b'=\"ab\")."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def decode(n):\n",
    "    return \"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "On en vient à RSA proprement dit. Codez la phrase: \"l algebre effective c est trop cool\".\n",
    "On devrait trouver 55670025528737887382431553890564338447362361699750 (il y a 50 chiffres)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "49.74562142046245220169257439339368880257399335373"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "log(55670025528737887382431553890564338447362361699750.,10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Voici ma clé RSA que je donne à tout le monde: *cle* est le produit de deux nombres premiers que je tiens secret mais dont je donne le produit et *exp* est un exposant que j'ai choisi pour être premier avec $\\varphi(cle)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "cle=51564215854895166241100000000000035579308939877664706359"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "exp=6753790093096013771"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Envoyez moi la phrase précédente codée. Vous devriez trouver:'qixllymaugladgrhwmyeiakpqosmqdkhmfxsszp'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Je n'ai pas été très malin, ma clé n'a que 55 chiffres. C'est trop peu. Vous pouvez décoder les messages que vous interceptez en utilisant judicieusement l'ordinateur. Faîtes le avec le message suivant:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "message=\"fihhn kir merxmxlbzsqkyvcvpecldodleohxy\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "À vous de vous créer une clé publique et un exposant. Il vous faut pour cela trouver 2 nombres premiers grands. Faîtes le."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "next_prime?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A partir de là, comment calculer $\\varphi(n)$ et trouver un exposant premier à $\\varphi(n)$?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Je me suis finalement rendu compte que vous lisiez mon courrier (au passage, ça vous fait moins 5 points!) et j'ai augmenté la taille de ma clé secrète (environ 200 chiffres). Du coup, je me suis dit que je pouvais économiser sur la taille de l'exposant (ça fait moins de calculs pour chiffrer un message)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "cle=34999999999999999999999999999999999999999999999999999999999999999999999943580545084716072139932442339500000000000000000000000000000000000000000000000821260436490287444342737236448339920284176974726843"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "exp=3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Montrez que ce n'est pas une bonne idée. Déchiffrez le message suivant (que vous conjecturez n'être pas trop long.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "message='lcyjtiklnclxgnttwtiuilfgvpaloynzsaadvzdbmpogcjnzxn  qgczihpvlclpvaosnmcyymflgazzoswlggiifafhz kq'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 7.5.1",
   "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": 0
}