費馬在JS中的小定理

Question

我剛試圖在JavaScript中實現費馬的小定理。我試了兩種方法，a（p-1）mod p = 1和a p 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); 
} 

它不工作兩種方式，有沒有辦法解決呢？

Answer 1

在Javascript中^意味着XOR。對於exponentiation您需要Math.pow(x, y)。

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

Answer 2

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

Answer 3

在JavaScript中，克拉（^）是XOR運算符。你想要使用的是Math.pow（x，y）函數，它相當於x^y。

Answer 4

除了^與Math.pow（）問題其他人指出，您可能會遇到的下一個障礙 是JavaScript內置數字 類型的有限精度。一旦指數開始變大，您將很快超過可準確表示的Javascript 數字的範圍，因爲如果您希望 使用這樣的例程作爲素數測試，它們將會很快超出範圍。您可能需要查看 支持取冪 的Javascript bignum庫（例如this one）以及任意大整數的模數。