views:

91

answers:

4

Hi,

I just tried to implement Fermat's little theorem in JavaScript. I tried it both ways, a^(p-1) mod p = 1 and a^p mod p = a mod p.

function fermat(a, p) {
  return (((a ^ (p - 1)) % p) === 1);
}

and

function fermat(a, p) {
  return ( ( a^p ) % p ) === ( a % p );
}

It doesn't work both ways, is there any way to fix that?

+6  A: 

Instead of ^, you need to use Math.pow

carnold
+6  A: 

In Javascript ^ means XOR. For exponentiation you need Math.pow(x, y).

function fermat(a, p) {
  return Math.pow(a, p - 1) % p === 1;
}
Mark Byers
+1  A: 

In javascript, the carat (^) is the XOR operator. What you want to use is the Math.pow(x,y) function which is equivalent to x^y.

Mike Clark
+2  A: 

In addition to the ^ vs. Math.pow() issue others have pointed out, the next hurdle you will likely face is the limited precision of the Javascript built-in numeric types. You will very quickly exceed the range of exactly representable Javascript numbers once the exponents start getting large, as they will be if you're wanting to use a routine like this as a primality test. You may want to look into a Javascript bignum library (for example, this one) that supports exponentiation and modulus for arbitrarily large integers.

Jim Lewis
yes, I know that. I already implemented Fermat's little theorem in Java and got an extremely fast response, but when I tried to get all primes up to 10k, I ran out of limits. But this is just for a test on jsperf (http://jsperf.com/prime-numbers/4), and it performs nearly as fast as some solutions using a cache (for half a million operation-loops). I'm fine with that result…
FB55