6

我只是尝试在 JavaScript 中实现费马的小定理。我尝试了两种方法，a^(p-1) mod p = 1 和 a^p mod p = a mod p。

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

和

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

这两种方法都不起作用，有什么办法可以解决吗？

4

6 回答 6

9

在 Javascript^中意味着XOR。对于幂运算，您需要Math.pow(x, y).

function fermat(a, p) {
  return Math.pow(a, p - 1) % p === 1;
}
于 2010-08-03T19:59:57.587 回答
7

而不是 ^，您需要使用 Math.pow

于 2010-08-03T19:59:46.180 回答
3

除了其他人指出的 ^ 与 Math.pow() 问题之外，您可能面临的下一个障碍是 Javascript 内置数字类型的有限精度。一旦指数开始变大，您将很快超过可精确表示的 Javascript 数字的范围，因为如果您想使用这样的例程作为素数测试，它们就会如此。您可能想要查看支持任意大整数的取幂和取模的 Javascript bignum 库（例如， this one ）。

于 2010-08-03T20:17:36.973 回答
2

在 javascript 中，克拉 (^) 是 XOR 运算符。您要使用的是 Math.pow(x,y) 函数，它等效于 x^y。

于 2010-08-03T20:01:06.170 回答
0

这是我的代码（JavaScript），用于根据费马小定理检查数字是否为素数。

    function getRandomInt(min,max) { /* getting a random between given max and min values */
        min = Math.ceil(min);
        max = Math.ceil(max);
        return Math.floor(Math.random()*(max-min))+min;
    }

    function getGCD(a,b) { /* getting the greatest common divisor */
        var tmp;
        while (b !== 0) {
            tmp = b;
            b = a%b;
            a = tmp;
        }
        return a;
    }

    function getPower(a,b,p) { /* getting the a^b mod p */
        if (b == 1)
         return a%p;
        else {
         x = getPower(a,Math.floor(b/2),p);
         if (b%2 == 0) 
          return (x*x)%p;
         else return (((x*x)%p)*a)%p;
        }
    }

    function fermatTesting(Num) { //Checking Num by using Fermat's theorem
        var a = getRandomInt(2,Num-1);
        if (getGCD(a,Num) !== 1) {
            return "COMPOSITE";
        }
        else {
            if (getPower(a,Num-1,Num) !== 1) {
                return "COMPOSITE";
            }
            else {
                return "PRIME"; 
            }
        }
    }

    console.log(fermatTesting(57)); //Displays "COMPOSITE"
于 2018-05-19T09:56:21.090 回答
0

没有什么比回答一个十一岁的问题更好的了！

由于现在是 2021 年，我们支持BigInt，它支持任意精度以及幂运算符 ( **) 和模运算符 ( %)。

接受答案中的函数可以重写为

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

其中a和p是 BigInt 值。

于 2021-10-21T02:59:45.273 回答