{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "4b6ddcad",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "# TP noté\n",
    "\n",
    "Ce TP est constitué de deux exercices indépendants. Une case de réponse est prévue pour chaque question. **Pour les questions « *Vérifier que …* », le code qui permet la vérification fait partie de la réponse et sera évalué. Cette vérification peut consister en un simple affichage de valeurs.**\n",
    "\n",
    "Par sécurité, merci d'indiquer vos prénom et nom dans la case ci-dessous :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "dea8d058",
   "metadata": {
    "tags": [
     "sujet"
    ]
   },
   "outputs": [],
   "source": [
    "# Prénom Nom : "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "666533d3",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "## Exercice 1 : Logarithme discret\n",
    "\n",
    "Le but de cet exercice est d'implanter, à l'aide des fonctions et classes de SageMath, quelques algorithmes de calcul de logarithme discret dans $ℤ/pℤ$. On rappelle qu'étant donné un générateur $g$ de $ℤ/pℤ$ et $h\\in ℤ/pℤ^×$, le logarithme discret de $h$ en base $g$ est l'unique entier $k< p$ tel que $g^k = h$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "86774d6c",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "0. On va effectuer les tests dans deux anneaux : $ℤ/p_1ℤ$ avec $p_1 = 65537$ et $ℤ/p_2ℤ$ avec $p_2 = 940026341$. Effectuer le travail suivant dans la cellule ci-dessous :\n",
    "    - définir `p1` et `p2` (avec les valeurs ci-dessus),\n",
    "    - définir les anneaux `Zp1` (pour $ℤ/p_1ℤ$) et `Zp2` (pour $ℤ/p_2ℤ$),\n",
    "    - calculer les générateurs `g1` de $ℤ/p_1ℤ^×$ et `g2` de $ℤ/p_2ℤ^×$,\n",
    "    - *vérifier que $g_1 = 3$ et $g_2 = 2$.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "73e5036e",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "08dc6979",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "1.  Écrire une fonction `log_naif(h,g,p)` qui prend en entrée $h\\in ℤ/pℤ^×$, un générateur $g$ de $ℤ/pℤ^×$ et $p$, et renvoie le logarithme discret de $h$ en base $g$. *L'algorithme consiste à essayer tous les exposants possibles à partir de $k = 0$.*\n",
    "    \n",
    "    Tester la fonction dans `Zp1` avec $h = 123$. *Vérifier le résultat avec la méthode `log` des éléments de $ℤ/pℤ$.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "12e99622",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "ac47cd3d",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "2. On s'intéresse maintenant à un algorithme plus rapide. Si on connaît la factorisation $p-1 = \\prod_{i=1}^k q_i^{e_i}$, on note $f_i = q_i^{e_i}$. Pour $i = 1$ à $k$, on calcule $g_i = g^{(p-1)/f_i}$, $h_i = h^{(p-1)/f_i}$ et le logarithme $n_i$ de $h_i$ en base $g_i$. On renvoie alors l'unique entier $n$ tel que $n≡_{f_i} n_i$ pour tout $i$.\n",
    "\n",
    "     - Utiliser la méthode `factor` des entiers pour écrire un algorithme `facteurs(p)` qui renvoie la liste des $f_i$. *`facteurs(21)` doit renvoyer `[4,5]`.*\n",
    "    \n",
    "     -  Écrire une fonction `log_restes(h,g,p)` qui calcule le logarithme discret de $h$ en base $g$ dans $ℤ/pℤ^×$ à l'aide de l'algorithme décrit ci-dessus. *Les calculs des $n_i$ sont effectués avec la fonction `log_naif`. Le calcul de $n$ peut se faire avec la fonction `crt(N, F)` qui, étant donné la liste des $n_i$ et la liste des $f_i$, calcule $n$.*\n",
    "    \n",
    "     -  Tester la fonction dans `Zp2` avec $h = 150251$. *Vérifier le résultat avec la méthode `log`.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "14256a8f",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "f7da0cd8",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "2c6d497d",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "7c9f9e2d",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "## Exercice 2 : évaluation et interpolation\n",
    "\n",
    "Un polynôme sur un corps $𝕂$ est une expression de la forme $P = p_0 + p_1x+p_2x²+\\dotsc+p_kx^k$. Son *degré* est $k$ si $p_k≠0$. L'évaluation de $P$ en $α\\in𝕂$ est $p(α) = \\sum_{i=0}^k p_iα^i$. Si on a $(k+1)$ points $α_0$, …, $α_k$, les $(k+1)$ évaluations $P(α_0)$, …, $P(α_k)$ peuvent s'obtenir comme le produit matrice-vecteur avec une matrice de Vandermonde :\n",
    "$$\\begin{pmatrix} P(α_0) & P(α_1) & \\dotsc & P(α_k)\\end{pmatrix} = \n",
    "\\begin{pmatrix}\n",
    "    1 & α_0 & α_0² & \\dotsc & α_0^k\\\\\n",
    "    1 & α_1 & α_1² & \\dotsc & α_1^k\\\\\n",
    "    \\vdots&\\vdots&\\vdots&&\\vdots\\\\\n",
    "    1 & α_k & α_k² & \\dotsc & α_k^k\n",
    "    \\end{pmatrix}\\cdot\\begin{pmatrix}p_0\\\\p_1\\\\\\vdots\\\\p_k\\end{pmatrix}.$$\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bb5d3c1e",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "1.  Écrire une fonction `Vandermonde(A)` qui renvoie la matrice de Vandermonde de dimension $(k+1)×(k+1)$ construite avec les $(k+1)$ éléments de la liste `A`. \n",
    "\n",
    "    *Vérifier que `Vandermonde([1,2,3])` renvoie la matrice $\\left(\\begin{smallmatrix} 1 & 1 & 1\\\\1 & 2 & 4\\\\1 & 3 & 9\\end{smallmatrix}\\right)$.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "91ca4dfb",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "ed530f53",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "2. Écrire une fonction `Evaluation(P, A)` qui prend en entrée le vecteur $(p_0,…,p_k)$ des coefficients d'un polynôme $P = \\sum_{i=0}^k p_i x^i$ et une liste de $(k+1)$ points $α_0$, …, $α_k$ et renvoie le vecteur des évalués $(P(α_0), …, P(α_k))$.\n",
    "\n",
    "   *Vérifier que les évalués du polynôme $P = 6x^5 + 5x^4 +4x^3 + 3x^2 + 2x + 1$ sur les points $0$, $1$, $2$, $3$, $4$, $5$ sont $(1, 21, 321, 2005, 7737, 22461)$.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "74bfd417",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "8811a1ec",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "3.  À l'inversion, la matrice de Vandermonde permet d'effectuer une *interpolation* : étant donnés $α_0$, …, $α_k$ (tous distincts) et $β_0$, …, $β_k$, l'objectif est de trouver l'unique¹ polynôme $P$ de degré $≤ k$ tel que $P(α_i) = β_i$ pour $0 ≤ i ≤ k$. En traduisant le problème en terme d'algèbre linéaire, écrire une fonction `Interpolation(A, B)` qui, étant donné les $α_i$ et les $β_i$, calcule le vecteur des coefficients de ce polynôme $P$. *On peut utiliser les méthodes disponibles pour les matrices pour résoudre un système linéaire `solve_left` ou `solve_right`.*\n",
    " \n",
    "    *Vérifier, avec `A = [-3,-2,-1,0,1,2,3]` et des valeurs aléatoires pour `P`, que `Interpolation(Evaluation(P, A), A)` renvoie toujours `P`. Attention à la taille que doit avoir `P`.*\n",
    "    \n",
    "¹ On admet ici l'existence et l'unicité de $P$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "a1d358ed",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "1fabbdc7",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "4.  La méthode des moindres carrés est une interpolation *approximative* : étant donné $α_0$, …, $α_k$ (distincts) et $β_0$, …, $β_k$ et un entier $d ≤ k$, on cherche le polynôme $Q$ de degré $d$ qui passe *au plus près* des points $(α_i, β_i)$. L'algorithme pour calculer $Q$ consiste à calculer une matrice de Vandermonde *tronquée* $V$ de $k$ lignes et $d$ colonnes (chaque ligne s'arrête à $α^d$), et à résoudre le système $V^⊤⋅V⋅\\vec q = V^⊤⋅\\vec b$ où $V^⊤$ est la transposée de $V$, $\\vec q$ est le vecteur des coefficients de $Q$ et $\\vec b$ le vecteur $(β_0, …, β_k)$. \n",
    "\n",
    "    Écrire une fonction `MoindresCarres(A, B, d)` qui implante cet algorithme. *Par exemple, `MoindresCarres([0,1,2,3],[-2,6,4,7],2)` doit renvoyer  $(-5/4,25/4,-5/4)$.*\n",
    "    \n",
    "    *Vérifier que `MoindresCarres(A, B, k)` renvoie le même résultat que `Interpolation(A, B)` si `A` et `B` sont de longueur $k+1$.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "5af1e39d",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "22874ffc",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.5",
   "language": "sage",
   "name": "sagemath"
  },
  "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.10.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}