how to show a number is prime or not if number is <2^63?

Question

I have read about Fermat's primality test... it was nice but there was one flaw about Carmichael number... it shows that it coulnd't find the distiguish them with prime numbers..

My code:

bool fermat(long long p,int itr)
{
  if(p==1)return false;
  for(int i=0;i<itr;i++)
  {
    long long a=rand()%(p-1)+1;
    if(modulo(a,p-1,p)!=1)
       return false;
    else
       return true;
  }
}

How can I find that p is prime without getting into the problem of Carmichael number? Any modification of this algo?

If you have a range, it's probably better to generate a sieve. — Luchian Grigore, Jun 21 '14 at 16:22
i have edited my heading..actually i want to find if a number is prime or not..the number may be 2^63 a huge number — , Jun 21 '14 at 16:25
There are a number of [probability tests](http://en.wikipedia.org/wiki/Prime_number_theorem) you can use for huge numbers. — Sani Huttunen, Jun 21 '14 at 16:30
2^63 isn't that big really, you can even do a plain old trial-division and ok you wouldn't win the contest but it wouldn't take crazy long. You could also look at [this old answer](http://stackoverflow.com/a/7205495/555045) and extend it to a larger range. — harold, Jun 21 '14 at 16:30
As @harold says, 2`63 isn't that big. With at BigNum class you can easily do a [Sieve of Erastothenes](http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) and in a very short time find out if a number is prime. — Sani Huttunen, Jun 21 '14 at 16:33
@setu probably not. You could try Miller-Rabin. Either by itself or to strengthen Fermat's test. — harold, Jun 21 '14 at 16:38
yes..i want to strengthen Fermat's test to avoid that carmichael numbers..any idea about that?? — , Jun 21 '14 at 16:40
@setu:if you want working source code for miller rabin test, i can post for you rbetter understanding of miller rabin — prashantitis, Jun 21 '14 at 21:12
i have got it from topcoder forum but some of its code i am not understanding... — , Jun 22 '14 at 13:07

score 1 · Answer 1 · answered Jun 21 '14 at 17:30

Pseudocode for the Miller-Rabin test, which gives a probabilistic answer, is shown below:

function isPrime(n, k=5)
    if n < 2 then return False
    for p in [2,3,5,7,11,13,17,19,23,29]
        if n % p == 0 then return n == p
    s, d = 0, n-1
    while d % 2 == 0
        s, d = s+1, d/2
    for i from 0 to k
        x = powerMod(randint(2, n-1), d, n)
        if x == 1 or x == n-1 then next i
        for r from 1 to s
            x = (x * x) % n
            if x == 1 then return False
            if x == n-1 then next i
        return False
    return True

That uses k (default 5) random bases. If you know in advance the limit on n you could chose a set of bases that gives a deterministic answer; see miller-rabin.appspot.com for lists of bases for various n.

how to show a number is prime or not if number is <2^63?

1 Answers1