素数测试与二次剩余：欧拉定理与勒让德符号

"该资源主要讨论了素数测试和相关的数论概念，包括欧拉定理、卡迈克尔数、二次剩余、勒让德符号以及二次互反律。" 在计算机科学和密码学中，素数测试是至关重要的，特别是在生成RSA密钥对时。RSA是一种广泛使用的公钥加密技术，依赖于大素数的选择。为了有效地找到素数，我们需要理解一些数论基础。 1.1 欧拉定理 欧拉定理是数论中的一个重要定理，它扩展了费马小定理。它指出，如果a和n是正整数，且a与n互质（即它们的最大公约数为1），那么\( a^{\phi(n)} \equiv 1 \mod n \)，其中φ(n)是欧拉函数，表示小于等于n且与n互质的正整数的数量。如果\( a^n \not\equiv a \mod n \)，那么a被称为n的一个见证，表明n不是素数，即合数。然而，有些合数如561（3×11×17）没有明显的见证，这样的数被称为卡迈克尔数或伪素数。 1.2 二次剩余 二次剩余是指一个整数a的平方除以另一个素数p的余数等于0的情况，即存在x使得\( x^2 \equiv a \mod p \)有解。对于大于2的素数p，有\( \frac{p-1}{2} \)个不同的二次剩余。 1.3 勒让德符号 勒让德符号\( (a/p) \)是一个定义在奇素数p和整数a上的符号，当a是p的二次剩余时取1，非二次剩余时取-1，若p|a，则取0。这个符号与a的模p的乘幂模p-1的一半的关系是\( (a/p) \equiv a^{(p-1)/2} \mod p \)。 1.4 二次互反律 二次互反律是数论中的一个深奥定理，它描述了两个奇素数p和q之间的勒让德符号的乘积关系。具体来说，如果p和q都为奇素数，那么\( (p/q) = (-1)^{(p-1)(q-1)/4} (q/p) \)。这个定律在计算和理论中有着广泛的应用。 以上理论在素数测试中起到关键作用，如米勒-拉宾素性检验等算法就是基于这些概念。理解并能够应用这些原理，能帮助我们有效地判断大整数是否为素数，这对于加密技术的安全性至关重要。