Hypothèse de Riemann généralisée
dans Arithmétique
Bonjour
1) Dans cet énoncé, je ne comprends pas qui vaut 1/2 ?
2) Quelle est son utilité sur le test de primalité de Solovay-Strassen ?
Merci.
1) Dans cet énoncé, je ne comprends pas qui vaut 1/2 ?
2) Quelle est son utilité sur le test de primalité de Solovay-Strassen ?
Merci.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
2) En supposant cette hypothèse, on peut montrer que le plus petit témoin de non primalité pour l'entier $n$ dans le test de Solovay-Strassen est $\ll (\log n)^2$. Ainsi, ce test passe d'un test probabiliste, à un test déterministe, et même polynomial, puisqu'il suffit de tester un "petit" nombre d'égalités pour conclure à la nature de $n$.
Merci
On en déduit un test probabiliste : on prend $a < n$ au hasard, s'il n'est pas premier avec $n$, c'est que $n$ est composé, sinon on teste la congruence ci-dessus. Si elle n'est pas vérifiée, $n$ est composé, sinon, on se dit que l'on avait au plus une chance sur deux d'avoir tiré un mauvais témoin. En supposant les tirages indépendants, au bout de $k$ tirages non concluant, on en déduit que $n$ est premier avec une probabilité d'au moins $1-\frac{1}{2^k}$.
Le problème est donc que cet algorithme ne peut jamais conclure avec certitude que $n$ est premier (et c'est ce qui est le plus intéressant en pratique). Bien sûr, on peut transformer le test en un test déterministe en vérifiant si la congruence est vraie pour plus de la moitié des $a<n$ premiers avec $n$, mais la complexité de l'algorithme devient alors exponentielle (en $\log n$, la taille de l'entrée) à cause du nombre d'étapes nécessaires pour l'exécuter, ce qui est rédhibitoire en pratique.
Si l'hypothèse de Riemann généralisée est vraie, on montre qu'il existe une constante absolue $C > 0$ telle que, si $n$ est composé, on peut trouver un témoin de non primalité $a \leq C(\log n)^2$. Le nombre d'étapes à effectuer pour conclure définitivement à la primalité ou non de $n$ devient alors de l'ordre d'une puissance de $\log n$, c'est un algorithme polynomial, bien plus efficace que l'algorithme naïf ci-dessus.
Merci.
La clé est le résultat d'Ankeny, qui implique notamment que le plus petit non carré inversible modulo $n$ est $O(\log^2 n)$.
Merci :-)