Vous avez dit Friable ?

Oui Friable ! Un nombre peut être friable.

Nous disons qu’un entier positif est friable (ou lisse) lorsque tous ses facteurs premiers sont petits par rapport à l’entier considéré.

Plus précisement nous parlons d’entier positif B-friable (ou B-lisse) lorsque tous ses facteurs premiers sont inférieurs au nombre B.

La friabilité est une caractéristique très importante pour la factorisation.

Pour tout entier naturel N, nous savons que :

  • trouver  \phi(N)
  • trouver les facteurs premiers de N

sont deux problèmes de complexité équivalente.

Rappelons également que pour tout nombre a premier avec N :
(Dans notre cas : N = pq et \phi(N) = (p-1)(q-1) )

  • a^\phi(N) = 1 \mod N
  • a^\phi(p) = a^{p-1} = 1 \mod p
  • a^\phi(q) = a^{q-1} = 1 \mod q

Posons M = k(p-1)k est un entier naturel non nul (i.e : M est un multiple de p-1).
Nous pouvons alors écrire en utilisant les rappels ci-dessus :
a^M = a^{k(p-1)} = (a^{(p-1)})^k= 1^k \mod p = 1 \mod p
Ceci est équivalent à : p |(a^M-1)

Et donc pgcd(N, (a^M-1)) = p

Très bien, mais vous allez nous demander : « Et la friabilité dans tout cela ? »

La friabilité va nous servir à trouver efficacement un M multiple de p-1.

En effet, si (p-1) est B-friable, alors il peut nous suffir de prendre M = B! pour avoir un candidat intéressant.

Si vous avez compris cette idée, alors vous avez compris l’algorithme dit de p-1 de Pollard !

Pour les puristes que vous êtes, nous complétons ici la réflèxion avec un petit lemme :

Si G est un groupe abélien d’ordre phi(N) et que k divise phi(N) alors il existe un sous groupe de G d’ordre k.

Nous vous laissons réfléchir aux implications !

Publicités

A propos JoMendes

Amateur de mathématiques et d'hexadécimal. Je m'intéresse de près ou de loin suivant mon niveau à tous les sujets de sécurité de l'information.
Cet article, publié dans Challenge ANSSI, Cryptographie Asymétrique, est tagué , . Ajoutez ce permalien à vos favoris.

Un commentaire pour Vous avez dit Friable ?

  1. Ping : Le logarithme discret et le PSG | Cryptobourrin

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s