Pseudoprimes fuertes de Miller-Rabin

16

Dado un número entero no negativo N, genera el número entero impar impar más pequeño que es un pseudoprimo fuerte para todas las primeras Nbases primas.

Esta es la secuencia OEIS A014233 .

Casos de prueba (un índice)

1       2047
2       1373653
3       25326001
4       3215031751
5       2152302898747
6       3474749660383
7       341550071728321
8       341550071728321
9       3825123056546413051
10      3825123056546413051
11      3825123056546413051
12      318665857834031151167461
13      3317044064679887385961981

Los casos de prueba para N > 13no están disponibles porque esos valores aún no se han encontrado. Si logra encontrar los siguientes términos en la secuencia, ¡asegúrese de enviarlos a OEIS!

Reglas

  • Puede optar por tomar Nun valor indexado a cero o uno indexado.
  • Es aceptable que su solución solo funcione para los valores representables dentro del rango de enteros de su idioma (hasta los N = 12enteros de 64 bits sin signo), pero su solución debe funcionar teóricamente para cualquier entrada con la suposición de que su idioma admite enteros de longitud arbitraria.

Antecedentes

Cualquier entero par positivo xpuede escribirse en la forma x = d*2^sdonde dsea ​​impar. dy sse puede calcular dividiendo repetidamente entre n2 hasta que el cociente ya no sea divisible entre 2. des ese cociente final y ses el número de veces que 2 se divide n.

Si un número entero positivo nes primo, entonces el pequeño teorema de Fermat dice:

Fermat

En cualquier campo finito Z/pZ (donde pes primo), las únicas raíces cuadradas de 1son 1y -1(o, equivalentemente, 1y p-1).

Podemos usar estos tres hechos para demostrar que una de las siguientes dos afirmaciones debe ser verdadera para un primo n(donde d*2^s = n-1y res algún número entero [0, s)):

Condiciones de Miller-Rabin

La prueba de primalidad de Miller-Rabin funciona probando el contrapositivo de la afirmación anterior: si existe una base atal que ambas condiciones anteriores son falsas, entonces nno es primo. Esa base ase llama testigo .

Ahora, probar cada base [1, n)sería prohibitivamente costoso en tiempo de cálculo para grandes n. Existe una variante probabilística de la prueba de Miller-Rabin que solo prueba algunas bases elegidas al azar en el campo finito. Sin embargo, se descubrió que probar solo las abases primarias es suficiente y, por lo tanto, la prueba se puede realizar de manera eficiente y determinista. De hecho, no todas las bases primas necesitan ser probadas, solo se requiere un cierto número, y ese número depende del tamaño del valor que se está probando para la primalidad.

Si se prueba un número insuficiente de bases primas, la prueba puede producir falsos positivos, enteros compuestos impares donde la prueba no puede demostrar su composición. Específicamente, si una base ano puede demostrar la composición de un número compuesto impar, ese número se llama un pseudoprimo fuerte a la base a. Este desafío consiste en encontrar los números compuestos impares que son fuertes psuedoprimos para todas las bases menores o iguales que el Nnúmero primo th (lo que equivale a decir que son pseudoprimos fuertes para todas las bases primas menores o iguales que el Nnúmero primo th) .

Mego
fuente
1
Publicación de Sandbox (ahora eliminada)
Mego
¿Es un algoritmo que prueba todos los valores impares de 1 para dar como resultado una fuerte pseudoprimidad permitida por las reglas?
user202729
@ user202729 No veo por qué no sería así. ¿Qué te haría pensar que es?
Mego
Sugeriría hacer esta pregunta de código más rápido porque la mayoría de las respuestas serán simplemente fuerza bruta.
Neil A.
@NeilA. No estoy de acuerdo con que esto sería mejor como código más rápido. Si bien es cierto que las respuestas seguramente serán fuerza bruta (dado que aún no se ha desarrollado otro algoritmo y no espero que PPCG lo haga), el código de golf es mucho más simple, tiene una barrera mucho más baja para la entrada (ya que los remitentes puede calificar sus propias soluciones), no requiere que yo ejecute y califique cada solución (y lidie con los tiempos de ejecución exorbitantes), y el problema es lo suficientemente interesante como un desafío de golf.
Mego

Respuestas:

4

C, 349 295 277 267 255 bytes

N,i;__int128 n=2,b,o,l[999];P(m){i<N&&P(m<2?l[i++]=n:n%m?m-1:n++);}main(r){for(P(scanf("%d",&N));r|!b;)for(++n,b=i=N;i--&&b;){for(b=n-1,r=0;~b&1;b/=2)++r;for(o=1;b--;o=o*l[i]%n);for(b=o==1;r--;o=o*o%n)b|=o>n-2;for(o=r=1;++o<n;r&=n%o>0);}printf("%llu",n);}

Toma una entrada basada en 1 en stdin, por ejemplo:

echo "1" | ./millerRabin

Ciertamente no va a descubrir nuevos valores en la secuencia en el corto plazo, pero hace el trabajo. ACTUALIZACIÓN: ¡ahora incluso más lento!

  • Ligeramente más rápido y más corto, inspirado en la respuesta de Neil A ( a^(d*2^r) == (a^d)^(2^r))
  • Significativamente más lento nuevamente después de darse cuenta de que todas las soluciones a este desafío serán impares, por lo que no es necesario hacer cumplir explícitamente que solo verifiquemos números impares.
  • ¡Ahora usando GCC's __int128, que es más corto que unsigned long longmientras trabaja con números más grandes! También en máquinas little endian, el printf con %llutodavía funciona bien.

Menos minificado

N,i;
__int128 n=2,b,o,l[999];
P(m){i<N&&P(m<2?l[i++]=n:n%m?m-1:n++);}
main(r){
    for(P(scanf("%d",&N));r|!b;)
        for(++n,b=i=N;i--&&b;){
            for(b=n-1,r=0;~b&1;b/=2)++r;
            for(o=1;b--;o=o*l[i]%n);
            for(b=o==1;r--;o=o*o%n)b|=o>n-2;
            for(o=r=1;++o<n;r&=n%o>0);
        }
    printf("%llu",n);
}

(Anticuado) Desglose

unsigned long long                  // Use the longest type available
n=2,N,b,i,d,p,o,                    // Globals (mostly share names with question)
l[999];                             // Primes to check (limited to 999, but if you
                                    // want it to be "unlimited", change to -1u)
m(){for(o=1;p--;o=o*l[i]%n);}       // Inefficiently calculates (l[i]^p) mod n

// I cannot possibly take credit for this amazing prime finder;
// See /codegolf//a/5818/8927
P(m){i<N&&P(m<2?l[i++]=n:n%m?m-1:n++);}

main(r){
    for(
        P(scanf("%llu",&N));        // Read & calculate desired number of primes
        r|!b;){                     // While we haven't got an answer:
        n=n+1|1;                    // Advance to next odd number
        for(b=1,i=N;i--&&b;){       // For each prime...
            for(d=n-1,r=0;~d&1;d/=2)++r; // Calculate d and r: d*2^r = n-1
            // Check if there exists any r such that a^(d*2^r) == -1 mod n
            // OR a^d == 1 mod n
            m(p=d);
            for(b=o==1;r--;b|=o==n-1)m(p=d<<r);
            // If neither of these exist, we have proven n is not prime,
            // and the outer loop will keep going (!b)
        }
        // Check if n is actually prime;
        // if it is, the outer loop will keep going (r)
        for(i=r=1;++i<n;r&=n%i!=0);
    }
    printf("%llu",n);               // We found a non-prime; print it & stop.
}

Como se mencionó, esto utiliza una entrada basada en 1. Pero para n = 0 produce 9, que sigue la secuencia relacionada https://oeis.org/A006945 . Ya no; ahora se cuelga en 0.

Debería funcionar para todos los n (al menos hasta que la salida alcance 2 ^ 64) pero es increíblemente lento. Lo he verificado en n = 0, n = 1 y (después de mucha espera), n = 2.

Dave
fuente
Hago un gran avance en mi solución, y luego tú me diste ... ¡Genial!
Neil A.
@NeilA. ¡Lo siento! Estaba jugando con tipos int más cortos antes de que publicaras tu actualización. Sin embargo, estoy seguro de que encontrarás 2 bytes en alguna parte; Esto está resultando ser sorprendentemente competitivo teniendo en cuenta que son 2 idiomas distintos del golf: D
Dave
3

Python 2, 633 465 435 292 282 275 256 247 bytes

0 indexado

Cuestiona tu implementación y prueba algo nuevo

La conversión de una función a un programa ahorra algunos bytes de alguna manera ...

Si Python 2 me da una forma más corta de hacer lo mismo, voy a usar Python 2. La división es un entero por defecto, por lo que es una forma más fácil de dividir por 2 y printno necesita paréntesis.

n=input()
f=i=3
z={2}
a=lambda:min([i%k for k in range(2,i)])
while n:
 if a():z|={i};n-=1
 i+=2
while f:
 i+=2;d,s,f=~-i,0,a()
 while~d&1:d/=2;s+=1
 for y in z:
  x=y**d%i
  if x-1:
   for _ in[]*s:
    x*=x
    if~x%i<1:break
   else:f=1
print i

Pruébalo en línea!

Python es notoriamente lento en comparación con otros lenguajes.

Define una prueba de división de prueba para la corrección absoluta, luego aplica repetidamente la prueba de Miller-Rabin hasta que se encuentra una pseudoprima.

Pruébalo en línea!

EDITAR : finalmente golfed la respuesta

EDITAR : Utilizado minpara la prueba de primalidad de división de prueba y lo cambió a a lambda. Menos eficiente, pero más corto. Tampoco pude evitarlo y usé un par de operadores bit a bit (sin diferencia de longitud). En teoría debería funcionar (ligeramente) más rápido.

EDITAR : Gracias @Dave. Mi editor me trolleó. Pensé que estaba usando pestañas, pero se estaba convirtiendo en 4 espacios. También revisé casi todos los consejos de Python y lo apliqué.

EDITAR : Cambiado a indexación 0, me permite guardar un par de bytes con la generación de los números primos. También repensé un par de comparaciones

EDITAR : se utiliza una variable para almacenar el resultado de las pruebas en lugar de las for/elsedeclaraciones.

EDITAR : movió el lambdainterior de la función para eliminar la necesidad de un parámetro.

EDITAR : convertido a un programa para guardar bytes

EDITAR : ¡Python 2 me ahorra bytes! Además, no tengo que convertir la entrada aint

Neil A.
fuente
¡+1 por la forma en que manejaste a^(d*2^r) mod n!
Dave
¿Sabe que puede usar una sangría de espacio único (o una sola pestaña) en Python para ahorrar ... una gran cantidad de bytes, en realidad
Dave
@Dave: Esto está usando 1 pestaña por nivel de sangría
Neil A.
Creo que su IDE está jugando con usted y ahorrando espacios mientras le dice que está usando pestañas; cuando los reemplazo por espacios individuales, obtengo un recuento de bytes de solo 311 bytes. Pruébalo en línea!
Dave
@Dave: Ok, eso es extraño, gracias, actualizaré la respuesta.
Neil A.
2

Perl + Math :: Prime :: Util, 81 + 27 = 108 bytes

1 until!is_provable_prime(++$\)&&is_strong_pseudoprime($\,2..nth_prime($_));$_=""

Corre con -lpMMath::Prime::Util=:all(penalización de 27 bytes, ¡ay!).

Explicación

No es solo Mathematica el que tiene una función integrada para prácticamente cualquier cosa. Perl tiene CPAN, uno de los primeros repositorios de bibliotecas grandes, y que tiene una gran colección de soluciones listas para tareas como esta. Desafortunadamente, no se importan (ni siquiera se instalan) de forma predeterminada, lo que significa que, básicamente, nunca es una buena opción usarlos en el , pero cuando uno de ellos encaja perfectamente con el problema ...

Recorremos números enteros consecutivos hasta encontrar uno que no sea primo y, sin embargo, un pseudoprimo fuerte para todas las bases enteras, desde 2 hasta n º primo. La opción de línea de comandos importa la biblioteca que contiene el builtin en cuestión, y también establece la entrada implícita (line-at-a-time; Math::Prime::Utiltiene su propia biblioteca bignum incorporada que no le gustan las nuevas líneas en sus enteros). Esto utiliza el truco estándar de Perl de usar $\(separador de línea de salida) como una variable para reducir los análisis incómodos y permitir que la salida se genere implícitamente.

Tenga en cuenta que tenemos que usar is_provable_primeaquí para solicitar una prueba principal determinista, en lugar de probabilística. (Especialmente dado que una prueba de prueba probabilística probablemente esté usando Miller-Rabin en primer lugar, ¡lo cual no podemos esperar para dar resultados confiables en este caso!)

Perl + Math :: Prime :: Util, 71 + 17 = 88 bytes, en colaboración con @Dada

1until!is_provable_prime(++$\)&is_strong_pseudoprime$\,2..n‌​th_prime$_}{

Corre con -lpMntheory=:all (17 bytes de penalización).

Esto usa algunos trucos de golf de Perl que tampoco conocía (¡aparentemente Math :: Prime :: Util tiene una abreviatura!), Sabía pero no pensé en usar ( }{para generar $\implícitamente una vez, en lugar de "$_$\"implícitamente cada línea) , o lo sabía, pero de alguna manera logró aplicar mal (eliminando paréntesis de las llamadas a funciones). Gracias a @Dada por señalarme esto. Aparte de eso, es idéntico.


fuente
Por supuesto, viene un lenguaje de golf y supera al resto. ¡Bien hecho!
Neil A.
Puedes usar en ntheorylugar de Math::Prime::Util. Además, en }{lugar de ;$_=""debería estar bien. Y puede omitir el espacio después 1y el paréntesis de algunas llamadas a funciones. Además, &funciona en lugar de &&. Eso debería dar 88 bytes:perl -Mntheory=:all -lpe '1until!is_provable_prime(++$\)&is_strong_pseudoprime$\,2..nth_prime$_}{'
Dada
Me había olvidado por completo }{. (Curiosamente, recordé el paréntesis, pero ha pasado un tiempo desde que jugué al golf en Perl y no podía recordar las reglas para dejarlo fuera). Sin embargo, no sabía nada de la ntheoryabreviatura.