question à propos du test de Miller-Rabin [édité]

Question

Il s'agit d'une question &#224; propos du test de Miller-Rabin. 
Pour ceux qui seraient perdus, ce test est un test probabiliste testant la primalit&#233; d'un nombre... 
(>> http://cryptosec.lautre.net/article.php3?id_article=12 ...&#224; lire pour comprendre la suite!) 
C'est l'un des tests les plus rapides qui existent au monde. 
Mais il poss&#232;de un "goulot d'&#233;tranglement" qui limite malgr&#233; tout sa vitesse d'ex&#233;cution d&#232;s lors que l'on veut tester des nombres de tr&#232;s grande taille (plus d'un million de chiffres). Ce goulot d'&#233;tranglement se situe &#224; la ligne qui effectue le calcul de y = a^r mod n (voir lien donn&#233; ci-dessus).
Ma question : pour diminuer sensiblement le temps d'ex&#233;cution de ce test, 
serait-il possible de choisir la variable al&#233;atoire a dans l'intervalle ]1 ; (n-1)/2[ , voire ]1 ; (n-1)/(10^1000)[ ??
Quelles r&#233;percussions sur le r&#233;sultat ? La probabilit&#233; d'avoir un nombre premier est-elle fortement modifi&#233;e?

Merci! 

-

scelw · Answer

si cette question et la recherche des nombres premiers vous int&#233;ressent, suivez le d&#233;bat sur : http://les-mathematiques.u-strasbg.fr/phorum/read.php?f=2&i=129673&t=128589 ! :)

amicalement,

scelw

Question à propos du test de Miller-Rabin [édité]

1 réponse

Votre réponse

Discussions similaires