Factorisation d’entiers

Les nombres de Mersenne sont les nombres de la forme \(2^p-1\). Pour tester les factorisations, on va considérer les nombres de Mersenne \(M_p=2^p-1\) qui ne sont pas premiers.

  1. Écrire une table des non-premiers de Mersenne \(M_p = 2^p-1\), pour \(p\) premier inférieur à 103.

    solution xcas ⇲ ⇱ solution xcas
    ithprime(27)
    M:=select(x->(! is_pseudoprime(x)),seq(2^ithprime(k)-1,k,1,27))
    

Méthode naïve

  1. Ecrire une fonction facteur_naif(n) qui renvoie le plus petit facteur premier de \(n\), en calculant la division par tous les entiers impairs inférieurs à \(n\).

    Quelle taille d’entiers peut-on factoriser ? Quels sont les nombres de Mersenne que l’on factorise en moins de dix secondes ?

    solution xcas ⇲ ⇱ solution xcas
    naif(n):=for(j:=3;j<=n;j++) { if (!irem(n,j)) return(j); }
    
  2. Améliorer la technique avec une fonction facteur_premier(n) n’effectuant de division que par les nombres premiers donnés par la fonction ithprime (laquelle utilise une base de nombres premiers précalculés).

    Quels sont les nombres de Mersenne qui résistent ?

    solution xcas ⇲ ⇱ solution xcas
    facteur_premier(n) := {
      local(p:=2);
      for(k:=1;p<n;p:=ithprime(k++)) {
      if(!irem(n,p)) return(p);
      }
    }
    
  3. Illustrer graphiquement le théorème des nombres premiers, qui énonce que \(\pi(x)\sim \frac{x}{\log x}\), où \(\pi(x)\) est le nombre de premiers inférieurs à \(x\).

    solution xcas ⇲ ⇱ solution xcas
    scatterplot(seq([ithprime(k),k],k,1,100))
    plot(x/log(x),x,2,ithprime(100))
    

Méthode rho de Pollard

  1. Écrire une fonction pollard_rho(n) qui calcule les \(\pgcd(x_{2k}-x_k,n)\), où \(x_k\) est donné par la suite récurrente \(x_0=1\), \(x_{k+1}=x_k^2+1\bmod n\), jusqu’à obtenir un facteur premier de \(n\).

    solution xcas ⇲ ⇱ solution xcas
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    pollard_rho(n) := {
      local x,y,g;
      x := 1; y := 1;
      g := 1;
      while(g == 1) {
        x := irem(x^2+1,n);
        y := irem(y^2+1,n);
        y := irem(y^2+1,n);
        g := gcd(x-y,n);
      }
      g;
    }
    
  2. Tester la fonction en factorisant les entiers de Mersenne.

  3. Faire afficher le rapport \(i/\sqrt{p}\)\(i\) est le nombre d’itérations effectuées pour trouver le facteur \(p\).

  4. Vérifier graphiquement que cette méthode a une complexité de \(O(\sqrt p)\) itérations.

  5. Changer de polynôme d’itération : examiner le comportement pour un polynôme linéaire, quadratique, cubique.

  6. Modifier pollard_rho en ajoutant un paramètre loops qui permet de diminuer le nombre de calculs de pgcd en accumulant le produit des u-v pour effectuer le pgcd toutes les loops itérations.

    Examiner le gain obtenu sur la factorisation des nombres de Mersenne.

    solution xcas ⇲ ⇱ solution xcas
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    pollard_rho2(n) := {
      local x,y,g,loops,l;
      x := 1; y := 1;
      g := 1; loops := 50;
      while(g && g == 1) {
        for(l:=1;l<loops;l++) {
          x := irem(x^2+1,n);
          y := irem(y^2+1,n);
          y := irem(y^2+1,n);
          g := irem(g*(x-y), n);
        }
        g := gcd(g,n);
      }
      g;
    }
    
  7. Quelle est la probabilité qu’un couple de nombres \(a,b\) tirés uniformément modulo \(n\) soient congrus modulo \(n\) ? soient congrus modulo \(p\) ? Quelle est la probabilité que \(k\) nombres tirés uniformément modulo \(n\) soient tous distincts modulo \(p\) ?

    solution xcas ⇲ ⇱ solution xcas

    Pour \(k\) tirages \(a_1,\dots a_k\), la probabilité de tirer des éléments tous distincts vaut

    \[\begin{split}P(a_2\not\equiv a_1\bmod p) &= \frac{p-1}p \\ P(\#\{a_1,a_2,a_3\}=3) &= \frac{p-1}p\frac{p-2}{p} \\ P(\#\{a_i\}=k) &= \prod_{j=1}^{k-1}\frac{p-j}{p}\end{split}\]
  8. Créer la fonction P:=i0->product(1-j/p,j=1..i0-1);. En utilisant limit en +infinity, montrer que \(\log P(2)\) est équivalent à \(-1/p\), \(\log P(3) \sim -3/p\)… Deviner une formule pour \(\log P(i)\).

  9. En utilisant cette formule, montrer que \(P(k) > 1/2\) dès que \(k\) est de l’ordre \(1.18\sqrt p\).

Méthode p-1 de Pollard

Note

On rappelle la méthode : si \(n\) possède un facteur premier \(p\) tel que \(p-1\) n’a que de petits facteurs premiers inférieurs à une borne \(B\) (on dit que \(p-1\) est \(B\)-friable), alors puisque \(a^{p-1}=1\bmod p\) on a également \(a^M=1\bmod p\) pour tout multiple \(M\) de \(p-1\), en particulier si l’on prend \(M\) égal à un produit de puissances de tous les petits nombres premiers inférieurs à \(B\).

Concrètement, on part d’un résidu \(a\) premier à \(n\), et pour chaque premier \(p_i\leq B\) on calcule un exposant \(b_i\) tel que \(p_i^{b_i}<n<p_i^{b_i+1}\). On pose \(M_i = M_{i-1}\times p_i^{b_i}\), et on calcule \(pgcd(a^{M_i}-1,n)\). Dès que l’on atteint la borne de friabilité d’un diviseur premier \(p\) de \(n\), \(p\) divise le pgcd.

  1. Implanter la méthode \(p-1\) de Pollard. L’utiliser pour factoriser les premiers nombres de Mersenne.
  2. Expliquer ce qui se passe lorsque l’on essaie de factoriser \(M_{29}\).
  3. Trouver une technique pour adapter la méthode \(p-1\) aux nombres semblables à \(M_{29}\).

Méthode de Dixon

On considère l’entier n := 10001 et la base de premiers \((p_1,\dots p_6) = (-1,2,3,5,7,11)\).

  1. Écrire une fonction friable(a) qui renvoie 1 si a est 11-friable, 0 sinon.
  2. Déterminer 7 entiers \(y\) au voisinage de \(\sqrt{n}\) tels que les \(y^2\bmod n\) sont 11-friables.
  3. Construire la matrice \(A\in M_{7,6}(\Z)\) des exposants \(e_{i,j}\) dans la factorisation des \(y_i^2 = \prod_{j=1}^7 p_j^{e_{i,j}}\).
  4. Calculer le noyau de \(A \mod 2\), et en déduire deux entiers \(a\) et \(b\) tels que \(a\not\equiv b\bmod n\) mais \(a^2\equiv b^2\bmod n\).
  5. Factoriser 10001.
  6. Généraliser l’algorithme.