Factorisation des grands nombres

[SPH]

Salut a tous,

a ce jour, existe t'il des methodes qui permettent de factoriser des grands nombres (de 200 a 300 chiffres) ?
Ou pire : a t'on pu prouvé que ce n'est pas possible sans tester tous les facteurs premiers possibles ?


-----

[invitedd63ac7a]

Avez-vous cherché sur google avec le mot clé code RSA ? Que vous pourrez compléter par le document suivant:
Twenty Years of Attacks on the RSA Cryptosystem
Attendre d'autres réponses, mes compétences sur le problème restent modestes...

[Paraboloide_Hyperbolique]

Bonjour,

L'un des algorithmes "efficace" que je connaisse est le crible quadratique: https://fr.wikipedia.org/wiki/Crible_quadratique

[gg0]

Bonjour SPH.

Il existe de nombreuses méthodes de factorisation des grands nombres, actuellement aucune de celles qui sont connues ne permettent raisonnablement de factoriser le produit de deux nombres premiers d'environ 100 chiffres en un temps raisonnable.

Cordialement.

[A voir en vidéo sur Futura]

[invite23cdddab]

Mais la question est encore ouverte (on n'a pas montré que ça n'était pas possible).

Après, si on s'autorise les ordinateurs quantiques, l'algorithme de Shor permet de factoriser un nombre à N chiffres en un nombre d'opérations de l'ordre de N^3. Bien entendu, il n'existe pas encore aujourd'hui d'ordinateur quantique de taille suffisante pour factoriser des nombres de plusieurs centaines de chiffres

[invitedd63ac7a]

Donc le chiffrement RSA a encore de beaux jours devant lui !
C'est un des rares procédés mathématiques récents (il date des années 70) qui soit accessible à des élèves de classe terminale. En général, les découvertes mathématiques du 20e siècle sont totalement hors niveau des élèves de Lycée.

[pm42]

Donc le chiffrement RSA a encore de beaux jours devant lui !

On ne sait pas. Il peut très bien devenir moins fiable dans 10 ans ou tenir plus longtemps.
Il faut noter qu'on a régulièrement relevé la taille des clés au cours de son existence.