0
$\begingroup$

Suppose that $N$ is a Carmichael number, but we don't know that yet and we perform the Fermat test on it: that is for numbers $a$ such that $gcd(a,N) = 1$ we check if $a^{N-1} \equiv 1 \pmod N$.

Since $N$ is Carmichael, it will pass this test for all such $a$, but how many values of $a$ do you need to test before you can be certain that a number is a Carmichael number?

Is $\sqrt{N}$ sufficient? I know that all Carmichael numbers are odd and so if $N$ passes the test to base $a$ is will also pass for base $N-a$, but is there a better bound than just $\frac{N-1}{2}$?

$\endgroup$
  • 2
    $\begingroup$ Well, if $N$ is prime then it will pass all the tests as well. $\endgroup$ – lulu Apr 16 '18 at 16:20
  • 1
    $\begingroup$ You can't be sure with Fermat tests. Use something like math.stackexchange.com/a/1729144/61216 to check for probable Carmichael numbers. $\endgroup$ – gammatester Apr 16 '18 at 17:14
1
$\begingroup$
  • If you find a base such that $N$ is a Fermat-pseudoprime but not a strong Fermat-pseudoprime, then you can efficiently find a non-trivial factor of $N$

  • Doing $\sqrt{N}$ tests is nonsense. You could as well apply trial division to completely factor the number. Since you assume the number $N$ is a Carmichael number, it must have a factor not exceeding $N^{1/3}$ , but for large $N$ it would still take too long to apply trial division.

  • Unfortunately, there is no general bound for a witness ( a base showing that $N$ is composite) because for every finite collection of bases there are infinite many composite numbers passing all those bases.

  • You will have to find the factorization to show that $N$ is a Carmichael-number. In this case, there is a nice criterion : If $N$ is composite, odd and squarefree, then $N$ is a Carmichael-number if and only if $p-1|N-1$ holds for every prime $p$ dividing $N$.

$\endgroup$
  • 1
    $\begingroup$ That last point is Korselt's criterion. $\endgroup$ – J.G. Apr 17 '18 at 6:22
  • $\begingroup$ To the proposer: A Carmichael number will have at least 3 prime divisors. The last part of the "nice criterion" will automatically fail if N has exactly 2 prime divisors. $\endgroup$ – DanielWainfleet Apr 17 '18 at 11:22
  • 1
    $\begingroup$ Peter is correct that in general we have to factor. There are some simple pre-tests to help with arbitrary inputs, such as must-be-odd and an optimistic square-free check (e.g. is it divisible by 9, 25, 49, 121, or 169 -- if so, not Carmichael). Then check Korselt's for small primes (basically a tiny bit of trial division and check as we find the small factors). For large enough input it is often worth a single Fermat test just to toss out some more before factoring. $\endgroup$ – DanaJ Apr 17 '18 at 17:52
0
$\begingroup$

no answer, only comment
Adding to @Peter's answer it might be instructive to see this a bit better. I've made a program to show the fermat-tests for consecutive bases (row-by-row) and consecutive or selected modules (col-by-col). Here is a screenshot of a short part of the spreadsheet. Where the entry is "1" the pseudoprime N is not detected by base B and conversely.
For $N=1729$ for instance you need to test up to base $B=7$ while for $N=341$ it suffices to test to base $b=3$. I tried one time to find an "optimal set of bases" as small as possible but as detecting as many pseudo-primes as possible. Long time ago I had found even some article on this problem but do not at the moment remember the source...

pic


You can download that program at my webspace (no big thing, just a bit to play with and programmed with Delphi 1.0 or 4.0 about 20 years ago)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.