Discussion:Test de primalité de Miller-Rabin
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Cet article est indexé par les projets Cryptologie et Mathématiques.
Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.
| Avancement | Importance | pour le projet | |
|---|---|---|---|
| Bon début | Moyenne |  | Cryptologie (discussion • critères • liste • stats • hist. • comité • stats vues) |
| Faible |  | Mathématiques (discussion • critères • liste • stats • hist. • comité • stats vues) | |
Cet article ne comporte pas de liste de tâches suggérées. Vous pouvez saisir une liste de tâches à accomplir (par exemple sous forme d'une liste à puces), puis sauvegarder. Vous pouvez aussi consulter la page d'aide.
Tout ou partie de cet article est issu de la traduction de l'article sous licence CC-BY-SA « (en) Miller–Rabin primality test » dans sa version du 10/10/2004.
Consultez l'historique de la page originale pour connaître la liste de ses auteurs.
Algorithme et temps d'exécution
modifierIl me semble qu'il manque le modulo n pour 1 et -1 dans la condition de l'algorithme. — Le message qui précède, non signé, a été déposé par un utilisateur sous l’IP 78.224.24.74 (discuter), le 17 juin 2009.
Il y était (avant le ≠) mais j'ai amélioré. Anne 13/9/14
Miller-Rabin et FFT
modifierJe n'ai rien trouvé à ce sujet, utilise-t-on vraiment les multiplications par FFT dans le cas de Miller-Rabin, et dans quel cas ? Proz (discuter) 26 octobre 2015 à 13:21 (CET)
Choix du témoin
modifier
Morvan.Bruno :, n - 1 ne risque certes pas d'être un témoin de Miller, cependant, contrairement à ce que vous avez écrit, ce n'est pas une erreur de choisir a avec 1< a < n, vous proposez juste une optimisation mineure qui est d'éliminer tout de suite n-1. Je reprends la version qui est dans les sources indiquées (Demazure, Cormen). Proz (discuter) 18 octobre 2023 à 19:51 (CEST)
- Merci de votre remarque. Je n'ai pas analysé dans le détail (pas le temps ...) mais j'ai constaté que la page (en) sur ce thème utilise cet intervalle :
- "That is why random a are usually chosen in the interval 1 < a < n − 1."
- Pour la petite histoire, j'avais besoin de travailler sur RSA, et j'ai repiqué le code https://www.codewars.com/kumite/587b268987264729e6000105?sel=587b268987264729e6000105
- et j'ai remplacé possibleWitness = random.randint(2, p-2) par possibleWitness = random.randint(2, p-1) (bornes incluses) pour me conformer à WP (fr).
- et là isPrime(13,100) renvoie False , 13 est composé....
- mais là encore pas vérifié que ce code est conforme.
- Bonne soirée. Morvan.Bruno (discuter) 18 octobre 2023 à 20:48 (CEST)
- Les deux sont possibles, tout dépend de la source invoquée, on pourrait effectivement éliminer n-1 car il ne peut pas être un témoin de Miller, c'est juste un choix de présentation, et autant rester fidèle aux sources que nous utilisons ici, ce n'est pas faux pour autant sur en:. Proz (discuter) 18 octobre 2023 à 20:58 (CEST) LE code avec 1 < a < n - 1 est possiblement plus efficace, mais en fait ça n'arrive quasiment jamais de tirer n - 1 par random de 1 à n-1, et de toute façon le calcul est alors immédiat. Proz (discuter)