Auteur: Ludovic PATEY

Publié le 5 janvier 2009

Modifié le: 6 janvier 2009

Page d'accueil

Factorisation d’un nombre semi-premier à partir du totient d’Euler

Vous êtes ici : Accueil / Articles / Mathématiques

Introduction

Les nombres semi-premiers sont utilisés notamment dans des systèmes de chiffrement comme RSA. Nous allons ici développer une manière simple pour factoriser ces nombres en connaissant la valeur de leur indicatrice d’euler.

Rappel

Soient p et q deux nombres premiers, et \varphi l’indicatrice d’Euler,

\varphi( pq ) = (p-1)(q-1)

Factorisation

Soient n = pq et m = \varphi(n).

n-m = pq - (p-1)(q-1) = p + q - 1

Soit a = n - m +1. Alors, (a - p )p = n. En effet, a = p+q.

(a-p)p -n = -p^2 + ap -n = 0

Il suffit donc de résoudre l’équation du second degré. Les racines sont

r_1 = \frac{a - \sqrt{a^2-4n}}{2}

r_2 = \frac{a + \sqrt{a^2-4n}}{2}

Ainsi, p = r_1 et q = r_2.

Commentaires

ogp a dit le 5 décembre 2009

Et alors.. ?

Ludovic PATEY a dit le 5 décembre 2009

Ce n’est pas le résultat mathématique qui compte en lui-même. C’est une information heuristique selon laquelle trouver un moyen de calculer l’image d’un nombre par la fonction indicatrice d’euler permettrait de factoriser un nombre semi-premier, et donc que la fonction indicatrice d’euler n’a probablement pas de formule ne faisant intervenir aucune fonction à sens unique.

Auteur :

Message :