Introducción / antecedentes
En una discusión reciente en el chat de cifrado, tuve el desafío de discutir / ayudar con la prueba de primalidad de Fermat y los números de Carmichael. Esta prueba se basa en la premisa que a^(p-1) mod p==1
siempre se mantendrá para los primos p
, pero no siempre para los compuestos. Ahora, un número de Carmichael es esencialmente el peor enemigo de la prueba de Fermat: un número para el que tienes que elegir a
para no ser primo p
para obtener a^(p-1) mod p!=1
. Ahora, si a
no es co-prime, esencialmente encontraste un factor no trivial dep
y como todos sabemos, factorizar puede ser bastante difícil. Especialmente si todos los factores son suficientemente grandes. Ahora puede darse cuenta de por qué la prueba de Fermat no se usa en la práctica con tanta frecuencia (bueno, hay mejores algoritmos), es porque hay números para los que usted como defensor (en términos de seguridad) tendría que hacer una cantidad similar de trabajo que un atacante (es decir, factorizar el número).
Entonces, ahora que sabemos por qué estos números son algo fascinantes, los generaremos de la manera más breve posible, ¡así que podemos memorizar el código de generación si alguna vez necesitamos alguno!
Los números de Carmichael también se conocen como A002997 en OEIS . Ya
existe un desafío relacionado , pero las entradas desde allí no son competitivas aquí porque están optimizadas para la velocidad en lugar del tamaño. El mismo argumento es válido para la dirección inversa, es probable que las entradas aquí hagan compensaciones contra la velocidad a favor del tamaño.
Especificación
Entrada
Este es un desafío de secuencia estándar , por lo que toma un entero positivo o no negativo n
como entrada. n
puede estar indexado 0 o 1 como prefiera (indíquelo).
Salida
Su salida será el n
enésimo número carmichael o los primeros n
números carmichael, como prefiera (indíquelo).
Especificación
Un entero x
es un número de Carmichael si y solo si x
es compuesto y para todos los enteros y
con gcd(x,y)=1
, contiene quey^(x-1) mod x==1
.
¿Quién gana?
Este es el código de golf , por lo que gana el código más corto en bytes.
Se aplican las reglas estándar de E / S y lagunas.
Casos de prueba
Los primeros números de Carmichael son:
561,1105,1729,2465,2821,6601,8911,10585,15841,
29341,41041,46657,52633,62745,63973,75361,101101,
115921,126217,162401,172081,188461,252601,278545,
294409,314821,334153,340561,399001,410041,449065,
488881,512461
fuente
Python 2 , 92 bytes
Pruébalo en línea!
1 indexado y lento como la melaza.
En la comprensión de la lista, utilizo el método de Dennis para generar todos los números enteros coprimos a
n
( totativos de n ), y luego calculox**~-n%n
para todos ellos. Llamemos a esta listaL
.Para detectar un número de Carmichael, comparo esta lista lexicográficamente con una lista que consta de
n-1
unos. ¿Por qué funciona esto?Cada elemento de
L
es un número entero positivo:(k/n)
es coprimo paran
,(k/n)**~-n
también lo es, así(k/n)**~-n%n > 0
. Por lo tanto, los únicos valores posibles deL
eso son lexicográficamente menores que[1]*(n-1)
los que consisten enteramente en menos den-1
unos. (¡L
no puede contener más quen-1
valores, yan
que no puede tener más quen-1
totativos! Entonces las comparaciones como[1,1,1,1,3] < [1,1,1,1]
están fuera).Verificar que haya menos de
n-1
entradasL
asegura quen
sea compuesto. (Tenern-1
totativos es una condición equivalente a la primalidad). Y luego, la condición para ser un número de Carmichael es exactamente que cada elemento deL
igual1
. Entonces, esta comparación lexicográfica detecta exactamente los correos electrónicosL
que nos interesan.El Sr. Xcoder guardó un byte al cambiar a la forma recursiva lambda:
j
cuenta regresiva cada vez que tocamos un número de Carmichael yn
cuenta cada vez que recurrimos. Entonces, una vez quej
llega a cero,n-1
es igual aloriginal_value_of_j
número th de Carmichael.fuente
Jalea ,
1211 bytes-1 byte gracias a miles & Mr. Xcoder (uso del átomo de función Carmichael y un golf del mismo)
Un enlace monádico que toma
n
y devuelve una lista de los primerosn
números de Carmichael.Pruébalo en línea!
¿Cómo?
Al igual que el anterior (a continuación), excepto que hay una función incorporada para la función Carmichael, que produce la potencia más pequeña de tal manera que la entrada elevada a esa potencia es congruente con un módulo que la potencia para todos los enteros co-prime a ese entero. Por lo tanto, podemos excluir los falsos positivos (primos) en menos bytes y tener un código más rápido.
Anteriores 12 bytes :
Pruébalo en línea! (Sí, se agota el tiempo para
n=3
).¿Cómo?
Un número,
c
es un número de Carmichael si es compuesto y es cierto que cualquier número enterox
, elevado ac
es congruente con elx
móduloc
.Tan sólo hay que comprobar esto de positivo
x
ax=c
sí mismo.Tenga en cuenta también que en
x=c
la verificación se determina six
elevar a la potencia dex
es congruente con elx
módulox
, lo cual es cierto, por lo que no necesitamos verificar esto (esto hace que el código sea más corto).fuente
ECMAScript Regex,
8689 bytesAdvertencia: no leas esto si no quieres que te estropeen un poco de magia regex unaria. Si desea intentar descubrir esta magia usted mismo, le recomiendo comenzar resolviendo algunos problemas en la expresión regular ECMAScript: consulte esta publicación anterior para obtener una lista de problemas recomendados etiquetados consecutivamente con spoilers para resolver uno por uno.
^(?!(x(x+))(?!\2*$)\1*(?=\1$)(?!(xx+)\3+$))((?=(xx+?)\5*$)(?=(x+)(\6+$))\7(?!\5*$)){2,}x$
Pruébalo en línea!
La magia principal de esta expresión regular está en la parte que afirma que todos los factores primos de N son de multiplicidad exactamente única. Es el mismo truco utilizado por mis cadenas Match, cuya longitud es una cuarta potencia y expresiones regulares de Find the Smoothest Number : división implícita repetida por el factor primo más pequeño.
También es posible probar directamente que N no tiene factores de cuadrado perfecto (es decir, que N no tiene cuadrado). Utiliza una variante del algoritmo de multiplicación que se describe brevemente en un párrafo de mi publicación de expresiones regulares abundantes para probar si un número es un cuadrado perfecto. Este es un spoiler . Así que no sigas leyendo si no quieres que se te estropee un poco de magia regex unaria avanzada . Si desea intentar descubrir esta magia usted mismo, le recomiendo comenzar resolviendo algunos problemas en la lista de problemas recomendados etiquetados consecutivamente con spoilers en esta publicación anterior , e intentando encontrar las ideas matemáticas de forma independiente.
Sin embargo, el uso de ese algoritmo en este problema no proporciona ningún beneficio. Resulta en una expresión regular más lenta, con un tamaño mayor de 97 bytes. Sin la prueba de multiplicidad primaria (que en un bucle afirma que hay al menos 2 factores primos y que cada uno es de multiplicidad única), tenemos que afirmar por separado que N es compuesto.
Pruébalo en línea!
fuente
decision-problem
respuesta, pero el desafío es unsequence
desafío.) ¿Presumiblemente en una variante de expresión regular más poderosa habría una prueba más directa para los divisores cuadrados disponibles?^(?!(x(x+))(?!\2*$)\1*(?=\1$)(?!(xx+)\3+$)|((^x|xx\5){2,})\4*$)(xx+)\6+$
, o tal vez incluso menos de 72 bytes.J ,
725951 bytesPruébalo en línea!
fuente
Retina , 94 bytes
Pruébalo en línea!1 indexado. No es rápido, por lo que se
n>5
agotará el tiempo en TIO. Explicación:Incrementar el valor actual. En la primera pasada, esto también elimina
n
del búfer de salida (pero$+
aún puede acceder a él).Pruebe si el valor actual es un número de Carmichael. Esto utiliza el algoritmo alternativo de @ Deadcode, ya que la detección de cuadrados es más corta cuando se escribe usando .NET / Perl / PCRE regex.
Repita hasta que el valor actual sea un número Carmichael.
Incrementar el valor actual.
Repita el incremento inicial y el bucle anterior
n
tiempos de .Convierte el resultado a decimal.
fuente
Haskell , 95 bytes
Pruébalo en línea!
Degolfed:
fuente