java - 了解Miller Rabin的实现

我正在学习Miller Rabin，我将从https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Primality_Testing#Java
我觉得我对算法有一个很好的理解，但是主要是因为缺乏文档，实现并不容易如果有人能够浏览代码并解释我们在每个步骤中所做的事情以及原因，这将非常有帮助引用算法将非常有用。

Algorithm:
Input: n > 3, an odd integer to be tested for primality;
Input: k, a parameter that determines the accuracy of the test
Output: composite if n is composite, otherwise probably prime
write n − 1 as 2s·d with d odd by factoring powers of 2 from n − 1
LOOP: repeat k times:
   pick a randomly in the range [2, n − 2]
   x ← a^d mod n
   if x = 1 or x = n − 1 then do next LOOP
   for r = 1 .. s − 1
      x ← x^2 mod n
      if x = 1 then return composite
      if x = n − 1 then do next LOOP
      return composite
   return probably prime

实施：

import java.math.BigInteger;

import java.util.Random;

public class MillerRabin {

    private static final BigInteger ZERO = BigInteger.ZERO;
    private static final BigInteger ONE = BigInteger.ONE;
    private static final BigInteger TWO = new BigInteger("2");
    private static final BigInteger THREE = new BigInteger("3");

    public static boolean isProbablePrime(BigInteger n, int k) {
        if (n.compareTo(THREE) < 0)
            return true;
        int s = 0;
        BigInteger d = n.subtract(ONE); // n-1
        while (d.mod(TWO).equals(ZERO)) { //?
            s++;                          //?
            d = d.divide(TWO);            //?
        }
        for (int i = 0; i < k; i++) {    //LOOP: repeat k times
            BigInteger a = uniformRandom(TWO, n.subtract(ONE)); //?
            BigInteger x = a.modPow(d, n);  //x = a^d mod n
            if (x.equals(ONE) || x.equals(n.subtract(ONE))) // if x=1 or x = n-1, then do next LOOP
                continue;
            int r = 1;
            for (; r < s; r++) { // for r = 1..s-1
                x = x.modPow(TWO, n);  //x = x ^ 2 mod n
                if (x.equals(ONE))     //if x = 1, return false (composite
                    return false;
                if (x.equals(n.subtract(ONE))) //if x= n-1, look at the next a
                    break;
            }
            if (r == s) // None of the steps made x equal n-1.
                return false; //we've exhausted all of our a values, probably composite
        }
        return true; //probably prime
    }

    //this method is just to generate a random int
    private static BigInteger uniformRandom(BigInteger bottom, BigInteger top) {
        Random rnd = new Random();
        BigInteger res;
        do {
            res = new BigInteger(top.bitLength(), rnd);
        } while (res.compareTo(bottom) < 0 || res.compareTo(top) > 0);
        return res;
    }

最佳答案

这部分代码

    while (d.mod(TWO).equals(ZERO)) { //?
        s++;                          //?
        d = d.divide(TWO);            //?
    }

对应于

write n − 1 as 2^s·d with d odd by factoring powers of 2 from n − 1

只要d是偶数，它就除以2，然后s就递增循环后d必须是奇数并且s保持n-1中因子2的数目。
这部分

BigInteger a = uniformRandom(TWO, n.subtract(ONE)); //?

工具

pick a randomly in the range [2, n − 2]

关于java - 了解Miller Rabin的实现，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33852331/