Hypothèse de Riemann généralisée

1) C'est la partie réelle du zéro non trivial considéré qui vaut $1/2$.

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$.

Je rappelle le principe du test. Soit $n$ l'entier dont la primalité est à tester. Si $n$ est premier, alors pour tout entier $a < n$, on a (critère d'Euler) $\left(\frac{a}{n}\right) \equiv a^{\frac{n-1}{2}} \text{ mod } n$. Si $n$ est composé, on peut montrer qu'au moins la moitié des entiers premiers avec $a$ ne vérifient pas la condition ci-dessus, on dit que ce sont des témoins de la non primalité de $n$.

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.

Je ne pourrai clairement pas tout te détailler ici, je te renvoie à cet article, qui montre notamment que l'on peut prendre $C=2$ : https://www.ams.org/journals/mcom/1990-55-191/S0025-5718-1990-1023756-8/S0025-5718-1990-1023756-8.pdf

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)$.

J'ai tout expliqué dans mon message précédent. Au bout de $k$ itérations (uniformes, indépendantes) non concluantes, il y a une probabilité d'au plus $1/2^k$ que $n$ soit composé, autrement dit au moins $1-1/2^k$ que $n$ soit premier. La personne que tu cites commet certainement une erreur d'inattention.