素数测试

在前两章的学习之后，我们了解了RSA加密原理。现在Bob准备用他的密钥和Alice进行通讯。为了创建RSA密钥，首先我们需要选择大素数p,q，主要的原因是，若p,q不是素数，则Bob需要对其进行因式分解再运算，其次，若素数不够大，则Eve可以对pq进行因式分解从而破解密码。

所以这节的主旨是，如何寻找大素数，只需要用到几个很简单的结论即可。例如，我们设Bob已经选择了一个大数

$\begin{aligned} n = 31987937737479355332620068643713101490952335301 \end{aligned}$

现在我们来判断其是否是素数，首先的是，经过简单的计算，小于100,0000的素数都不是其的因子。我们怀疑可能是真的素数，现在，我们计算$2^{n-1} \mod n$的值，那么经过计算机可以得到：

$\begin{aligned} 2^{n-1} \equiv 1281265953551359064133601216247151836053160074 \mod n \end{aligned}$

那么利用费马小定理，若p是素数，则$a^{p-1}\equiv 1 \mod p$（除非p$\mid $a，则由该同余式子，我们知道其是合数。现在我们描述一个更强一点的费马小定理

费马小定理（版本2

令p是素数，则

$\begin{aligned} a^p\equiv a \mod p ~~~\text{对所有整数a成立} \end{aligned}$

证明： 若$p\nmid a$，由费马小定理$a^{p-1}\equiv 1 \mod p$两边乘a就可以得到$a^p \equiv a \mod p$。其次，若$p\mid a$，由整除性，$a \equiv 0 \mod p$意味着定理两边都是0，矛盾。

现在，鲍勃可以利用它找到一个大素数

$\begin{aligned} n = 2967952985951692762820418740138329004315165131 \end{aligned}$

现在鲍勃选择计算$2^n \equiv 2 \mod n$，它现在准备逆用费马小定理的版本2.但这可能成功吗，答案是不一定的，考虑

$\begin{aligned} 2^{341} \equiv 2 \mod 341 ，但 341=11*31 \end{aligned}$

所以341不是一个素数。但这是个不错的开始，我们开始能缩小范围寻找素数。这促使我们做出如下的定义

定义

固定整数n，我们说整数a是判断n的合数性的证据，则

$\begin{aligned} a^n\not\equiv a \mod n \end{aligned}$

所以，若这种证据只有一个，则结合版本2的费马小定理则很容易验证n是否为合数，其次，讨论n是否是质数一个方法就是尝试非常多的数字$a_1,\cdots$。若其中有一个满足上述条件可以作为证据，则n是合数。但是，由于刚才的例子，若其中没有可以证明n是合数的证据，则我们继续对n是否是素数保持怀疑。

所以鲍勃需要一个比费马小定理更强的定理来生成素数。

命题

令p是奇素数且记

$\begin{aligned} p-1 = 2^kq & 其中q是奇数 \end{aligned}$

再设a是任何不被p整除的数，则a满足下述两个条件之一

  • $a^q\equiv 1 \mod p$
  • $a^q,a^{2q},\cdots ,a^{2^{q-1}q},a^{2^kq}$其中有一个模$p$与 $-1$同余

证明： 费马小定理告诉我们$a^{p-1}\equiv 1\mod p$，则对列表

$\begin{aligned} a^q,a^{2q},\cdots ,a^{2^{q-1}q},a^{2^kq} \end{aligned}$

的最后一个数有$\mod p$为1，注意列表每个数字都是前一个数字的平方，那么会有两种情况：

  1. 列表中第一个数模$p$余1.
  2. 列表中一些数字不模$p$余1，但它的平方模$p$余1.

但唯一满足两个条件的数

$\begin{aligned} b\not\equiv 1\mod p ~~~ 和 ~~~ b^2\equiv 1\mod p \end{aligned}$

是$-1$，因此表中应该有一个数与$-1$同余。

现在我们给出一种较强的米勒-拉宾合数检验流程：

给定测试数n，令a是待检验的合数性证据
1. 若n是偶数或者1 < gcd(a,n)，则n是合数
2. 记n-1 = $2^kq$，其中$q$是奇数
3. 令$a = a^q\mod n$
4. 若a$\equiv 1\mod n$，则测试失败，n不一定是合数
5. 做循环$i=0,1,\cdots,k-1$
6.若$a\equiv -1\mod n$，则测试失败
7.令$a=a^2\mod n$
8. 增加i的次数并持续的做步骤5的循环验证
9. 得到n是合数

从上述流程，我们把它重写为定义。

定义

设$n$是奇数且记$n-1 = 2^kq$，其中$q$是奇数。则满足gcd(a,n) =1且满足下述两个条件的整数$a$称为a是n的米勒-拉宾的合数性证据

  • $a^q\equiv 1 \mod n$
  • $a^{2^iq}\not\equiv -1 \mod n$对所有$i=0,1,\cdots,k-1$成立。

所以由上述流程，若a是n的一个合数性证据，则n一定是合数。现在假设 Bob 想要检查大数 n 是否可能是素数。为此，他使用一组随机选择的 a 值运行米勒-拉宾检验。为什么这比使用费马小定理检验更好？答案是，对于米勒-拉宾检验，我们可以避免诸如之前341这样的奇葩例子存在。因为我们严格的检验每个小于n-1的2的平方。而每个合数都有非常多的合数性证据。他们如下述定理所描述：

命题

令$n$是奇合数，则$1$到$n-1$的数字a中至少有$75\%$都是n关于米勒-拉宾的合数性证据

这意味着Bob在寻找合数的时候都有75%的概率找到。假设Bob十次都没有找到合数的证据，这样的概率是$(25\%)^{10}$，如果找了100次，这个概率将低至$(25\%)^{100}\approx 10^{-60}$

现在给出一个例子

例子

我们选择$a=2$和$n=561$做合数检验，现在有

那么就有

$\begin{aligned} 2^35 \equiv& 264 \mod 561\\ 2^{2*35}\equiv& 263^2 \equiv 166 \mod 561\\ 2^{4*35} \equiv& 166^2 \equiv 67 \mod 561\\ 2^{8*35} \equiv& 67^2 \equiv 1\mod 561 \end{aligned}$

由于第一个数字是$\mod 561$既不是1也不是余1，所以它是合数。其他数最后也不是mod 561 余-1，所以定理告诉我们它是合数。

例子2

我们取$n = 172947529$和$n-1 = 2^3 \cdot 21618441 = 2^3\cdot q$

我们引用检验法在$a = 17$上并试着找

对于第一个数$a^q, $它是$17^{21618441} \equiv 1\mod n$。测试不通过，现在尝试$a=3$，则$3^q \equiv -1 \mod n$，测试也不通过，但我们选择$a=23$的时候，有

所以$n$也是一个合数，但就是有点难发现。