Discussion:Test de primalité de Solovay-Strassen
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Cet article est indexé par le projet 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 | À évaluer |  | 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.
Symbole de Legendre
modifierqu'en est il du symbole de jacobi?? il me semble que le test de solovay strassen l'utilise.. en effet le symbole de legendre n'est défini que pour un n premier, tandis que la définition du symbole de jacobi l'étend à tous les entiers. Ici il s'agit de chercher si n est premier, il me semble qu'il y a un raccourci bien ennuyeux. — Le message qui précède, non signé, a été déposé par un utilisateur sous l’IP 82.227.34.84 (discuter), le 10 mars 2007.
C'est réparé. Anne 13/9/14
Présentation récursive de l'algorithme?
modifierNe pourrait-on pas présenter l'algorithme récursivement? Ça serait tellement plus clair! --Pierre de Lyon (discuter) 25 septembre 2015 à 15:09 (CEST)
Preuve/Source pour la partie performance ?
modifierN'ayant pas réussi à obtenir la preuve par moi même et constatant que cette partie n'est pas tiré de la version anglaise, est-ce que quelqu'un pourrait fournir la preuve ou des sources confirmant la partie Performance?
> En utilisant des algorithmes rapides d’exponentiation modulaire, la complexité en temps dans le pire cas de cet algorithme est un O(k × log3 n), où k est le nombre maximum de fois où l'on tire aléatoirement un entier pour calculer un symbole de Jacobi avec lui, et n est la valeur dont on veut examiner la primalité. La probabilité pour que l’algorithme échoue, c'est-à-dire la probabilité que n soit composé sachant que l'algorithme dit qu'il est premier, est inférieure à , avec (et non pas 2-m comme on le trouve chez certains auteurs, ce qui est en fait la probabilité que l'algorithme réponde que n est premier alors qu'il ne l'est pas. Il y a deux ordres de grandeurs entre ces deux probabilités pour des valeurs typiques de n !) 37.171.217.142 (discuter) 15 novembre 2022 à 11:05 (CET)