java - 了解 Miller Rabin 实现

Question

我正在学习 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;
    }

Answer 1

这部分代码

    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]