1

私は Java で Miller-Rabin 確率検定を実演するプログラムを書いています。コードはかなり完成しました...

import java.util.Random;
import java.util.Scanner;

/**
 * Program to demonstrate Miller-Rabin primality testing
 * 
 * @author Nick Gilbert
 */
public class MillerRabin
{
    public static void main(String[] args)
    {
        //Setting up for algorithm
        Scanner in = new Scanner(System.in);
        Random rn = new Random();
        int n = 0, k = 0, m = 0, a = 0;
        double b = 0;
        boolean probablyPrime = false;

        //Asking user for an odd n
        do
        {
            System.out.print("Enter an odd number to test for primality: ");
            n = in.nextInt();
        }
        while(n % 2 == 0);

        //Calculating k and m
        m = n - 1;
        while(m % 2 == 0)
        {
            m /= 2;
            k++;
        }

        //Generating random a
        //a = rn.nextInt(n-1);

        //Outputting numbers that will be used in algorithm
        System.out.println("k = " + k);
        System.out.println("m = " + m);
        System.out.println();
        a = 86;
        System.out.println("A = " + a);

        //Running the algorithm
        //b_{0}
        b = Math.pow(a, m) % n;
        System.out.println("b0 = " + b);
        if(Math.abs(b) == Math.abs(1 % n)) //Dealing with +/- case via absolute value
        {
            probablyPrime = true;
        }
        else
        {
            //b_{1-(k-1)}
            for(int i = 1; i < k; i++) //Going to k-1
            {
                b = Math.pow(b, 2) % n;
                System.out.println("b" + i + " = " + b);
                if(Math.abs(b) == Math.abs(1 % n)) //Dealing with +/- case via absolute value
                {
                    probablyPrime = true;
                    break;
                }
            }
        }

        //Printing result
        if(probablyPrime)
        {
            System.out.println("Probably Prime");
        }
        else
        {
            System.out.println("Definitely Composite");
        }


    }
}

問題を示すために、値として 86 をハードコーディングしました。a を m に増やし、法 n をとって初めて b を計算するところは、計算が正しくありません。86^19 % 153 に対する正しい答えである 86 の b0 を与える代わりに、b0 は 107 に等しくなります。デバッガーで自分の値をチェックしましたが、それらは正しいです。a^m の値も確認したところ、86^19 が得られたので、モジュラス部分で問題が発生しました。残念ながら、何が数学を台無しにしているかわかりません。

4

3 に答える 3

2

doubleJava (および任意の IEEE システム) の精度は、15 ～ 16 桁の精度しかありません。これより大きい数値を使用すると、表現エラーが発生します。

最も可能性が高いのは、任意の精度を処理するだけでなく、電力とモジュラスに最適化されたメソッドを持つ BigInteger を使用することです。

// 86^19 % 153
BigInteger result = BigInteger.valueOf(86).modPow(BigInteger.valueOf(19), BigInteger.valueOf(153));
System.out.println(result);

版画

86
于 2015-03-30T02:41:03.843 に答える
1

ここで、Math.pow は double を返すため、double のモジュラスを取得しても役に立ちません (double で Mod を取得しないでください。得られるものについては誰も責任を負いません)。

(89^19) はおよそ 2^122 なので、unsigned long(2^64-1) はこれらの数値を保持しないことに注意してください。double の精度は 2^53 です (mod に double を使用しないでください。数論は整数に基づいています)。より小さい値を試すか、BigIntegerクラスを使用してください。

于 2015-03-30T02:39:45.547 に答える
0

プリミティブ データ型にはサイズが設定されているため、精度が制限される可能性があります。

Java には、シナリオに適したBigIntegerクラスがあります。

于 2015-03-30T02:40:28.460 に答える