Java的Rabin-Miller

Question

我有一个使用BigInteger类的函数RSA程序。但是，我使用内置的函数生成了我的素数。相反，im要求通过Rabin-Miller测试生成两个素数p和q。

rabin将分别运行，我将生成两个素数，然后将它们作为静态数字输入到我的RSA程序中，因此它们将是两个单独的程序。

拉宾-米勒在维基百科上的伪码

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(ONE) == 0)
            return false;
        if (n.compareTo(THREE) < 0)
            return true;
        int s = 0;
        BigInteger d = n.subtract(ONE);
        while (d.mod(TWO).equals(ZERO)) {
            s++;
            d = d.divide(TWO);
        }
        for (int i = 0; i < k; i++) {
            BigInteger a = uniformRandom(TWO, n.subtract(ONE));
            BigInteger x = a.modPow(d, n);
            if (x.equals(ONE) || x.equals(n.subtract(ONE)))
                continue;
            int r = 0;
            for (; r < s; r++) {
                x = x.modPow(TWO, n);
                if (x.equals(ONE))
                    return false;
                if (x.equals(n.subtract(ONE)))
                    break;
            }
            if (r == s) // None of the steps made x equal n-1.
                return false;
        }
        return true;
    }

    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;
    }

    public static void main(String[] args) {
        // run with -ea to enable assertions
        String[] primes = {"1", "3", "3613", "7297",
                "226673591177742970257407", "2932031007403"};
        String[] nonPrimes = {"3341", "2932021007403",
                "226673591177742970257405"};
        int k = 40;
        for (String p : primes)
            assert isProbablePrime(new BigInteger(p), k);
        for (String n : nonPrimes)
            assert !isProbablePrime(new BigInteger(n), k);


    }
}

现在我的问题：

由此，我将不得不生成x个素数，x个位长。让我们说:从512位中生成2个素数。知道该怎么做吗？

我也应该产生20个随机a。

我想我不需要程序或代码的结尾，只需要表示rabin-miller的数学运算，然后以某种方式产生X位长度的素数。

我该怎么做？

Answer 1

好的，所以您希望在2 ^ 511到2 ^ 512 - 1的范围内有一个大整数。这样，您就可以确保初始位设置为1，使其成为512位随机数。这可能有点奇怪，但512位随机数只包含511个随机位；显然，第一个位不可能是零，因为在这种情况下，这个数不是512位。

为此，您需要在0和2 ^ 511 - 1之间生成一个数字，然后向其中添加2 ^ 511。当然，您希望使用SecureRandom来生成安全密钥：

public static void main(String[] args) throws Exception {
    int bitsize = 512;
    SecureRandom rng = new SecureRandom();
    for (int i = 0; i < 1000; i++) {
        BigInteger randomForBitSize = createRandomForBitSize(bitsize, rng);
        System.out.printf("%d : %X%n", randomForBitSize.bitLength(), randomForBitSize);
    }
}

private static BigInteger createRandomForBitSize(int bitsize, Random rng) {
    BigInteger randomFromZero = new BigInteger(bitsize - 1, rng);
    BigInteger lowestNumberBitSize = BigInteger.valueOf(2).pow(bitsize - 1);
    BigInteger randomBitSize = lowestNumberBitSize.add(randomFromZero);
    return randomBitSize;
}