Números Primos: regla mod 6k-1 (¿Nueva Descubierta?)

Question

He notado que aunque todos los números primos siguen el patrón de $6k - 1$ y $6k + 1$ lo cual parece ser un hecho algo conocido.

Sin embargo, también he observado que todos los números primos del patrón de $6k - 1$ solo necesitan ser probados contra aquellos que también son $6k - 1$ (más allá de la raíz cuadrada, hasta una sexta parte de su tamaño). ¿Se ha descubierto esto antes? ¿Podría este algoritmo teóricamente encontrar el número primo más grande más rápido que los algoritmos actuales?

En teoría, todo lo que se necesitaría hacer es multiplicar seis por miles de dígitos, y luego hacer un módulo una vez en todo el espectro por todos los productos de $6k - 1$, más rápido incluso si sabemos si esos números $6k - 1$ ya son primos.

Por ejemplo, $6k - 1$ donde $k = 100$, por lo tanto estamos probando si 599 es primo. Para este número solo necesitamos probar todos los $6k - 1 \times 6 \leq 599$.

Aquí hay un código Java que realiza una media criba y funciona bastante rápido ya que no usa módulo, sino que simplemente elimina los múltiplos de cada número en la criba.

public class primesUnder {

public static void main(String[] args) {

    int maxNumber = 100;
    int[] primesUnder = new int[maxNumber];

    for (int i=5, count=0; count < maxNumber; i+=6) {
        primesUnder[count++]=i; 
    }

    for (int index=0; index < maxNumber; index++) {

        if (primesUnder[index] != 0) {

            int x = primesUnder[index];
            int z = x+index;

            while (z < primesUnder.length) {

                primesUnder[z] = 0;
                z+=x;

            }
        }   
    }

  }

}

Answer 1

Si un número $n=6k-1$ se descompone como un producto de primos, no necesariamente distintos $$ n=6k-1=p_1\cdot\cdots\cdot p_t $$ al menos uno de los $p_i$ debe ser de la forma $6k^\prime-1$. Esto es bastante obvio usando aritmética modular para el módulo $6.

De hecho, ninguno de los $p_i$ puede ser ni $2$ ni $3$ ya que el lado izquierdo no es divisible por $2$ ni por $3$. Por lo tanto, la fórmula mostrada se lee $$ n\equiv-1\equiv(\pm1)\cdot\cdots\cdot (\pm1)\bmod 6 $$ y para que se cumpla al menos un factor en el lado derecho (y de hecho un número impar de factores) debe ser $-1$.

Answer 2

Preguntaste dos preguntas, y la respuesta existente solo responde a una de ellas. La respuesta a

¿En teoría este algoritmo sería más rápido para encontrar el primo más grande que los algoritmos actuales?

es no, pero por una razón bastante específica. Los diez primeros primos conocidos son todos primos de Mersenne, primos de la forma $2^p - 1$ donde $p$ es primo. La razón es que hay una forma particularmente rápida de probar números de esta forma para primorialidad, la prueba de primalidad de Lucas-Lehmer. (Y como nota al margen, los primos de Mersenne son equivalentes a $1 \pmod 6$).

Answer 3

Con esas fórmulas se obtienen números no primos, es decir, 6*8+1=49=7*7. También es un hecho conocido que no existe una fórmula polinómica para obtener números primos. Sin embargo, esta fórmula produce buenos resultados. Te recomiendo que leas el artículo de wikipedia sobre ello. Te dará un mejor enfoque sobre este tema.