质数世代中的随机数据

Question

在密钥生成过程中 GnuPG 显示：

 We need to generate a lot of random bytes. It is a good idea to perform
some other action (type on the keyboard, move the mouse, utilize the
disks) during the prime generation; this gives the random number
generator a better chance to gain enough entropy.

现在我想知道：这个随机数据在素数生成中有什么用？我熟悉 Erathosthénis 的筛子，但想不出将此类数据应用到筛子中。我也知道Rabin-Miller strong test可以使用随机数据作为mod n使用，但不确定是不是这样。

Answer 1

2048 位 RSA 中的 public 模数，例如是两个 1024/1025 位随机素数的乘积，其二进制分解将最高有效位和最低有效位设置为 1。其余的是随机的，并且对整个数字进行素数测试：

// to generate a 16-bit prime
// the MSB must be one, if the prime is to be 16-bit
// and the LSB must be one, because all primes (p > 2) are odd
a = rand();     // between 0 and MAX_INT
a &= 0x7ffe;    // Leave 14 middle bits as is
a |= 0x8001;    // Force MSB and LSB to one
while (!is_prime(a)) a += 2;

因此我们从一个随机整数开始，然后将候选值增加 2，直到找到一个。调用 is_prime 的次数通常在 log2(N) (IIRC) 的范围内。这可以通过计算 a += N(a) 稍微改善，其中 N 使用 SoE 跳过几个小素数的倍数。

取其中两个随机数可用于生成 31-32 位 RSA 模数。

在实践中，素数测试是通过 Rabin-Miller 或其他强大的测试进行的，因为 SoE 需要大量内存并且需要难以理解的步骤数才能跳过 sqrt(2^1024) 范围内的所有素数~= 2^512.

质数世代中的随机数据

Random data in prime generation

primes

cryptography

rsa

number-theory

modular-arithmetic