java - RSA加密——寻找P和Q

Question

我试图通过找出 P 和 Q 来找出 RSA 加密(使用 Java)。这是我必须做的:

我必须生成两个随机数(P 和 Q)并遵循指南:

1. P & Q 的长度不得超过 7 位
2. P & Q 不能为 0 或 1(我在这一步中使用 Math.random() 函数)
3. P & Q 必须是素数
4. P & Q 不能是同一个数字(已经想通了)
5. (PQ) 必须至少为 256(已经知道了)

所以，基本上我是从这个开始的:

    double p = Math.random();
    double q = Math.random();

...然后尝试遵循上述 5 条准则。任何人都可以提示我如何计算出 #1 和 #3 吗？

谢谢!

Answer 1

您可以使用 Seive of Eratosthenes , 检查一个数是否为素数。

您可以做的是，生成小于 2^7 的所有质数列表(seive 有助于轻松构建)- 以便条件 #1 得以维持。然后从列表中随机选择 2 个数字，p 和 q。

以下是使用 seive 构建素数列表的方法:

List<Integer> getPrimeList(final int MAX_PRIME) {
    // Initialize a boolean array and set all values to true.
    bool[] isPrime = new bool[MAX_PRIME + 1];
    Arrays.fill(isPrime, true);

    List<Integer> primes = new ArrayList<>();

    // Start from 2. 0 and 1 are not prime.
    for(int i = 2; i * i <= MAX_PRIME; i++) {
        // If we've found a prime, set all it's multiples as composite,
        // and add this prime number to the list.
        if(isPrime[i]) {
            for(int j = i * i; j <= MAX_PRIME; j += i) isPrime[j] = false;
            primes.add(i);
        }
    }

    return primes;
}

您可以生成一次此列表，并在每次需要获取随机素数时使用它。

int getRandomPrime() {
    int randIndex = (int)(Math.random() * primes.size());
    return primes.get(randIndex);
}