# Making fermat's little theorem for composite numbers the ultimate test.

It is a programming question but mathematics has a major role to play in it. I have to find the largest prime less than a number $n$. Note that $n\leq10^{18}$. I can go for Fermat's Little Theorem which runs in $O(\log n)$ time and then check whether the number is prime or not by checking for existence of its divisors from $2$ to $\sqrt n$. But this will take $O(\sqrt n)$ time which is way beyond the machine's capability.

So how do I make Fermat's Little Theorem ultimate i.e. what are the values I'll need to run FLT with to ensure that it is prime or composite without having to go through $O(\sqrt n)$ operations?

-
Are you supposed to use Fermat's Little Theorem? –  Mohammad Ali Baydoun May 8 '13 at 16:16
Yes.A O(log n) algorithm is the only feasible algorithm. In fermat's little theorem, I select a value a(<=(n-1)) and find a^(p-1) mod p. What I want is the values of a such that I am sure that the number is prime. Or any other possible solution is also acceptable. –  sudeepdino008 May 8 '13 at 16:19
Why do you assume that $O(10^9)$ is 'way beyond the machine's capacity', what sort of machine is this? My machine executes $O(10^9)$ operations on a regular basis and I've run searches that did a couple of orders of magnitude more than that more than once... –  Steven Stadnicki May 8 '13 at 16:21
What programming language do you use exactly? –  Mohammad Ali Baydoun May 8 '13 at 16:23
There are no such values: en.wikipedia.org/wiki/Carmichael_number –  Micah May 8 '13 at 16:28