Primalité

Factorisation et carrés

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

Tests de primalité

  1. Trouver un nombre pseudo-premier de 1000 chiffres se terminant par 2017.

Preuves de primalité : la méthode p-1

On peut démontrer qu’un entier est premier à l’aide de la caractérisation suivante :

Proposition

\(n\) est premier ssi \((\Z/n\Z)^\ast\) est cyclique d’ordre \(n-1\).

De plus, dans ce cas, il y a \(\phi(n-1)\) générateurs du groupe multiplicatif, donc une proportion assez élevée.

Il suffit donc de tirer des résidus \(a\) au hasard, et d’être en mesure de montrer pour l’un d’eux que son ordre vaut exactment \(n-1\).

On utilise le lemme suivant

Lemme

Soit \(a\) un élément d’un groupe \(G\) et un exposant \(m\) tel que \(a^m=1\). Alors \(a\) est d’ordre exactement \(m\) si et seulement si \(a^{\frac mp}\neq 1\) pour tout diviseur premier \(p\mid m\).

  1. Fournir une démonstration que n1 := 145531 est un nombre premier.

  2. Démontrer ensuite la primalité de n2 := 40963336208247701473.

    On peut exhiber une preuve sous forme de certificat, c’est-à-dire une liste [n, a, F, L]

    • n est le nombre dont on démontre la primalité ;
    • a est un générateur de \((\Z/n\Z)^\ast\) ;
    • F est la factorisation de \(n-1\) (obtenue à l’aide de la fonction facteurs_premiers()) ;
    • L est une liste formée de certificats de primalité pour chaque premier \(p>1000\) de la factorisation F.

    Un exemple de certificat

    [ 192383, 5, [ 2, 1, 43, 1, 2237, 1],
      [ [2237, 2, [2, 2, 13, 1, 43, 1], [] ] ]
      ]