Polinomios de Chebyshev del primer tipo y prueba de primalidad

Question

Puede usted dar una prueba o un contraejemplo para la declaración dada a continuación ?

Inspirado por Agrawal de la conjetura en este documento y por el Teorema 4 en este trabajo he formulado la siguiente declaración :

Deje $n$ ser un número natural mayor que dos . Deje $r$ el menor número primo impar tal que $r \nmid n$ e $n^2 \not\equiv 1 \pmod r$ . Deje $T_n(x)$ ser el polinomio de Chebyshev de la primera clase , a continuación, $n$ es un número primo si y sólo si $T_n(x) \equiv x^n \pmod {x^r-1,n}$ .

Puede ejecutar esta prueba aquí .

He probado esta afirmación a $5 \cdot 10^4$ y no hubo contraejemplos .

EDITAR

Implementación del algoritmo en PARI/GP sin calcular directamente $T_n(x)$ .

Answer 1

Wow. Esto merece un aparte de respuesta.

Como mencioné en un comentario, motivado por la pregunta, en un comentario anterior, por Igor Rivin si un eficiente primalidad de la prueba puede realizarse si el enunciado de la pregunta es verdad, yo les hice una pregunta por separado acerca de si se podría calcular de manera eficiente $T_n(x)$ modulo $x^r-1,n$. Que pregunta recibió una brillante respuesta por Lucía, que permite realmente demostrar que si el enunciado de la pregunta es verdadera, de hecho, se obtiene una muy eficiente primalidad de la prueba basado en él.

He hecho este rápido y sucio código de Mathematica

polmul[f_, g_, r_, n_] := Mod[f.NestList[RotateRight, g, r - 1], n]

matmul[a_, b_, r_, n_] :=  Mod[
 {{polmul[a[[1, 1]], b[[1, 1]], r, n] + polmul[a[[1, 2]], b[[2, 1]], r, n], 
   polmul[a[[1, 1]], b[[1, 2]], r, n] + polmul[a[[1, 2]], b[[2, 2]], r, n]}, 
  {polmul[a[[2, 1]], b[[1, 1]], r, n] + polmul[a[[2, 2]], b[[2, 1]], r, n], 
   polmul[a[[2, 1]], b[[1, 2]], r, n] + polmul[a[[2, 2]], b[[2, 2]], r, n]}}, n]

matsq[a_, r_, n_] := matmul[a, a, r, n]

matpow[a_, k_, r_, n_] := If[k == 1, a,
 If[EvenQ[k],
  matpow[matsq[a, r, n], k/2, r, n], 
  matmul[a, matpow[matsq[a, r, n], (k - 1)/2, r, n], r, n]
 ]
]

xmat[r_, n_] :=
 {{PadRight[{0, 2}, r], PadRight[{n - 1}, r]},
  {PadRight[{1}, r], ConstantArray[0, r]}}

isprime[n_] := With[{r = smallestr[n]}, 
 If[r == 0, n == 2,
  With[{xp = matpow[xmat[r, n], n - 1, r, n]},
   Mod[RotateRight[xp[[1, 1]]] + xp[[1, 2]], n]
    === PadRight[Append[ConstantArray[0, Mod[n, r]], 1], r]
  ]
 ]
]

donde smallestr es como en mi otra respuesta.

Ejecutar esto en $n$ hasta 100000 (todas las respuestas correctas) da la siguiente duración:

Parece que es en el peor logarítmica de la orden (como la respuesta de Lucía sugiere) - en realidad la gráfica de $\log(\operatorname{time}(n))/\log\log(n)$ casi parece que va a estar delimitado por encima:

Dado que el algoritmo consiste en un procedimiento recursivo para la matriz de competencias, en principio, que uno también tiene que comprobar el uso de memoria. Aquí debo confesar que los resultados son extraños, tal vez es algo de hardware específico. $$ \begin{array}{r|l} \text{amount of memory}&\text{number of cases (out of 100000)}\\ \hline 32&1407\\ 64&94408\\ 80&1\\ 288&1\\ 320&42\\ 352&3\\ 392&8\\ 424&2316\\ 456&1812\\ 3452552&1 \end{array} $$ Esta última cantidad 3452552 corresponde a $n=65969$, no tengo idea de por qué es necesaria tanta memoria. Como dije esto podría ser algo específico de máquina - tal vez algunos de recolección de basura se produjo en ese momento o algo así. De todos modos, en contraposición a la memoria de la medición de datos de tiempo parece ser muy precisa, he utilizado el Mathematica comando AbsoluteTiming y la documentación dice que le da real de tiempo de procesador se utiliza para el cálculo con muy alta precisión.

Answer 2

Decidió hacer un cw respuesta con una ilustración de tiempo de crecimiento.

Yo lo he probado en Mathematica este:

isprime[n_] := 
 With[{r = smallestr[n]}, 
  If[r == 0, n == 2, 
   PolynomialMod[PolynomialRemainder[ChebyshevT[n, t] - t^n, t^r - 1, t], n] === 0
  ]
 ]

donde

smallestr[n_] := Module[{r},
  If[n==1 \[Or] EvenQ[n], Return[0]];
  For[r = 3, MemberQ[{0, 1, r - 1}, Mod[n, r]], r = NextPrime[r + 1],
   If[r < n \[And] Mod[n, r] == 0, Return[0]]
  ];
  r
 ]

Me he quedado en $n$ hasta alrededor de 31.000 (todas las respuestas son correctas); aquí está el gráfico de tiempo necesario como una función de la $n$.

El crecimiento parece más rápido que el polinomio de la gráfica de $\log(\text{time}(n))/\log(n)$ no parece estabilizar:

Por otro lado áspero de un límite superior en el crecimiento puede deducirse del hecho de que $\log(\text{time}(n))/(n\log(n))$ parece ir hacia abajo:

Algunos comentarios adicionales.

(0)

Puntos de datos son sólo para los $n$ que tiene valor positivo de la smallestr, yo. e. de manera que los correspondientes $r$ es menor que cualquier divisor no trivial de $n$. Es comprensible que para otros $n$ cálculo es cualitativamente más rápido.

(1)

Búsqueda de $r$ es muy eficiente: $$ \begin{array}{c|c} r&\text{smallest %#%#% that requires this %#%#%}\\ \hline 11&29\\ 13&419\\ 19&1429\\ 23&315589\\ 29&734161\\ 31&1456729 \end{array} $n$n$r$T_n(x)-x^n$$

(2)

Seems like $n$ is prime iff all coefficients of $T_n$ are divisible by $n$. If true, this must be well known of course, but I don't know. Should be provable from the explicit form of coefficients of $n$.

(2')

Given (2), it is obvious that at prime $a_0$ the algorithm gives correct answer. To also prove that it detects composite $a_n$ one has to show the following. Denote by $T_n(x)-x^n$, ..., $a_i$ the coefficients of $n$. Then, if some of the $s_j:=a_j+a_{j+r}+a_{j+2r}+...$ is not divisible by $j=0,...,r-1$, then also one of the sums $n$, $a_j$ is not divisible by $n$. Seemingly if $j$ is not divisible by $n$; tal vez esto puede ayudar.