Fermat's Theorem in JS

Question

I just tried to implement Fermat's little theorem in JavaScript. I tried this in both directions, 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 ); } 

This does not work in both directions, is there a way to fix this?

Answer 1

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

 function fermat(a, p) { return Math.pow(a, p - 1) % p === 1; } 

Answer 2

Instead of ^, you need to use Math.pow

Answer 3

In addition to the problem ^ vs. Math.pow () others have indicated that the next hurdle you are likely to encounter is the limited precision of Javascript's built-in numeric types. You will very quickly exceed the range of accurately represented Javascript numbers when exponents begin to get large, as they will if you want to use a procedure such as a primacy test. You can look into the javascript bignum library (like this one ), which supports exponentiation and a module for arbitrarily large integers.

Answer 4

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