问BBS中剩余$3$除以$4对$p$和$q$的重要意义

EN

这是为了最大化发电机的状态空间经过多个步骤。经过s步骤后，BBS生成器将具有状态i^{2^s}\mod N，其中i为初始种子，N为模数。

特别是，状态必须是2^s_th幂模N.剩余模N的个数，也就是2^s_th幂的乘积，是2^s_th幂模p乘以2^s_th幂模q数的乘积，因此我们希望最大限度地利用这两者。

不同的2^s、th幂模a素p的个数是(p-1)/2^{\mathrm{min}(s,k)}，其中2^k是2除以p-1的最大幂。为了最小化这一点，我们选择素数p，其中k=1 (resp )。q)。这些素数是3模4，对于这些素数，2^s的第四次幂数将是(p-1)/2 (resp )。(q-1)/2)，因此，2^s_th幂模N的个数将是(p-1)(q-1)/4。