java - Java 中使用 eulers totient 和中国剩余定理的模幂

Question

编辑 - 澄清

我正在尝试使用拉格朗日和中国余数定理在 Java 中实现模幂运算。

例如，如果 N 是 55，已给出质因数 5 和 11，则 phi 为 40，所以我知道有 40 个与 N 互质的数字低于 55。我的老师说，这样做的方法是“使用拉格朗日定理，对 5 和 11 进行模数乘法以及 CRT 将两个结果结合起来”

我的问题是如何计算这些数字？我需要他们将它们放入中国余数定理中来完成计算，但我想不出一种聪明的方法来使用 phi(n) 作为结果来循环 N 。 N 将是一个非常大的数字，至少 1024 位。我可能走错了路，我是否需要所有这些素数？

我确实怀疑答案将与扩展的 euclid 函数有关，我已经对其进行了编码，因此如果我需要使用它的结果也没关系。

我不明白 How many numbers below N are coprimes to N? 中的代码所以这对我来说没有太大帮助，而且我看的数学论文很难理解，总和和乘积类型符号让我有点困惑。另外，一些答案使用平方根和对数，这实际上并不是 BigInteger 的选项(如果我错了，请纠正我)

有人可以用简单的英语给我答案吗？

可以向我展示代码，这更多的是一个学习练习，因为我要提交的答案使用 Montgomery。 (是的，我知道，奇怪的是我可以通过数学公式算出蒙哥马利，但这个拉格朗日加 CRT 让我完全困惑)

我已经通过我找到的一个例子做到了这一点。质因数是 7 和 5，因此 35 的 phi 是 24(我有一个有效的 Euler totient 函数)。

Answer 1

参见this answer一个已解决的例子。它准确地展示了如何通过对质因数进行模运算并组合结果来执行对复合模求模的模幂运算。