{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "1a13300c",
   "metadata": {},
   "source": [
    "# Partiel MAO Calcul Formel 20 mai 2026"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "82ab8ff7",
   "metadata": {},
   "source": [
    "## question 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "aff3a5b2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def est_carre(a,p):\n",
    "    a=Zmod(p)(a)\n",
    "    if a==0:\n",
    "        return \"nul\"\n",
    "    if a^((p-1)//2)==1:\n",
    "        return \"carre\"\n",
    "    return \"non_carre\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c367a801",
   "metadata": {},
   "source": [
    "## question 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "025b8b5f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "carre carre non_carre\n"
     ]
    }
   ],
   "source": [
    "p=10^9+7\n",
    "a1=12345678\n",
    "a2=123456789\n",
    "a3=1234567890\n",
    "print(est_carre(a1,p),est_carre(a2,p),est_carre(a3,p))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3f8df967",
   "metadata": {},
   "source": [
    "## question 7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "a6006773",
   "metadata": {},
   "outputs": [],
   "source": [
    "def recherche_naive(p,d):\n",
    "    for x in range(1,ceil(sqrt(p))):\n",
    "        q=p-x^2\n",
    "        if q%d==0:\n",
    "            y2=q//d\n",
    "            r=floor(sqrt(y2))\n",
    "            if r^2==y2:\n",
    "                return (x,r)\n",
    "    return \"pas_de_solution\"\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "11ec85e3",
   "metadata": {},
   "source": [
    "## question 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "8e496f24",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(2, 17) (30, 7) pas_de_solution\n"
     ]
    }
   ],
   "source": [
    "p=2027\n",
    "d1=7\n",
    "d2=23\n",
    "d3=31\n",
    "print(recherche_naive(p,d1),recherche_naive(p,d2),recherche_naive(p,d3))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7517be20",
   "metadata": {},
   "source": [
    "## question 11"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "a361a7d4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def pas_sol(p):\n",
    "    if not(is_prime(p)):\n",
    "        return pas_sol(p+4)\n",
    "    d=1\n",
    "    while d<p:\n",
    "        if est_carre(-d,p)==\"carre\":\n",
    "            return (d,p)\n",
    "        d+=4\n",
    "    return pas_sol(p+4)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "3f1ee3ad",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(5, 7)"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pas_sol(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2d91b4b6",
   "metadata": {},
   "source": [
    "## question 13"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "581d98d9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def calcul_t(p,d):\n",
    "    moinsd=Zmod(p)(-d)\n",
    "    t=moinsd.sqrt()\n",
    "    if t>p//2:\n",
    "        t=p-t\n",
    "    return t"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "72fa1abb",
   "metadata": {},
   "source": [
    "## question 14"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "f925c0ed",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "45209247"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p=10^9+7\n",
    "d=123\n",
    "calcul_t(p,d)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0f27dc2a",
   "metadata": {},
   "source": [
    "## question 15"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "c53c7e97",
   "metadata": {},
   "outputs": [],
   "source": [
    "def recherche_efficace(p,d):\n",
    "    racp=floor(sqrt(p))\n",
    "    t=ZZ(calcul_t(p,d))\n",
    "    r0,r1,v0,v1=p,t,0,1\n",
    "    while r1>racp:\n",
    "        q=r0//r1\n",
    "        r0,r1,v0,v1=r1,r0-q*r1,v1,v0-q*v1\n",
    "    if r1^2+d*v1^2==p:\n",
    "        return (r1,abs(v1))\n",
    "    return \"pas_de_solution\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "250bcfeb",
   "metadata": {},
   "source": [
    "## question 16"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "32b2ba51",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "pas_de_solution (21664, 1633) (29506, 109)\n"
     ]
    }
   ],
   "source": [
    "p=10^9+7\n",
    "d1=123\n",
    "d2=199\n",
    "d3=10891\n",
    "print(recherche_efficace(p,d1),recherche_efficace(p,d2),recherche_efficace(p,d3))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 10.3",
   "language": "sage",
   "name": "SageMath-10.3"
  },
  "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.11.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}