Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
There are no such values: en.wikipedia.org/wiki/Carmichael_number –  Micah May 8 '13 at 16:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.