Arithmétique

Algorithme d’Euclide

  1. Programmer l’algorithme d’Euclide, de manière récursive puis de manière itérative.

  2. Programmer l’algorithme d’Euclide étendu permettant de déterminer des relations de Bezout.

  3. Déterminer l’inverse de \(3\) modulo \(2^{107}-1\).

Exponentiation rapide

Note

Soit \(n\) dont l’écriture en base \(2\) est

\[n=e_0+2e_1+4e_2+\dots 2^re_r\]

on peut alors écrire \(a^n\) sous la forme

\[a^n = a^{e_0} \times (a^2)^{e_1} \times \dots (a^{2^r})^{e_r}\]

ou bien

\[a^n = a^{e_0} \times \bigl( a^{e_1} \times \bigl(\dots a^{e_r}\bigr)^2\dots\bigr)^2\bigr)^2.\]
  1. On a écrit la fonction récursive suivante

    puissance_rec(a,n):= {
      local r;
      if(n==0) return 1;
      r := puissance_rec(a^2,iquo(n,2));
      if(irem(n,2))
        { return a*r; }
      else
        { return r; }
      }
    

    À quelle écriture correspond-elle ?

  2. Modifier la fonction puissance_rec pour qu’elle corresponde à l’autre écriture.

  3. Soit \(p\) un nombre premier et \(a\) un entier premier à \(p\), proposer deux (ou trois) algorithmes de calcul de \(a^{-1}\).

  4. Calculer l’inverse de \(3\) modulo \(2^{107}-1\) avec chaque méthode.

  5. Même question avec \(2^{11213}-1\).

  6. Evaluer la complexité de chaque technique.

Nombres premiers

  1. Créer la liste L des nombres entiers inférieurs à 100 en utilisant seq, select, et le test de primalité d’Xcas.

  2. En déduire le nombre de nombres premiers inférieurs à 10000.

  3. Faire de même en écrivant votre propre fonction de test de primalité est_premier.

On veut calculer plus rapidement la liste des premiers inférieurs à 10000 (ou leur nombre).

  1. L’algorithme de crible d’Eratosthène consiste à partir de la liste des entiers de \(2\) à \(n\), et en partant du premier \(p=2\) rayer tous ses multiples. Le nombre premier suivant est le premier entier \(p>2\) qui n’a pas été rayé, on raye ses multiples, et ainsi de suite.

    Le programmer, et mesurer le temps mis pour trouver les premiers inférieurs à 10000 (utiliser time).

  2. Un autre algorithme consiste à tenir à jour une liste des nombres premiers déjà découverts, et à tester la primalité d’un entier en ne divisant que par ces nombres premiers.

    Le programmer, et mesurer le temps mis pour trouver les premiers inférieurs à 10000.

Nombres de Carmichael

On appelle nombres de Carmichael les entiers \(n\) non premiers vérifiant l’égalité de Fermat

\[\forall a\in\N, a^n \equiv a\bmod n.\]
  1. Déterminer le plus petit nombre de Carmichael.

  2. On donne le critère suivant (Korselt, 1899) : \(n\) est un nombre de Carmichael si et seulement si

    \[\forall p\mid n, p^2\nmid n \text{ et } p-1\mid n-1\]
  3. Donner la liste des nombres de Carmichael inférieurs à \(10^4\).

Sécurité de RSA

On définit un module RSA \(n=pq\), avec

\[p = \frac{15^{73}-1}{14}, \; q = \frac{11^{73}-1}{10}\]
  1. Calculer les racines carrées de \(1\) dans \(\Z/n\Z\). Combien y en a-t-il ?

  2. Montrer que si \(a\neq\pm1\bmod n\) vérifie \(a^2=1\bmod n\), alors \(n\) n’est pas premier, et \(\pgcd(a-1,n)\) est un facteur non trivial de \(n\).

  3. 410041 est un nombre de Carmichael. Le factoriser en déterminant une telle valeur de \(a\).

  4. Supposons que l’on connaisse les exposants de chiffrement et de déchiffrement \(ed\) du système RSA. On pose \(ed-1=2^rm\). Montrer qu’au plus la moitié des \(a\in(\Z/n\Z)^\ast\) vérifie \(a^m=1\) ou \(a^{2^jm}=-1\) pour \(0\leq j<m\).

  5. En déduire un algorithme pour factoriser \(n\).

  6. Faire le test avec votre voisin : construire et échanger des clefs RSA, et les casser quand on connaît \(e\) et \(d\).