CODEWITHSUNDEEP
cprimes
yasar
yasar

Reputation: 13738

How does this isPrime function work?

I was reading http://www2.informatik.hu-berlin.de/~weber/slipOff/hashmap_c.html and having hard time understanding how this function works:

static unsigned long isPrime(unsigned long val)
{
  int i, p, exp, a;

  for (i = 9; i--;)
  {
    a = (rand() % (val-4)) + 2;
    p = 1;
    exp = val-1;
    while (exp)
    {
      if (exp & 1)
        p = (p*a)%val;

      a = (a*a)%val;
      exp >>= 1;
    }

    if (p != 1)
      return 0;
  }

  return 1;
}

If its name is any indicator of what it does, it checks whether a number is prime. However, I can't figure out how it does that.

I can understand what each statement do, but I don't see how it works.

Upvotes: 3

Views: 514

Answers (1)

advocateofnone
advocateofnone

Reputation: 2541

Basically if a number q is prime then fermat theorem states that

a(q - 1) = 1 (mod q)

where a and q are co-prime.

So basically the while loop is just calculating the some random number to the power val-1 and also taking the modulo val. If the end result is 1, it says val is prime otherwise not. But in general this can be true for some random value of a even if p is not prime. Thus we generally take a few random numbers and repeat the same procedure, if all give p=1 in the end we say that val is prime with high probability ( the outer loop is for repeating the procedure , more iterations more is the probability that your answer is correct). So basically if val is prime this method will correctly detect it as prime but if it is composite it might detect is as prime, with probability of that being low. Although this method is not as effective as other methods.

Upvotes: 6

Related Questions