Introduction / Background
In a recent discussion in the crypto chat I was challenged to discuss / help with the Fermat primality test and Carmichael numbers. This test is based on the premise that
a^(p-1) mod p==1 will always hold for primes
p, but not always for composites. Now a carmichael number is essentially the Fermat's test worst enemy: A number for which you have to pick
a to be not co-prime with
p to get
a^(p-1) mod p!=1. Now if
a is not co-prime, you essentially found a non-trivial factor of
p and as we all know factoring can be quite hard. Especially if all factors are sufficiently large. You may now realize why the Fermat test isn't used in practice as often (well there are better algorithms), it's because there are numbers for which you as a defender (in security terms) would have to do a similar amount of work as an attacker (namely factor the number).
So now that we know why these numbers are somewhat fascinating, we're gonna generate them in the shortest way possible, so we can just memorize the generating code if we ever need any!
Carmichael numbers are also known as A002997 on OEIS.
There is a related challenge already, but entries from there are not competitive here because they are optimized for speed as opposed to size. The same argument holds for the inverse direction, entries here are likely to make trade-offs against speed in favor of size.
This is a standard sequence challenge, so you take a positive or non-negative integer
n as input.
n may be 0- or 1-indexed as you prefer (please indicate).
Your output will either be the
n-th carmichael number or the first
n carmichael numbers, as you prefer (please indicate).
x is a Carmichael number if and only if
x is composite and for all integers
gcd(x,y)=1, it holds that
y^(x-1) mod x==1.
This is code-golf, so the shortest code in byte wins!
Standard IO and loophole rules apply.
The first few carmichael numbers are:
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