Forum de mathématiques - Bibm@th.net

Bonjour,

J'étudie en ce moment le test de primalité de Miller-Rabin et je vous remercie de sa preuve sur votre site sous forme d'exercice (http://www.bibmath.net/ressources/justeunexo.php?id=721). (D'ailleurs il y a une petite erreur de frappe dans l'indication et le corrigé si quelqu'un pouvait la corriger :) )

Toutefois, il n'y a pas la preuve de l'assertion suivante qui suit l'énoncé du test de primalité (ici http://www.bibmath.net/dico/index.php?a … abin.html)

"on dit que n passe le test. Un entier premier n va passer le test pour tout entier a. Toutefois, pour un a fixé, un entier non premier n peut aussi passer le test. On démontre qu'il ne peut pas le passer pour plus d'un quart des entiers a compris entre 1 et n−1"

Quelqu'un saurait-il le prouver? Où puis-je trouver une documentation à ce sujet?

J'ai pour le moment trouvé un pdf de 18 pages sur le sujet en anglais ... mais bon ça métonne qu'il faille 18 pages pour prouver ça ... du coup si quelqu'un a une astuce, je suis preneur :)