Carmichael number

Carmichael number is composite number that passed probabilistic prime tests. Carmichael number will pass Fermat test, Lucas test, Miller-Rabin test and any other probabilistic prime test. Carmichael number is also called pseudoprime.

Since the creation of prime number using deterministic prime test take times, many implementation/program just use a pseudoprime which have not been tested thoroughly with deterministic prime test, but these pseudoprimes are working fine in the program, creating a key-pair in RSA for example requires a prime number P and Q, and its implementation such as in OpenSSL (for example) just using pseudoprime, sometime it uses strong pseudoprime which mean the pseudoprime divided by two (2) is a prime/pseudoprime ((P-1/)2 = pseudoprime/prime).

The carmichael number occurance depends on:
1. Test algorithm (e.g.: Fermat test, Lucas test, Miller_rabin test, etc.)
2. Base value (random value)
3. Number of loop (total of random values)

Example(1):
Fermat little theorem prime test,
Base value (witness) 2 (one witness only)
The first sequence of Carmichael numbers are 341, 561, 645, etc.
Prove:
2^341 = 2 (mod 341) .. 11 * 31 = 341 (not prime)
2^561 = 2 (mod 561) .. 3 * 11 * 17 = 561 (not prime)
2^645 = 2 (mod 645) .. 3 * 5 * 43 = 645 (not prime)

Example(2):
Fermat little theorem prime test,
Base value (witness) 2 and 3 (two witnesses only)
The first sequence of Carmichael number are 561, 1105, 1729, etc.
Prove:
2^561 = 2 (mod 561)
3^561 = 3 (mod 561) .. 3 * 11 * 17 = 561 (not prime)
2^1105 = 2 (mod 1105)
3^1105 = 3 (mod 1105) .. 5 * 13 * 17 = 1105 (not prime)
2^1729 = 2 (mod 1729)
3^1729 = 3 (mod 1729) .. 7 * 13 * 19 = 1729 (not prime)

So, with different test algorithm and different base value (witness) and different number of loop will have different Carmichael number.

To eliminate Carmichael number:
1. Use many base values (witnesses).
2. Test with many loop.
3. Use other different prime test algorithm for the value which passed the prime test algorithm value.

NOTE: Normally to avoid Carmichael number, developer use many base values (witnesses), but developer use fewer base values (witnesses) to keep the speed of the running test so it will not hurt the performance.