Fork me on GitHub

Méthode de factorisation p – 1

Nous avons appris que la sécurité de certains protocoles cryptographiques, tel RSA, repose sur la difficulté de factoriser un nombre composé de la forme , où et sont deux nombres premiers de même taille (en pratique, 500 ou 1000 bits).

La factorisation est un problème estimé difficile en général, mais pas tous les nombres sont également difficiles à factoriser. Un nombre est dit friable si sa factorisation ne comporte que des petits nombres premiers. Les nombres friables sont faciles à factoriser, mais par construction les modules RSA n’en sont pas.

L’une des premières familles de modules RSA faibles à avoir été découverte est constitué des nombres tels que (ou ) est friable. Ces modules sont facilement factorisables par la méthode de Pollard. Remarquez qu’un nombre premier pris au hasard a très peu de chances de satisfaire cette propriété.

La méthode de factorisation p – 1

Soit avec et des grands premiers, et supposons que tous les facteurs premiers de sont plus petits qu’une borne , appelée borne de friabilité. La méthode retrouve les facteurs inconnus et , à partir de la seule connaissance de et d’une hypothèse sur la borne .

La méthode est basée sur les propriétés des anneaux modulaires et . L’intuition est simple : puisque divise , l’anneau contient une copie cachée de .1 En effet les réductions modulo sont compatibles avec les réductions modulo  :

(attention, la réciproque n’est pas vraie). En particulier, si est un multiple de , et si n’est pas divisible par , on a

où la dernière égalité est une conséquence du petit théorème de Fermat. Par conséquent est divisible par , et il y a peu de chances qu’il soit aussi divisible par . On a alors , ce qui nous donne la factorisation de .

Pour résumer, voici une réalisation de la méthode de Pollard.

Entrées : un entier , une borne  ;
Sorties : un facteur de , ou ÉCHEC.

  1. Calculer  ;
  2. Choisir un élément au hasard ;
  3. Calculer  ;
    • Si , renvoyer .
  4. Calculer par exponentiation binaire ;
  5. Calculer  ;
    • Si , renvoyer ÉCHEC (borne trop grande) ;
    • Si , renvoyer ÉCHEC (borne trop petite) ;
    • Sinon, renvoyer .

Quelques remarques :

La classe BigInteger

Java possède plusieurs types primitifs d’entiers: byte, short, char, int, long. Tous ces types sont à précision fixe : ils tiennent dans un nombre prédéterminé d’octets et ne peuvent pas dépasser cette borne. Le type le plus grand est long, qui code les entiers sur 64 bits.

Cependant, 64 bits correspondent à peine 20 chiffres décimaux : largement en dessous des tailles d’entiers nécessaires à la cryptographie (plutôt 1024 bits ou 300 chiffres décimaux). La classe java.math.BigInteger offre des entiers à précision arbitraire : leur occupation en mémoire grandit au fur et à mesure que les calculs l’exigent. Plus de soucis à se faire sur les dépassements de bornes!

Les BigInteger sont des objets immuables, comme les String : c’est à dire qu’une fois qu’il a été crée, un BigInteger ne peut plus être changé.

Pour créer un BigInteger, rien de plus simple : on peut en créer à partir d’une chaîne de caractères

BigInteger a = new BigInteger("12345678901234567890");

Des constantes aux noms qui parlent de soi sont aussi prédéfinies :

BigInteger.ZERO
BigInteger.ONE
BigInteger.TEN

Les opérateurs usuels +, *, etc. ne sont pas utilisables sur les BigInteger : ils sont remplacés par des méthodes. Voici un bref comparatif des opérations arithmétiques sur les entiers (int ou long) et sur les BigInteger.


  entiers machine BigInteger
création int a = 10; BigInteger a = BigInteger.valueOf(10);
opérations c = a + b; c = a.add(b);
  c = a - b; c = a.subtract(b);
  c = a * b; c = a.multiply(b);
  c = a / b; c = a.divide(b);
  c = a % b; c = a.mod(b);¹
comparaisons a == b a.equals(b)
  a < b a.compareTo(b) == -1
  a > b a.compareTo(b) == 1

¹a.mod(b) se comporte mieux que a % b, en ce que le résultat est toujours positif. Si vous voulez avoir exactement le même comportement que a % b, il faut utiliser a.remainder(b).


D’autres opérations encore sont définies sur les BigInteger, allez voir la documentation.

À vos javac

Le but de ce DM est d’implanter le méthode pour des grands entiers, cependant la classe BigInteger implante déjà une bonne partie du DM. Pour que ce ne soit pas trop simple, il vous est interdit de vous servir des méthodes BigInteger.modPow() et BigInteger.gcd() (vous pouvez vous en servir pour tester vos fonctions, par contre).

Écrivez un programme Java qui prend en entrée un entier et une borne et qui applique la méthode de factorisation . Vous aurez à écrire, notamment

Vérifiez votre programme avec des petits nombres composés. Voici quelques entiers facilement factorisables avec cette méthode :

Votre mission: visitez cette page et utilisez la méthode pour sauver le monde! Faites attention: ces nombres sont bien trop gros pour vous passer de la classe BigInteger

Soumettez votre code source, dans la boîte de dépôt sur e-campus 2, ou par mail à votre enseignant. Vous avez jusqu’au 8 mai à 4h du matin pour soumettre votre travail. Un point de pénalité pour chaque heure de retard : le 8 mai à 23h59 c’est votre dernière chance !

  1. De manière plus formelle, on a un isomorphisme d’anneaux . C’est un cas particulier du théorème des restes chinois.