Introdução / Histórico
Em uma discussão recente no chat de criptografia, fui desafiado a discutir / ajudar com o teste de primalidade de Fermat e os números de Carmichael. Esse teste é baseado na premissa que a^(p-1) mod p==1
sempre será válida para primos p
, mas nem sempre para compostos. Agora, um número de Carmichael é essencialmente o pior inimigo do teste de Fermat: um número para o qual você precisa escolher a
para não ser co-primo p
para obter a^(p-1) mod p!=1
. Agora, se a
não for co-prime, você basicamente encontrou um fator não trivial dep
e como todos sabemos, fatorar pode ser bastante difícil. Especialmente se todos os fatores forem suficientemente grandes. Agora você pode perceber por que o teste de Fermat não é usado na prática com tanta frequência (bem, existem algoritmos melhores), é porque existem números para os quais você, como defensor (em termos de segurança), teria que fazer uma quantidade semelhante de trabalho como um invasor (ou seja, fatorar o número).
Então agora que sabemos por que esses números são fascinantes, vamos gerá-los da maneira mais curta possível, para que possamos memorizar o código de geração, se precisarmos de algum!
Os números de Carmichael também são conhecidos como A002997 no OEIS .
Já existe um desafio relacionado , mas as entradas de lá não são competitivas aqui porque são otimizadas para velocidade, em vez de tamanho. O mesmo argumento vale para a direção inversa; as entradas aqui provavelmente farão trocas contra a velocidade em favor do tamanho.
Especificação
Entrada
Este é um desafio de sequência padrão , então você usa um número inteiro positivo ou não negativo n
como entrada. n
pode ser indexado com 0 ou 1 como preferir (indique).
Resultado
Sua saída será o n
número -th carmichael ou o primeiro n
número carmichael, como você preferir (indique).
Especificação
Um inteiro x
é um número Carmichael se e somente se x
é composto e para todos os inteiros y
com gcd(x,y)=1
, afirma que y^(x-1) mod x==1
.
Quem ganha?
Isso é código-golfe , então o código mais curto em byte vence!
Aplicam-se regras padrão de E / S e lacunas.
Casos de teste
Os primeiros números de carmichael são:
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
fonte
Python 2 , 92 bytes
Experimente online!
1-indexado e lento como melaço.
Na compreensão da lista, eu uso o método de Dennis para gerar todos
n
os coprimes de números inteiros para ( totativos de n ) e, em seguida, calculox**~-n%n
para todos eles. Vamos chamar esta listaL
.Para detectar um número de Carmichael, comparo esta lista lexicograficamente com uma lista composta por um
n-1
. Por que isso funciona?Cada elemento de
L
é um número inteiro positivo:(k/n)
é coprime paran
, então(k/n)**~-n
também é, então(k/n)**~-n%n > 0
. Assim, os únicos valores possíveisL
disso são lexicograficamente menores do que[1]*(n-1)
aqueles consistindo inteiramente de menos do que valoresn-1
. (L
não pode conter mais do quen-1
valores, assim comon
não pode ter mais do quen-1
totativos! Portanto, comparações como[1,1,1,1,3] < [1,1,1,1]
estão fora.)Verificar se há menos de
n-1
entradasL
assegura quen
seja composto. (Tern-1
totative é uma condição equivalente à primalidade.) E então, a condição para ser um número de Carmichael é exatamente esse todo elemento deL
igual1
. Portanto, essa comparação lexicográfica detecta exatamente oL
que nos interessa.O Sr. Xcoder salvou um byte mudando para a forma lambda recursiva: faz uma
j
contagem regressiva toda vez que atingimos um número de Carmichael e uma contagem regressivan
toda vez que recorremos. Então, uma vez quej
atinge zero,n-1
é igual aooriginal_value_of_j
número th th Carmichael.fonte
Geléia ,
1211 bytes-1 byte graças a milhas e o Sr. Xcoder (uso do átomo da função Carmichael e um golfe dele)
Um link monádico que pega
n
e retorna uma lista dos primeirosn
números de Carmichael.Experimente online!
Como?
Muito parecido com o anterior (abaixo), exceto que há uma função interna para a função Carmichael - que produz a menor potência, de modo que a entrada aumentada para essa potência é congruente a um módulo dessa potência para todos os inteiros co-prime para esse inteiro. Assim, podemos excluir os falsos positivos (números primos) em menos bytes e ter um código mais rápido!
12 bytes anteriores :
Experimente online! (Sim, é o tempo limite para
n=3
).Como?
Um número
c
,, é um número de Carmichael, se for composto e é verdade que qualquer número inteirox
elevado ac
é congruente para ox
móduloc
.Nós só precisamos verificar isso positivo
x
porx=c
si próprio.Observe também que, na
x=c
verificação, éx
aumentado o poder dex
é congruente aox
módulox
, o que é verdadeiro - portanto, não precisamos verificar isso (isso gera um código mais curto).fonte
ECMAScript Regex,
8689 bytesAviso: Não leia isso se não quiser que você estrague uma mágica de expressões regulares unárias. Se você quiser tentar descobrir essa mágica, eu recomendo começar resolvendo alguns problemas no regex ECMAScript: consulte esta postagem anterior para obter uma lista de problemas recomendados consecutivamente identificados por spoilers para resolver um por um.
^(?!(x(x+))(?!\2*$)\1*(?=\1$)(?!(xx+)\3+$))((?=(xx+?)\5*$)(?=(x+)(\6+$))\7(?!\5*$)){2,}x$
Experimente online!
A principal mágica desse regex está na parte que afirma que todos os fatores primos de N têm exatamente uma multiplicidade única. É o mesmo truque usado pelas minhas strings Match, cujo comprimento é uma quarta potência e as regexes Find the Smoothest Number : divisão implícita repetida pelo menor fator primo.
Também é possível testar diretamente que N não possui fatores quadrados perfeitos (ou seja, N é livre de quadrados). Isso usa uma variante do algoritmo de multiplicação descrito brevemente em um parágrafo dos meus abundantes números regex post para testar se um número é um quadrado perfeito. Este é um spoiler . Portanto , não leia mais se não quiser que você estrague uma mágica avançada de expressões regulares unárias . Se você quiser tentar descobrir essa mágica, eu recomendo começar resolvendo alguns problemas na lista de problemas recomendados consecutivamente identificados por spoilers neste post anterior e tentando apresentar os insights matemáticos de forma independente.
No entanto, o uso desse algoritmo nesse problema não oferece nenhum benefício. Isso resulta em um regex mais lento, com um tamanho maior de 97 bytes. Sem o teste de multiplicidade primária (que em um loop afirma que existem pelo menos 2 fatores primos e que cada um deles é de multiplicidade única), temos que afirmar separadamente que N é composto.
Experimente online!
fonte
decision-problem
resposta, mas o desafio é umsequence
desafio.) Presumivelmente, em uma variante de regex mais poderosa, haveria um teste mais direto para divisores quadrados disponíveis?^(?!(x(x+))(?!\2*$)\1*(?=\1$)(?!(xx+)\3+$)|((^x|xx\5){2,})\4*$)(xx+)\6+$
, ou talvez até menos, 72 bytes.J ,
725951 bytesExperimente online!
fonte
Retina , 94 bytes
Experimente online! 1 indexado. Não é rápido, então o tempo limite será
n>5
excedido no TIO. Explicação:Incremente o valor atual. Na primeira passagem, isso também exclui
n
do buffer de saída (mas$+
ainda pode acessá-lo).Teste se o valor atual é um número Carmichael. Isso usa o algoritmo alternativo do @ Deadcode, pois a detecção quadrada é mais curta quando escrita usando o regex .NET / Perl / PCRE.
Repita até que o valor atual seja um número Carmichael.
Incremente o valor atual.
Repita o incremento inicial e os
n
tempos de loop acima .Converta o resultado em decimal.
fonte
Haskell , 95 bytes
Experimente online!
Degolfado:
fonte