Arithmétique

L’anneau \(Z/n\Z\)

  1. Si l’on scinde un numéro de sécurité sociale au niveau des deux derniers chiffres, il est formé de deux entiers \(m\) et \(n\) de respectivement 13 et 2 décimales.

    Vérifiez la validité de votre numéro personnel en calculant \(m+n\bmod 97\).

  2. Déterminer la première puissance de \(13\) qui se termine par \(01012013\).

pgcd, identité de Bézout

  1. Programmer le calcul du pgcd de deux entiers \(a\) et \(b\) à l’aide d’une fonction récursive.

    Justifier la terminaison de l’algorithme.

  2. Écrire une fonction bezout(a,b) qui renvoie la liste [u,v,d] telle que \(au+bv=d\), où \(d\) est le pgcd de \(a\) et \(b\).

restes chinois

  1. Écrire une fonction chinois(x,a,y,b) qui code l’isomorphisme chinois

    \[(x,y)\in\Z/a\Z\times\Z/b\Z\mapsto z\in\Z/ab\Z\]
  2. Déterminer un entier \(x\) tel que

    \[x\equiv 17 \bmod 65537\]\[x\equiv 63 \bmod 3511\]
  3. Soit la matrice

    \[\begin{split}A = \left(\begin{array}{cc}4&5\\6&-7\end{array}\right)\end{split}\]

    En réduisant \(A\) modulo \(2,3,5\) et \(7\), calculer son déterminant.

Théorèmes de Fermat et d’Euler

Le petit théorème de Fermat énonce que si \(p\) est premier, tout entier \(a\) vérifie

\[a^p \equiv a\bmod p\]

test de Fermat et nombres de Carmichael

On appelle nombres de Carmichael les exceptions à la réciproque de l’énoncé de Fermat, c’est-à-dire les entiers \(n\) non premiers vérifiant

\[\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\).

Plus généralement (théorème d’Euler), on a \(a^{\phi(n)}\equiv 1\bmod n\) pour tout \(a\in(\Z/n\Z)^\ast\).

  1. Montrer que pour tout entier \(p\) premier impair et tout entier \(a\) premier à \(p\), \(a^{p-2}\equiv a^{-1}\bmod p\).

racines carrées

  1. Résoudre l’équation \(x^2=1\) dans \(\Z/19\Z\).

  2. Déterminer les racines carrées de \(1\) modulo 2325781.

  3. Sachant que \(75569613259^2=1 \mod 98765432111\), comment peut-on en déduire une factorisation de l’entier 98765432111 ?

    Connaître des racines carrées (non triviales) modulo \(n\) est équivalent à connaître une factorisation (non-triviale) de \(n\).

  4. Soit \(p\) un nombre premier congru à 3 modulo 4. Montrer que pour tout entier \(y\), en posant \(x=y^{\frac{p+1}4}\) :

    • ou bien \(x\) et \(-x\) sont les racines carrées de \(y\) ;
    • ou bien \(y\) n’a pas de racines carrées et \(x\) et \(-x\) sont celles de \(-y\).

    Programmer une fonction squareroots(y,p) qui calcule les racines de \(y\) modulo \(p\), si elles existent.

  5. Déterminer toutes les racines carrées de 1522756 modulo 2325781.

test de Miller-Rabin

Soit \(n\) un entier impair, on pose \(n-1=2^km\) avec \(m\) impair. Si \(n\) est premier, alors pour tout entier \(a<n\) on a

\[\begin{split}\begin{cases} \text{ou bien } a^m \equiv 1\bmod n\\ \text{ou bien } \exists i\in[0..k-1], a^{2^im}\equiv -1\bmod n. \end{cases}\end{split}\]
  1. Écrire une fonction miller(n,a) qui vérifie que \(n\) passe le test de Miller pour l’entier \(a\). On ne factorisera pas \(n-1\).
  2. Combien y a-t-il d’entiers \(a\) permettant de prouver la non primalité de \(n=1729\) ?

On appelle faux témoin de primalité pour l’entier \(n\) non premier tout entier \(a\) qui passe le test de Miller.

Le théorème de Rabin énonce que si \(n\) n’est pas premier, le nombre de faux-témoins est inférieur à \(\frac{\phi(n)}4\).

  1. Au bout de combien d’essais d’entiers \(a\) qui passent le test de Miller peut-on affirmer que \(n\) est premier avec \(99,99\%\) de certitude ?
  2. Écrire un test rabin(n) qui effectue ce test.