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}$?
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$.