4.4.2 Factorisation de nombres premiers

La multiplication de deux nombres premiers donne un nombre qui n'a comme diviseurs que ces deux nombres premiers initiaux, 1 et lui-même. Par exemple, dans le cas où $n=pq$, $n$ a comme diviseurs 1, $p$, $q$ et $n$. Si l'on veut trouver le totient de $n$, que l'on sait le résultat de la multiplication de deux nombres premiers, il nous faut absolument connaître ses facteurs. Il nous faut factoriser $n$. Cette opération consiste à diviser $n$ par tous les nombres premiers qui lui sont inférieurs jusqu'à ce que l'on trouve un diviseur qui donne un résultat entier. Pour $n=143$, on trouve très rapidement ses facteurs, 11 et 13. Par contre, il devient très laborieux de factoriser de grands nombres. Il n'y a pas d'algorithme connu qui pourrait permettre d'accélérer la factorisation de grands nombres.

Ce qui est important de retenir est qu'il est calculatoirement improbable de découvrir le totient de $n$ si l'on ne connaît pas ses facteurs, $p$ et $q$, lorsque $n$ est assez grand. C'est sur cette base que repose tout le mécanisme de RSA.