pseudo-primalidad y prueba de Solovay-Strassen

Question

Dejemos que $n$ sea un entero impar, decimos que $n$ es $a$ -pseudoprima si $gcd(a,n)=1$ y :

$$\begin{pmatrix}\frac{a}{n}\end{pmatrix}=a^{\frac{n-1}{2}}\text{ mod } n $$

El criterio de Euler establece que si $n$ no es primo, entonces a lo sumo la mitad de los elementos $a$ en $\frac{\mathbb{Z}}{n\mathbb{Z}}^*$ son tales que $n$ es $a$ -pseudoprima.

Ahora me gustaría saber si podemos tener una mejor estimación para esto (al menos en algunos casos). Por ejemplo, se puede demostrar que para $n:=p^{\alpha}$ hay exactamente $p-1$ elementos $a$ en $\frac{\mathbb{Z}}{n\mathbb{Z}}^*$ son tales que $n$ es $a$ -pseudoprima. Para ello hay que utilizar el hecho de que $\frac{\mathbb{Z}}{p^{\alpha}\mathbb{Z}}^*$ es cíclico.

En realidad, el conjunto de $a$ tal que $n$ es $a$ -pseudoprima es en este caso exactamente el conjunto

$$\{a\mid a^{\frac{n-1}{2}}=\pm 1\text{ mod } n\}$$

Mi pregunta es la siguiente, ¿tenemos otros casos (es decir, otros $n$ ) donde podemos dar una buena estimación del número de $a$ de tal manera que $n$ es $a$ -¿pseudoprima?

No espero una fórmula general pero si asumimos $n$ libre de cuadrados o incluso un número de Carmichael creo que es posible resolverlo.

Answer 1

Si conoces la factorización primaria de $n=p_1 ^{d_1} \dots p_N ^{d_N}$ entonces la pregunta ya ha sido formulada y respondió El número que está buscando es $\prod \limits _{k=1} ^N \gcd (n-1, p_k -1)$ .

Si no conoce la factorización de $n$ entonces Pomerance ha obtenido un límite inferior dado por $\exp (\log x) ^{\frac E {E+1} - \varepsilon}$ (véase la sección 4) y un límite superior dado por $\frac x {\sqrt {\exp \frac {\log x \log \log \log x} {\log \log x}}}$ . Estos resultados también son citados por Erdos en un artículo de 1988 . (Al consultarlos, tenga en cuenta que $\log = \log _2$ y que en el segundo artículo de Pomerance $\log_2 = \log \log$ y $\log_3 = \log \log \log$ Una notación muy poco inspirada. Sin embargo, estas estimaciones no son probablemente lo que tiene en mente para sus alumnos).

Answer 2

La fórmula dada en la respuesta de Alex M. es correcta para los pseudoprimos, pero la pregunta se refería a los pseudoprimos de Euler-Jacobi. Para los pseudoprimos de Euler-Jacobi, la fórmula de recuento de impar $n$ es $E(n)=\delta(n)e(n)$ donde:

$$\nu(n)=\min_{p|n} v_2(p-1)$$

$$e(n) = \prod_{p|n} \left(\frac{n-1}{2}, p-1\right)$$

$$\delta(n) = \left\{\begin{array}{ll} 2 & \text{if}\ \nu(n)=v_2(n-1) \\ 1/2 & \text{if}\ \exists p|n\ \text{with}\ v_2(p-1)<v_2(n-1)\ \text{and}\ v_p(n)\ \text{odd} \\ 1 & otherwise \\ \end{array}\right.$$

y $v_p(x)$ es el exponente de $p$ en la factorización primaria de $x$ . Esta fórmula fue publicada originalmente en 1980 por Monier . Erdos y Pomerance dan una buena presentación de la fórmula junto con las de los pseudoprimes ordinarios y los pseudoprimes fuertes. Las utilizan para encontrar fórmulas de recuento para el número de pseudoprimos.