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[modifier le code]
qu'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?[modifier le code]
Ne 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 ?[modifier le code]
N'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)