CODEWITHSUNDEEP
calgorithm
user2291995
user2291995

Reputation:

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

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?

Upvotes: 0

Views: 193

Answers (1)

user448810
user448810

Reputation: 17866

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.

Upvotes: 1

Related Questions