Fermat's Little Theorem in Java

费马小定理 是对数量概念的一项基本贡献，广泛应用于算术和计算机科学。它在离散算术、密码学和基本验证中尤其真实。

该理论以法国数学家皮埃尔·德·费马的名字命名，该理论阐述了高位数作为模数的关键性质。

在本节中，我们将讨论该定理、其证明、相关程序包，以及在 Java 中的实现，然后对代码进行简洁的说明。

费马小定理

对于任何整数 a 和素数 p，费马小定理指出

这意味着当 a 提高到 p 次幂时，结果与 a 模 p 同余。当 a 不能被 p 整除时，会出现一个更实用且常用的变体。

在这种情况下，我们可以用 a 除（在模算术下是允许的，因为 a 在模 p 下具有乘法逆元）

费马小定理的证明

使用数学归纳法证明模算术

考虑整数集 S=1,2,…,p-1。由于 p 是素数，该集合中的所有元素都与 p 互质。现在，将 S 中的每个元素乘以 a（其中 gcd(a, p) = 1），得到一个新集（T=a⋅1,a⋅2,…,a⋅(p-1)）模 p。

1. T 中的每个元素模 p 都不同。如果 ( a⋅i≡a⋅j(modp))，那么通过除以 a（利用 a 在模 p 下具有逆元的事实），我们得到 ( i≡j(modp))，这意味着 ( i = j )。
2. 由于 T 在模 p 下包含与 S 相同的元素，因此它们的乘积模 p 也必须相等
   (a⋅1)⋅(a⋅2)⋅…⋅(a⋅(p-1))≡1⋅2⋅…⋅(p-1)(modp)
3. 简化后，a^(p-1)⋅(p-1)!≡(p-1)!(modp)。
4. 通过除以 (p-1)!（这是有效的，因为 ( (p-1)! ) 不能被 p 整除），我们得到 a^p-1≡1(mod p)。

因此，费马小定理得证。

费马小定理的应用

1. 模幂运算：费马小定理常用于高效计算模 p 的大幂。与直接计算 (a^b mod p) 相比，当 p 是素数时，我们可以将指数模 (p-1) 缩小，从而显著减少计算量。
2. 素性测试：费马小定理构成了类似费马素性测试的素性评估的基础。如果对于某个 a，a^p-1≢1(modp)，则 p 不是素数。
3. 密码学：该定理是 RSA 等公钥 密码学 算法的基础，其中大素数的模算术至关重要。
4. 寻找模逆元：当 p 是素数时，可以使用费马小定理将 (a mod p) 的模逆元计算为 (a^p-2 modp)。

文件名：FermatsLittleTheorem.java

输出

 
Enter the base (a): 
3
Enter the exponent (b): 
9
Enter the prime modulus (p): 
11
Result: 4   

解释

该程序包含一个函数 modularExponentiation()，该函数使用模幂运算的方法高效计算 (a^b mod p)。它通过重复平方基数 a，在每次乘法后对其进行模 p 约简，并且仅当指数 b 的当前位为 1 时才将其乘到结果中。

这种方法确保了以 b 的大小为对数的复杂度。在 main() 方法中，用户输入基数 a、指数 b 和素数模 p。如果 b 超出 p-1，则根据费马定理将其模 p-1 约简，以确保计算高效。

复杂度分析

时间复杂度：模幂运算函数以 O(log b) 的时间复杂度运行，其中 b 是指数。这种效率来自于重复平方方法，该方法在每次迭代中将指数除以 2。此外，相对于现代处理器中的典型字大小，模运算是常数时间。

空间复杂度：该算法使用 O(1) 的额外空间，因为它在整个计算过程中只维护几个 变量（result、a 和 b）。不需要额外的数据结构。

在最坏的情况下，当 b 没有模 p-1 约简时，时间复杂度仍然是 O(log b)。但是，应用费马小定理（将 b 模 p-1 约简）后，b 的有效大小大大减小，这使得算法在实践中更快。

结论

费马小定理是模算术的基石，对于涉及素数的绿色计算至关重要。它在密码学和素性测试中的实际效用，凸显了其在现代应用中的重要性。所呈现的 Java 实现演示了如何利用该定理进行模幂运算，展示了其优雅和强大。