-1
私は、64ビット整数(long)で機能するスクラッチ(プリミティブとストリングのみ)からMiller-Rabin素数テストを実装しようとしています。私はWikipediaからJavaと擬似コードだけでなく、他のさまざまなWebサイトを試してみました。これまでは、非常に小さな数字しか正しく機能していませんでした。ほとんどの数値は、53や101などの間違ってマークされたコンポジットです。私は、問題のどこにあるかを見るためにコードのさまざまなセクションを追跡しようとしました。それは一番内側のループのようです。私は特定の問題が何であるか分からない。どんな助けもありがとうございます。ありがとう!ここで Miller-Rabin Primality Test頻繁に素数のコンポジットを返します
は私のコードです:public class PrimeTest
{
public static void main(String[] args)
{
PrimeTest app = new PrimeTest();
}
private PrimeTest()
{
long n = 53; // Change to any number. 53 is prime, but is reported as composite
if (checkPrime(n, 10))
{
System.out.println(n + " is prime.");
}
else
{
System.out.println(n + " is not prime.");
}
}
// Check if n is prime with 4^(-k) change of error
private boolean checkPrime(long n, int k)
{
// Factor n-1 as d*2^s
long d = n - 1;
int s = 0;
while (d % 2 == 0)
{
d /= 2;
s++;
}
// Repeat k times for 4^-k accuracy
for (int i = 0; i < k; i++)
{
long a = (long) ((Math.random() * (n - 3)) + 2);
long x = modPow(a, d, n);
if (x == 1 || x == (n - 1))
{
continue;
}
int r;
for (r = 0; r < s; r++)
{
x = modPow(x, 2, n);
if (x == 1)
{
return false;
}
if (x == (n - 1))
{
break;
}
}
if (r == s)
{
return false;
}
}
return true;
}
// Return (base^exp) % mod
private long modPow(long base, long exp, long mod)
{
if (mod == 1)
{
return 0;
}
long result = 1;
base = base % mod;
while (exp > 0)
{
if ((exp & 1) == 0)
{
result = (result * base) % mod;
}
exp = exp >> 1;
base = (base * base) % mod;
if (base == 1)
{
break;
}
}
return result;
}
}
する必要がありますたくさんのコードがここにあります。あなたの問題がどこにあるのかを明確にするためには、問題を直接引き起こしていないコードを削除してください。もしそれを10行以下に減らすことができれば、私はdownvoteを引っ込めることを検討します。参照:[最小限で完全で検証可能な例の作成方法](http://stackoverflow.com/help/mcve)と[小規模プログラムのデバッグ方法](https://ericlippert.com/2014/03/05)/how-to-debug-small-programs /) –