Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(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

Pied de page des forums