编辑 - 澄清
我正在尝试使用拉格朗日和中国余数定理在 Java 中实现模幂运算。
例如，如果 N 是 55，给定素数 5 和 11，phi 是 40，所以我知道有 40 个数字与低于 55 的 N 互质。我的导师说这样做的方法是“使用拉格朗日定理, 几个模 5 和 11 的乘法和 CRT 结合两个结果"
我的问题是如何计算这些数字？我需要他们将它们放入中国剩余定理中来完成计算，但我想不出一个聪明的方法来使用 phi(n) 循环遍历 N。N 将是一个非常大的数字，至少 1024 位。我可能在这里走错了路，我什至需要所有这些素数吗？
我确实怀疑答案将与扩展的 euclid 函数有关，我已经对其进行了编码，所以如果我需要使用它的结果，那很好。
我不明白N 以下多少个数与 N 互质？所以这对我没有多大帮助，而且我看的数学论文很难理解，总和和乘积类型符号让我有点困惑。此外，一些答案使用平方根和日志，这不是 BigInteger 的真正选项（如果我错了，请纠正我）
谁能用简单的英语给我答案？？
可以给我看代码，这更像是一个学习练习，因为我要提交的答案使用蒙哥马利。（是的，我知道，奇怪的是我可以从数学公式中算出蒙哥马利，但这个拉格朗日加 CRT 让我完全困惑）
我已经做到了这一点，通过我找到的一个例子来工作。素数是七和五，所以 35 的 phi 是 24（我有一个工作的欧拉函数）。