Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
Discussion fermée
#1 30-05-2017 04:32:54
- Mandar
- Membre
- Inscription : 30-05-2017
- Messages : 2
Test de primalité de Miller-Rabin
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 :)
Dernière modification par Mandar (30-05-2017 04:59:23)
Hors ligne
#2 30-05-2017 10:27:32
- Fred
- Administrateur
- Inscription : 26-09-2005
- Messages : 7 035
Re : Test de primalité de Miller-Rabin
Bonjour,
Je vais corriger les deux fautes de frappe (ce que j'ai vu, c'est la place de "modulo p" dans l'indication, et un i manquant dans le corrigé).
Je crois que la deuxième propriété n'est pas si simple que cela. J'avais lu une preuve il y a longtemps, et elle me semblait délicate....
F.
Hors ligne
#3 31-05-2017 16:16:07
- Mandar
- Membre
- Inscription : 30-05-2017
- Messages : 2
Re : Test de primalité de Miller-Rabin
Okay, merci quand même !
Hors ligne
Pages : 1
Discussion fermée