{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "23a158bb-576b-4376-8d1c-ad0d39285875",
   "metadata": {},
   "source": [
    "# Introduction à Sage"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b576e74e-53fe-44db-b714-a161d6abda6a",
   "metadata": {},
   "source": [
    "## 1.Bases "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "b8818354-f1c8-47a7-9454-90dff3e8c20b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1000"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2 + 3\n",
    "5 * 7\n",
    "10 / 3\n",
    "10^3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "36dbdc4f-93d2-49f9-8814-512e8a8efed0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(5, 7, 9)"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "v = vector([1, 2, 3])\n",
    "w = vector([4, 5, 6])\n",
    "v + w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "b6daa746-0447-49c1-bf27-f62887730e44",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[  -2    1]\n",
       "[ 3/2 -1/2]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = matrix([[1, 2], [3, 4]])\n",
    "A.det()\n",
    "A.inverse()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "8997cbe4-aa06-4820-a9bf-6b9e5ed5e21c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_prime(97)\n",
    "factor(360)\n",
    "gcd(84, 30)\n",
    "lcm(12, 18)\n",
    "Mod(3, 7)^100\n",
    "sqrt(36)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "5783a470-51f2-41a0-bf83-252cb94b3808",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "4\n",
      "9\n",
      "16\n",
      "2\n",
      "4\n",
      "6\n",
      "8\n",
      "10\n",
      "12\n"
     ]
    }
   ],
   "source": [
    "for i in range(5):\n",
    "    print(i^2)\n",
    "for k in [1..6]:\n",
    "    print(2*k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "2e9b6232-e733-497f-98ec-968bb7c49b99",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "26"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def f(x):\n",
    "    return x^2 + 1\n",
    "f(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "538b73a4-a578-4592-a67a-490193183af4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Liste=[]\n",
    "p=2\n",
    "Liste.append(p)\n",
    "Liste"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ea09c393-3583-4698-97c7-1f0f04bfe432",
   "metadata": {},
   "source": [
    "## Q. Écrire la fonction suivante en Sage:\n",
    "```\n",
    "fonction factorielle(n) :\n",
    "    p ← 1\n",
    "    pour k dans [1, n] :\n",
    "        p ← p * k\n",
    "    retourner p\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "9ba5f439-3c5e-4184-a99b-51abc54ac0ce",
   "metadata": {},
   "outputs": [],
   "source": [
    "def factorielle(n):\n",
    "    #TODO\n",
    "    return \"TODO\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "7bcda7e4-5ae0-4126-b907-023ed3a677c1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'TODO'"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factorielle(17)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c6db9cd-74c9-4ff6-bf69-a75e02c05635",
   "metadata": {},
   "source": [
    "### Q. Ecrire une fonction qui affiche les valeurs intermédiaires de la fonction précédente\n",
    "On pourra utiliser une liste qui se déclare comme suit `Liste=[]`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "6c64ba65-50f2-46b6-9763-2179462e74af",
   "metadata": {},
   "outputs": [],
   "source": [
    "def newfactorielle(n):\n",
    "    Liste=[]\n",
    "    #TODO\n",
    "    for k in [1..n]:\n",
    "        Liste.append(k)\n",
    "    return Liste"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "041cca56-54d7-4f51-8212-a6a8c6a339b5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 7]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "newfactorielle(7)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "de15e29c-aec0-4885-8126-a95562cb211d",
   "metadata": {},
   "source": [
    "## Primalité"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fa1e3d4a-1c7a-40d8-b0b5-cc117ca5b01f",
   "metadata": {},
   "source": [
    "Un entier naturel est dit **premier** s’il est supérieur ou égal à 2 et\n",
    "n’est divisible que par 1 et lui-même. Il existe une infinité de nombres premiers (preuve ?)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2b3374ef-ce67-47d9-a2f1-c977533d43f4",
   "metadata": {},
   "source": [
    "### Q. On considère la construction de nombre suivante :\n",
    "$2.3+1=...$\n",
    "\n",
    "$2.3.5+1=...$\n",
    "\n",
    "$2.3.5.7+1=...$\n",
    "\n",
    "$2.3.5.7.11+1=...$\n",
    "\n",
    "1) Peut-on affirmer que le résultat de ces calculs est forcément\n",
    "un nombre premier ?\n",
    "\n",
    "2) Considérons : $2.3.5.7.11.13+1$\n",
    "- Justifier qu’il n’est pas divisible par 2, 3, 5, 7, 11, 13\n",
    "- Mais n’est-il pas divisible par au moins un autre nombre premier ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f746f7a1-55de-4673-b877-aef55ba97a40",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "db082da2-98e5-4096-a567-5416b0697956",
   "metadata": {},
   "source": [
    "### Q. Démontrer que la proposition suivante est fausse : $$\\forall n\\in N, n^2-n+41 \\text{ est premier}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ed77a7ee-d6a2-40ed-87b1-57395e6e14a2",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "68b99a19-77ee-48fb-b396-671336ebb8f6",
   "metadata": {},
   "source": [
    "### Q. Écrire une fonction est_premier permettant de tester si un nombre est premier.\n",
    "Vous pourrez utilisez la fonction `mod(a,b)` qui donne le reste de la division de a par b. Essayez d'avoir une fonction optimisée..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "cc0ff461-17ba-46cb-b738-9a343fcaf80c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def est_premier(p):\n",
    "    #TODO\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "3832776e-1a4c-4833-b97e-187210098a6a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "est_premier(1322)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f2471db-7fe6-4c45-b6ee-7d63c34b5bfa",
   "metadata": {},
   "source": [
    "### [Hors TD] Implanter la fonction phi d'Euler\n",
    "On considère les nombres de 1 à n. Lister tous ces entiers qui sont premiers avec n. Donner ensuite le nombre d'entiers qui respectent cette condition (en utilisant `len`). On appelera par la suite cette fonction $\\varphi(n)$ et vous pourrez l'appeler avec `euler_phi()`. Nous utiliserons cette fonction pour le TP sur RSA."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "232c9f86-b595-4062-b197-d65a8f98c428",
   "metadata": {},
   "outputs": [],
   "source": [
    "def listpremier(n):\n",
    "    #TODO\n",
    "    return 42"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "1858f8fc-e58c-478e-9ecb-94eaaab27192",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "euler_phi(20)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a97b7393-2571-485b-87b8-caec2aa0c6a2",
   "metadata": {},
   "source": [
    "# Cryptographie Classique"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cec20748-c2fa-4a00-b9fc-995c07d12610",
   "metadata": {},
   "source": [
    "*Consignes Générales* : On écrit les messages en lettres majuscules, sans accents, ni espaces, ni ponctuation. Ceci a pour but de simplifier l’écriture de fonctions de chiffrement et le déchiffrement en `Sage`. Si vous êtes rapide, vous pourrez ensuite généraliser le traitement.\n",
    "\n",
    "On utilise la correspondance ci-dessous entre les lettres de l’alphabet $\\{A,B,C,\\ldots,Z\\}$ et les nombres $\\{0,1,2,\\ldots,25\\}$.\n",
    "\n",
    "| A | B | C | D | E | F | G | H | I | J | K | L | M |\n",
    "|---|---|---|---|---|---|---|---|---|---|---|---|---|\n",
    "| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |\n",
    "\n",
    "| N | O | P | Q | R | S | T | U | V | W | X | Y | Z |\n",
    "|---|---|---|---|---|---|---|---|---|---|---|---|---|\n",
    "| 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2f1fd6af-03c1-4fde-93ae-9badafeb0d2d",
   "metadata": {},
   "source": [
    "## 1. Une faille de sécurité"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "810afa35-b2a3-4c3f-a855-fa345ec11297",
   "metadata": {},
   "source": [
    "Le cryptogramme suivant a été obtenu à l’aide d’un chiffrement par décalage inconnu :\n",
    "\n",
    "**TZTVIFEVJKLEREV.**\n",
    "\n",
    "Un espion habile a réussi à découvrir que la lettre **S** est chiffrée par la lettre **J**.\n",
    "\n",
    "1. Écrivez deux fonctions `Sage` effectuant respectivement le chiffrement et le déchiffrement par décalage, à partir d’un message (une chaîne de caractères) et d’une clé de chiffrement (un nombre entier). Vous aurez peut-être l’usage des fonctions `ord()` et `chr()`.\n",
    "\n",
    "2. Décryptez le message proposé. Précisez quelles sont les clés de chiffrement et de déchiffrement correspondantes.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "afeab42f-559a-4315-b905-470e60a34f99",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "8406a2d2-ed35-4b63-addc-856ed616128d",
   "metadata": {},
   "source": [
    "3. On donne le message ci-dessous (écrit en anglais) chiffré avec un décalage inconnu. Retrouvez le message d'origine.\n",
    "   $$\\textsf{OVDTHUFWVZZPISLRLFZHYLAOLYL}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "53afdd58-2173-4c1d-9078-6d86d59675fc",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "005314b3-c89f-4662-a699-3a6601bade2e",
   "metadata": {},
   "source": [
    "## 2. Vigenère"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "228b6539-d74e-47b5-8936-0e64eee56343",
   "metadata": {},
   "source": [
    "Au seizième siècle, le diplomate français Blaise de Vigenère a conçu un chiffrement basé sur le chiffrement de César, mais dans lequel l’utilisation d’un mot-clé permet de changer à chaque lettre la valeur du décalage utilisé. Par exemple, si le mot-clé est `CESAR`, alors il faudra faire d’abord un décalage de 2, puis de 4, puis de 18, puis de 0 (la lettre `A` correspond à un décalage de 0) et enfin de 17 lettres vers la droite dans l’alphabet.\n",
    "\n",
    "Pour **chiffrer** la phrase `ESOPE RESTE ICI ET SE REPOSE`, qui est plus longue que le mot-clé, il faut recopier le mot-clé autant de fois que nécessaire pour avoir un décalage pour chaque lettre. Finalement, le chiffré est :\n",
    "\n",
    "`GWGPV TIKTV KGA EK UI JEGQWW`\n",
    "\n",
    "comme calculé dans le tableau ci-dessous.\n",
    "\n",
    "| clair :   | E | S | O | P | E | R | E | S | T | E | I | C | I | E | T | S | E | R | E | P | O | S | E |\n",
    "|-----------|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|\n",
    "| clé :     | C | E | S | A | R | C | E | S | A | R | C | E | S | A | R | C | E | S | A | R | C | E | S |\n",
    "| chiffré : | G | W | G | P | V | T | I | K | T | V | K | G | A | E | K | U | I | J | E | G | Q | W | W |\n",
    "\n",
    "Pour **déchiffrer**, il faut effectuer les décalages opposés avec le mot-clé.\n",
    "\n",
    "1. Écrivez une fonction `Sage` effectuant le chiffrement de Vigenère avec un message et un mot-clé passés en paramètre.  \n",
    "2. Écrivez la fonction de déchiffrement correspondante.  \n",
    "3. Chiffrez puis déchiffrez le message `JE NE PERDS JAMAIS, SOIT JE GAGNE, SOIT J'APPRENDS.` avec le mot-clé `SEPT`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a110aa1a-c985-4be6-91f4-3e3de20444a4",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "13375193-aae5-4d3c-a00e-4aeabc3abcee",
   "metadata": {},
   "source": [
    "# Sécurité des mots de passe\n",
    "Les mots de passe font partis des éléments importants de la sécurité informatique. Parmi les caractéristiques cruciales qui influent sur la solidité des mots de passe, il y a sa longueur. Voici quelques éléments qui permettent de mesurer l'effet d'un mot du nombre de caractères d'un mot de passe :\n",
    "- Sur un clavier standard, il y a $105$ caractères imprimables;\n",
    "- La vitesse du processeur d'un ordinateur actuel est de l'ordre de 3 GHz, ce qui signifie qu'il exécute environ $3$ milliards d'opérations à la seconde.\n",
    "- L'espérance de vie des humains est de $80$ ans environ.\n",
    "\n",
    "### Q. En considérant qu'un mot de passe est vérifié en une opération, calculer le nombre de caractères qu'il doit comporter pour que la durée d'une vie humaine ne suffise pas à le découvrir par recherche exhaustive avec un ordinateur actuel."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c81d401c-3ee4-42a1-ab9c-7ecba2445b71",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "d8a761e0-4fb8-4c7f-a653-2199013331bb",
   "metadata": {},
   "source": [
    "# [BONUS] Chiffrement Scytale\n",
    "Bruce a intercepté le message (en anglais) suivant :\n",
    "  \n",
    "$$\\mathsf{SUTSTRUISREERYNAOCTAOSCIIOPDTIPCS}$$\n",
    "\n",
    "Sachant que le message a été généré avec une scytale, retrouvez le\n",
    "message d'origine."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 10.7",
   "language": "sage",
   "name": "sagemath-10.7"
  },
  "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.13.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}