En revanche, je suis curieux d'avoir plus de détails sur cette suite de nombres premiers. J'avais tjs entendu dire que ces nombres avaient, a priori, une distribution aléatoire, ce à quoi j'avais conclu qu'il n'existait pas de suite qui contienne tous les nombres premiers (et uniquement eux)... Donc, des info stp :)
Sinon, un dernier truc qui me hérisse : RSA (factorisation d'un produit de 2 nombres premiers) . C'est FAUX : RSA != FACTORISER !!!Personne n'a encore démontré qu'il était nécessaire de savoir factoriser un entier pour casser RSA. En revanche, dans l'autre sens, c'est vrai : si tu sais factoriser un entier, RSA est cassé.
Enfin, sur les tests de primalités probabilistes, il n'y en a qu'un réellement efficace, le test de Miller-Rabin (http://minimum.inria.fr/~raynal/index.php3?page=5(...) ) : à chaque itération, tu démontres qu'il y a une probabilité de 0.25 que le nombre de soit pas premier. Si tu itères le test n fois, la probabilité devient (0.25)^n ... ce qui diminue quand même assez rapidement. Donc, si le nombre que tu testes est "grand", tu as plus de coefficients à tester et donc, tu peux faire bien plus diminuer cette probabilité. Par exemple, si tu teste 3, tu ne peux tester qu'avec le nombre 2 et tu as donc comme réponde que 3 a une proba de 0.25 de ne pas être premier.
[^] # droit de réponse ;)
Posté par pappy . En réponse à la dépêche Campagne pour la libéralisation de la cryptographie. Évalué à 1.
En revanche, je suis curieux d'avoir plus de détails sur cette suite de nombres premiers. J'avais tjs entendu dire que ces nombres avaient, a priori, une distribution aléatoire, ce à quoi j'avais conclu qu'il n'existait pas de suite qui contienne tous les nombres premiers (et uniquement eux)... Donc, des info stp :)
Sinon, un dernier truc qui me hérisse : RSA (factorisation d'un produit de 2 nombres premiers) . C'est FAUX : RSA != FACTORISER !!!Personne n'a encore démontré qu'il était nécessaire de savoir factoriser un entier pour casser RSA. En revanche, dans l'autre sens, c'est vrai : si tu sais factoriser un entier, RSA est cassé.
Enfin, sur les tests de primalités probabilistes, il n'y en a qu'un réellement efficace, le test de Miller-Rabin (http://minimum.inria.fr/~raynal/index.php3?page=5(...) ) : à chaque itération, tu démontres qu'il y a une probabilité de 0.25 que le nombre de soit pas premier. Si tu itères le test n fois, la probabilité devient (0.25)^n ... ce qui diminue quand même assez rapidement. Donc, si le nombre que tu testes est "grand", tu as plus de coefficients à tester et donc, tu peux faire bien plus diminuer cette probabilité. Par exemple, si tu teste 3, tu ne peux tester qu'avec le nombre 2 et tu as donc comme réponde que 3 a une proba de 0.25 de ne pas être premier.