>C'est pas sur le fait que cette décomposition est
>très difficile que reposent les méthodes de
>cryptographie actuelle (enfin, j'ai plus vraiment
>de souvenirs hein ...)
C'est exactement là-dessus que se base la sécurté de la méthode RSA. Ta mémoire est bonne.
La clef publique est le produit de deux nombres premiers "grands". Et actuellement on ne dispose pas de méthode "rapide" pour décomposer un nombre.
En gros, rien de tellement mieux que d'essayer de diviser le nombre par les nombres premiers inférieurs à son carré.
Le second problème vient du fait qu'à moins de connaître exactement tous ces dits nombres premiers inférieurs à sa racine carrée, on en est souvent réduit à tester 2, 3 et 5 puis 7+2*k.
Au final, si le nombre est "grand", l'algorithme de décomposition est en n^(1/2) avec n la valeur du nombre a décomposer.
Le temps de calcul augmente beaucoup trop vite avec la taille du nombre.
(J'espère juste ne pas m'être trompé dans ces calculs...)
[^] # Re: Un nouvel algo de compression ?
Posté par Olivier Dupuis . En réponse à la dépêche Un nombre premier exécutable ... illégal ?. Évalué à 3.
>très difficile que reposent les méthodes de
>cryptographie actuelle (enfin, j'ai plus vraiment
>de souvenirs hein ...)
C'est exactement là-dessus que se base la sécurté de la méthode RSA. Ta mémoire est bonne.
La clef publique est le produit de deux nombres premiers "grands". Et actuellement on ne dispose pas de méthode "rapide" pour décomposer un nombre.
En gros, rien de tellement mieux que d'essayer de diviser le nombre par les nombres premiers inférieurs à son carré.
Le second problème vient du fait qu'à moins de connaître exactement tous ces dits nombres premiers inférieurs à sa racine carrée, on en est souvent réduit à tester 2, 3 et 5 puis 7+2*k.
Au final, si le nombre est "grand", l'algorithme de décomposition est en n^(1/2) avec n la valeur du nombre a décomposer.
Le temps de calcul augmente beaucoup trop vite avec la taille du nombre.
(J'espère juste ne pas m'être trompé dans ces calculs...)