{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "a0711efe",
   "metadata": {},
   "source": [
    "# Séance 7 : factorisation d'entiers -- méthodes exponentielles\n",
    "\n",
    "\n",
    "Tout entier naturel $n \\ge 2$ peut se décomposer comme un produit de facteurs premiers élevés à une certaine puissance. Cette décomposition est uneique à l'ordre des facteurs près :\n",
    "\n",
    "$$\n",
    "    n = \\prod_{i=1}^k p_i^{e_i}\n",
    "$$\n",
    "\n",
    "où les $p_i$ sont premiers  et les $e_i$ sont des entiers strictement positifs.\n",
    "\n",
    "En informatique, on peut donc représenter une factorisation de $n$ comme un ditionnaire, où l'on associe à chaque $p_i$ sa valuation $e_i$.\n",
    "\n",
    "Par exemple, l'entier $n = 600 = 2^3 \\cdot 3 \\cdot 5^2$ peut être représenté par le dictionnaire"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "79088b48",
   "metadata": {},
   "outputs": [],
   "source": [
    "{ 2: 3, 3: 1, 5: 1}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "80a11440",
   "metadata": {},
   "source": [
    "## Exercice 1 : divisions successives\n",
    "\n",
    "Dans cet exercice, on utilise un algorithme \"naïf\" de factorisation, à l'aide de divisions successives.\n",
    "\n",
    "**Question 1.** Écrire une fonction `factorise_divisions(n)`, qui prend en entrée un entier $n \\ge 2$, et qui retourne sa décomposition en facteurs premuiers sous la forme d'un dictionnaire, comme présenté ci-dessus."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8aff630c",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "def factorise_divisions(n):\n",
    "    x = n\n",
    "    s = math.sqrt(n)\n",
    "    p = 2\n",
    "    facto = dict()\n",
    "    while x >= s:\n",
    "        while x % p == 0:\n",
    "            if p in facto:\n",
    "                facto[p] += 1\n",
    "            else:\n",
    "                facto[p] = 1\n",
    "            x //= p\n",
    "        p += 1\n",
    "    if x != 1:\n",
    "        if x in facto:\n",
    "            facto[x] += 1\n",
    "        else:\n",
    "            facto[x] = 1\n",
    "    return facto\n",
    "    \n",
    "for n in [8, 21, 101, 600]:\n",
    "    print(n, \":\", factorise_divisions(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c878914e",
   "metadata": {},
   "source": [
    "**Question 2.** Jusqu'à quelle valeur de $n$ (en orde de grandeur) l'algorithme prend-il moins d'une seconde ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b04f7288",
   "metadata": {},
   "outputs": [],
   "source": [
    "import time, random\n",
    "\n",
    "t = 0.0\n",
    "e = 3\n",
    "while t < 0.1:   # 0.1 sec. pour moi\n",
    "    n = random.randint(10**e, 10**(e+1))\n",
    "    t = time.time()\n",
    "    x = factorise_divisions(n)\n",
    "    t = time.time() - t\n",
    "    print(n, \":\", x)\n",
    "    e += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8209b298",
   "metadata": {},
   "source": [
    "## Exercice 2 : algorithme de Fermat\n",
    "\n",
    "\n",
    "Dans cet exercice, on utilise la méthode de Fermat pour factoriser un entier. L'algorithme est le suivant :\n",
    "\n",
    "**Entrée :** $n \\ge 3$ impair\n",
    "\n",
    "**Sortie :** deux diviseurs $a$ et $b$ de $n$\n",
    "\n",
    "1. Calculer $t = \\lceil \\sqrt{n} \\rceil$ et $c = t^2-n$.\n",
    "2. **Tant que** $c$ n'est pas un carré :\n",
    "   - $c \\leftarrow c + 2t + 1$\n",
    "   - $t \\leftarrow t+1$\n",
    "3. Calculer $s$ la racine carrée de $c$.\n",
    "4. Retourner $(t+s, t-s)$\n",
    "\n",
    "\n",
    "Ci-dessous vous est fournie une fonction de **calcul de racine carrée entière avec reste**, qui pour un entier $N$ en entrée, retourne un couple d'entier naturels $(X, R)$ tels que $N = X^2 + R$ et $0 \\le R < 2X+1$. Si $R = 0$, l'entier $N$ en entrée est donc un carré."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b496715d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def decomposition_base_4(N):\n",
    "    n = N\n",
    "    res = []\n",
    "    while n > 0:\n",
    "        res.append(n % 4)\n",
    "        n //= 4\n",
    "    return res\n",
    "\n",
    "def racine_carree_entiere(N):\n",
    "    decomp = decomposition_base_4(N)\n",
    "    d = len(decomp)\n",
    "    R = 0\n",
    "    X = 0\n",
    "    for j in range(d-1, -1, -1):\n",
    "        T = 4*R + decomp[j]\n",
    "        if T > 4*X:\n",
    "            R = T - 4*X - 1\n",
    "            X = 2*X+1\n",
    "        else:\n",
    "            R = T\n",
    "            X = 2*X\n",
    "    return X, R"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "611113ff",
   "metadata": {},
   "source": [
    "Vous pouvez également utiliser la fonction `isqrt` du module `math` de python.\n",
    "\n",
    "\n",
    "**Question 1.** Écrire une fonction `etape_fermat(n)`, qui prend en entrée un entier $n \\ge 3$ impair, et retourne deux diviseurs $a$ et $b$ de $n$ grâce à la méthode de Fermat."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "430fa0ce",
   "metadata": {},
   "outputs": [],
   "source": [
    "def etape_fermat(n):\n",
    "    t, r = racine_carree_entiere(n)\n",
    "    if r != 0:\n",
    "        t += 1\n",
    "    c = t**2 - n\n",
    "    s, r = racine_carree_entiere(c)\n",
    "    while r != 0:\n",
    "        c += 2*t +1\n",
    "        t += 1\n",
    "        s, r = racine_carree_entiere(c)\n",
    "    return [t+s, t-s]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "875458cb",
   "metadata": {},
   "source": [
    "Puis, on peut tester que la méthode fonctionne bien avec des entiers $n$ constitués de deux diviseurs $a$ et $b$ proches de $\\sqrt{n}$ :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "115b147f",
   "metadata": {},
   "outputs": [],
   "source": [
    "for e in range(3, 8):\n",
    "    a = random.randint(10**e, 10**(e+1))\n",
    "    p = a - random.randint(0, 10**(e//2))\n",
    "    if p % 2 == 0:\n",
    "        p -= 1\n",
    "    q = a + random.randint(0, 10**(e//2))\n",
    "    if q % 2 == 0:\n",
    "        q += 1\n",
    "    n = p*q\n",
    "    print(n, etape_fermat(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b0c75b72",
   "metadata": {},
   "source": [
    "**Question 2 (facultative).** Écrire une fonction `factorise_fermat(n)`, qui prend en entrée un entier $n \\ge 1$ quelconque, et retourne sa facorisation complète en utilisant la méthode de Fermat."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b1fb7e39",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fermat_aux(n, fact):\n",
    "    while n % 2 == 0:\n",
    "        if not(2 in fact):\n",
    "            fact[2] = 0\n",
    "        fact[2] += 1\n",
    "        n //= 2\n",
    "    f, g = etape_fermat(n)\n",
    "    if (f == 1 or f == n):\n",
    "        if not(n in fact):\n",
    "            fact[n] = 0\n",
    "        fact[n] += 1\n",
    "        return\n",
    "    fermat_aux(f, fact)\n",
    "    fermat_aux(g, fact)\n",
    "\n",
    "def factorise_fermat(n):\n",
    "    fact = dict()\n",
    "    fermat_aux(n, fact)\n",
    "    return fact\n",
    "    \n",
    "for n in [8, 21, 101, 600]:\n",
    "    print(n, \":\", factorise_fermat(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ce860e2f",
   "metadata": {},
   "source": [
    "## Exercice 3 : méthode $\\rho$ de Pollard\n",
    "\n",
    "Dans cet exercice, on utilise la méthode du $\\rho$ de Pollard pour factoriser un entier. Voir slides de cours pour les détails.\n",
    "\n",
    "\n",
    "**Question 1.** Écrire une fonction `etape_pollard_rho(n)`, qui prend en entrée un entier $n$ qui n'est pas la puissance d'un nombre premier, et qui retourne deux diviseurs $a$ et $b$ de $n$ grâce à la méthode de Fermat. La fonction implémentera l'algorithme de Floyd pour la recherche du cycle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d9313159",
   "metadata": {},
   "outputs": [],
   "source": [
    "def function_f(z):\n",
    "    return z**2 + 1\n",
    "\n",
    "def etape_pollard_rho(n, func):\n",
    "    x = random.randint(0, n-1)\n",
    "    y = x\n",
    "    d = 1\n",
    "    while (d == 1):\n",
    "        x = func(x) % n\n",
    "        y = func(func(y)) % n\n",
    "        d = math.gcd(x-y, n)\n",
    "    if d == n:\n",
    "        return etape_pollard_rho(n, func)\n",
    "    return d, n//d"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "77bb5550",
   "metadata": {},
   "source": [
    "**Question 2 (facultative).** Écrire une fonction `factorise_pollard_rho(n)`, qui prend en entrée un entier $n \\ge 1$ quelconque, et retourne sa facorisation complète en utilisant la méthode de Fermat."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "72f25edf",
   "metadata": {},
   "outputs": [],
   "source": [
    "# à terminer"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "python",
   "language": "python",
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}