第三次公钥实验

第三次NTL相关理论分析

$Fermat$

基于费马小定理，对于素数p有：

$$a^{p-1} \equiv 1 \pmod p$$

费马素性检验的基本思想是：对于给定的数$n$，随机选择一个整数$a$，如果$a^{n-1} \mod n = 1$，则$n$可能是素数，否则$n$是合数。所以计算$a^{n-1}$ 是否$\mod n$余$1$就可以粗略地判断一个数是否为素数，多次实验可以提高判断的正确率。

$Solovay-Strassen$

基于$Jacobi$符号，对于素数p有：

$$a^{\frac{p-1}{2}} \equiv \left(\frac{d}{p}\right) \pmod p$$

$Solovay-Strassen$素性检验的基本思想是：对于给定的数$n$，随机选择一个整数$a$，如果$a^{\frac{n-1}{2}} \mod n = \left(\frac{d}{p}\right)$，则n可能是素数，否则n是合数。所以计算$a^{\frac{n-1}{2}} \mod n$ 是否等于$\left(\frac{d}{p}\right)$就可以粗略地判断一个数是否为素数，对于这个式子，p是素数，则这个式子一定成立，但是满足这个式子的数不一定是素数，所以需要多次实验来提高正确率。

$\left(\frac{d}{p}\right)$的计算方式为将$p$分解为素数的乘积，然后计算每个素数的$Legendre$符号，最后将每个素数的$Legendre$符号相乘，得到的结果就是$\left(\frac{d}{p}\right)$的值，所以我们可以通过递归的方式来设计函数来计算$\left(\frac{d}{p}\right)$的值。

$Miller-Rabin$

基于Fermat小定理及其引理，假设 $n$ 是一个奇素数，且$n > 2$，此时$n − 1$必然为一个偶数，可以被表示为$2^{s}· d$的形式对于素数p有：

$$a^{2^{s}d} \equiv 1 \pmod p$$

对上式引理，有：

$$a^{2^{s-1}d} \equiv \pm 1 \pmod p$$

要是结果为$-1$，我们可以一直做取平方根的操作，最终简化得到：

$$a^{d} \equiv 1 \pmod p$$

即如果随机选取一个整数$a(1<a<n-1)$，使得对任意$r(0<r<s-1)$能使得$a^{2^{r}d} \equiv -1 \pmod p$，或者$a^{d} \equiv 1 \pmod p$，则$n$可能是素数，否则$n$一定是合数。所以计算以上就可以粗略地判断一个数是否为素数，对于这个式子，$p$是素数，则这个式子一定成立，但是满足这个式子的数不一定是素数，所以需要多次实验来提高正确率。

第三次NTL实验结果分析

以上三种检测方式的结果相同，对于测试数据：

\begin{align*} & (1) : \text{110051}\\ & (2) : \text{181901} \\ & (3) : \text{410041} \\ & (4) : \text{769278483628740226167794860061798621150347827303123617} \\ & (5) : \text{1145169445838968401708775025324117691359108534130461797} \\ & (6) : \text{10221010696405715306543052536189788914202546069582395786318675605080695490061540792643337272761347929547435453096763879202778100241119332976939005254498509} \\ & (7) : \text{121833461555674589736949565105565398169972481095177279279180138710896774154003337848675741258281654778624527588581168846185536461680316105333272201631014303487127548432732619231950555289262966188279062132341418648002287985828399879599539829714743040809931482374894459448142788978098724300047711192868698944741} \\ \end{align*}

依次的素性检测结果为：

$$\begin{array}{|c|c|c|} \hline \text{测试数据} & \text{结果} \\ \hline (1) & \text{True} \\ (2) & \text{False} \\ (3) & \text{False} \\ (4) & \text{False} \\ (5) & \text{False} \\ (6) & \text{True} \\ (7) & \text{True} \\ \hline \end{array}$$

经验证为正确答案。在实验中，我们发现，对于大数，$Miller-Rabin$的速度要比$Fermat$和$Solovay-Strassen$快很多，但是对于小数，$Miller-Rabin$的速度要比$Fermat$和$Solovay-Strassen$慢很多，所以我们可以根据数的大小来选择不同的算法来进行素性检测。同时，对于检测次数，我们发现，检测次数越多，正确率越高，但是速度越慢，所以我们可以根据需要来选择检测次数。