Fermat的小實現問題的實現

下面是我對Fermat的小定理的實現。有誰知道它爲什麼不起作用？Fermat的小實現問題的實現

下面是我遵循的規則：

設n是數以測試素性。
選取2到n-1之間的整數a。
計算a^n模n。
檢查是否a^n = a mod n。

mycode的：

int low = 2; 
int high = n -1; 
Random rand = new Random(); 

//Pick any integer a between 2 and n-1. 
Double a = (double) (rand.nextInt(high-low) + low); 

//compute:a^n = a mod n 
Double val = Math.pow(a,n) % n; 

//check whether a^n = a mod n 
if(a.equals(val)){ 
return "True"; 
}else{ 
return "False"; 
}

這是素數小於100000的列表，每當我在任何這些數字的輸入，而不是越來越「真實」，我得到「假」。

The First 100,008 Primes

這就是爲什麼我相信代碼是不工作的原因。

來源

2012-12-27 evthim

它以什麼方式不起作用？ – Hbcdev

爲什麼'rInt'和'val'' Double's的值應該總是爲'int's？ – MrSmith42

我會第一次替換'if（a。等於（val））{ return「True」; } else { return「False」; }帶'返回a.equals（val）;' - 出於兩個原因。 1）返回'boolean'比返回'True'或'False'（或者它是'true'或'false'或..？）的'String'要簡單得多。 2）它更短。 –

在java中，一個double只有15到17位的精度有限。這意味着，雖然您可以計算出Math.pow(a,n)的值，但對於大數字，您無法保證一旦該值超過15位數字，就會得到確切的結果。

對於a或n的較大值，您的計算將超出此限制。例如， Math.pow(3, 67)將具有值9.270946314789783e31，這意味着最後3個之後的任何數字都會丟失。因此，在應用模運算後，您無法保證獲得正確的結果（example）。

這意味着您的代碼實際上不會測試您的想法。這是浮點數的工作方式固有的，你必須改變你持有你的值的方式來解決這個問題。你可以使用long但隨後你就必須有溢出的問題（長期不能持有超過2^64 - 1更大的值如此反覆，在3^67你有另外一個問題的情況下。

一種解決方案是使用設計的一類舉例來說，BigInteger是Java SE API的一部分

來源

2012-12-27 23:00:31 ARRG

正如其他人已經注意到的那樣，採取權力會很快溢出，例如，如果你選擇一個數字n來檢驗素數小到可以說， 30，隨機數a爲20,20^30 = 10^39，這是>> 2^90（我拿了10^39中的ln）

你想用BigInteger，其中甚至有你想要的確切方法：

public BigInteger modPow(BigInteger exponent, BigInteger m)

「返回一個BigInteger，其值是（this ^指數模m）」

另外，我不認爲測試2和n-1之間的單個隨機數將「證明」任何事情。你必須遍歷2和n-1之間的所有整數。

來源

2012-12-27 23:42:29 user949300

沒錯，一個基本篩比證明一個數的素性（初始性？初始性？）更有效。但是，通過弄清如何正確編碼算法，可以學到很多東西，包括編程和數學。 – iamnotmaynard

Fermat的小實現問題的實現

回答

相關問題