1

これがフェルマーの小定理の実装です。なぜ機能しないのか誰か知っていますか？

私が守っているルールは次のとおりです。

  • 素数性をテストする数を n とします。
  • 2 から n-1 までの任意の整数 a を選択します。
  • a^n mod n を計算します。
  • a^n = a mod n かどうかを確認します。

マイコード:

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 未満の素数のリストです。これらの数値のいずれかを入力すると、「true」ではなく「false」が返されます。

最初の 100,008 個の素数

これが、コードが機能していないと私が信じる理由です。

4

3 に答える 3

1

他の人が指摘したように、力を奪うとすぐに溢れます。たとえば、30 などの小さな素数性をテストするために数値 n を選択し、乱数 a が 20 の場合、20^30 = 約 10^39、つまり >> 2^90 となります。（私は10 ^ 39のlnを取りました）。

BigIntegerを使用したいのですが、これには必要な正確なメソッドがあります。

public BigInteger modPow(BigInteger exponent, BigInteger m)

「値が (this^exponent mod m) である BigInteger を返します」

また、2 から n-1 までの単一の乱数をテストしても、何も「証明」されるとは思いません。2 から n-1 までのすべての整数をループする必要があります。

于 2012-12-27T23:42:29.523 に答える
1

Java では、double の精度は約 15 ～ 17 桁に制限されています。これは、 の値を計算することはできますがMath.pow(a,n)、非常に大きな数の場合、値が 15 桁を超えると正確な結果が得られる保証がないことを意味します。

a または n の値が大きいと、計算がその限界を超えます。たとえば Math.pow(3, 67)、 の値は9.270946314789783e31、最後の 3 桁の後の数字が失われることを意味します。このため、モジュロ演算を適用した後、正しい結果が得られる保証はありません ( example )。

これは、あなたのコードが、あなたが考えていることを実際にはテストしていないことを意味します。これは浮動小数点数の動作に固有のものであり、この問題を解決するには値を保持する方法を変更する必要があります。使用できますが、オーバーフローの問題が発生します (別の問題が発生した場合に備えてlong、 long はそれ以上の値を保持できません。2^64 - 13^67

1 つの解決策は、 Java SE APIBigIntegerの一部であるなど、任意の大きな数を保持するように設計されたクラスを使用することです。

于 2012-12-27T23:00:31.837 に答える