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  
• 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 )

• 
• 
• 

Posons M = k(p-1) où 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 :

Ceci est équivalent à :

Et donc

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 et que k divise alors il existe un sous groupe de G d’ordre k.

Nous vous laissons réfléchir aux implications !