Por qué no hay pruebas de primalidad basadas en comparar el candidato $n$ con valores de $k \in [0,n]?$

Question

Estoy aprendiendo básicos de la teoría de números y según lo que pude leer, básicamente, todas las pruebas de primalidad (o prueba de primalidad teoremas) que son capaces de decidir si un determinado $n$ es el primer (o un especial pseudoprime) se basan en la comparación de $n$ frente a un general, gran cantidad $\in [n+1,..)$

Yo no estoy incluido el primer tamices en el concepto de primalidad de la prueba, porque implican normalmente más comparaciones que una prueba de primalidad (por ejemplo, la Criba de Eratóstenes)

Por ejemplo yo estoy considerando como pruebas de primalidad (no en orden de importancia, tal como los recuerdo):

• Fermat poco teorema (requiere poderes, por ejemplo,$2^n$)
• Wilson del teorema (requiere $n!$)
• Fibonacci-Lucas pruebas de primalidad ($F_n$ crece muy rápidamente)
• Catalán pruebas de primalidad ($C_n$ crece muy rápidamente)
• Triángulo de Pascal coeficientes binomiales modularidad (requiere coeficientes binomiales así factoriales crecen muy rápidamente)
• Cualquier otro pruebas probabilísticas.
• etc.

Todos los primalidad teoremas y propiedades, cuando se aplica a sus pruebas requieren de un conjunto de varios números más grandes que el candidato $n$ a ser probado.

"En virtud de $n$" hay primer número de tamices, pero si no me equivoco no hay primalidad de prueba basado en la comparación con un valor de $k \in [0,n]$ en la forma en que el mencionado teoremas se aplican, y todos los probados teoremas parecen implicar que cualquier primalidad de la propiedad se obtiene mediante la comparación de los valores "$n$ " y no "bajo $n$", pero es que el punto de una condición necesaria?

Entiendo que una posible respuesta es simplemente que "no fue hallado sin embargo, si existen" pero en otro lado: ¿hay que demostrar que el primalidad de la propiedad en la moda de los anteriores teoremas es posible si y sólo si la comparación se realiza con un número más grande que el candidato $n$?

Así que la pregunta que me gustaría compartir:

Por qué no hay pruebas de primalidad (o primalidad propiedades o teoremas de primalidad) basado en comparaciones de $n$ y algunos de valor de $k \in [0,n]$? Hay una probada imposibilidad teórica detrás de ella?

Gracias!

(Si hay referencias a este tema, también son muy bienvenidos, y como de costumbre voy a quitar la pregunta no es muy clara, por favor, házmelo saber)

Answer 1

La respuesta rápida es que todos los algoritmos que involucran números modulo $n$, y, en particular, usted nunca ir más allá de $n$. Los algoritmos a dar una receta – un algoritmo de computación en algunos números modulo $n$ y la comparación entre ellas. A veces esta receta se puede resumir como una expresión que, si no se realiza el modulo $n$, mayor que la de $n$. Un sucinto de la representación es engañoso, ya que toda la aritmética se hace modulo $n$, e incluso los resultados intermedios nunca tienen más de $n^2$ (ya que todo se reduce a la suma y la multiplicación).