编辑 - 澄清
我正在尝试使用lagrange和中文余数定理在Java中实现模幂运算 .
例如，如果N是55，已经给出了素数因子5和11，则phi是40，所以我知道在N低于55时有40个数字共同素数 . 我的导师说这样做的方法是“使用拉格朗日定理” ，以5和11为模的几次乘法和CRT结合两种结果“
我的问题是如何计算这些数字？我需要他们把它们放入一个中国余数定理来完成计算，但我想不出一个聪明的方法来使用phi（n）作为结果循环N. N将是一个非常大的数字，至少1024位 . 我可能在这里错误的轨道，我甚至需要所有这些素数？
我怀疑答案将与扩展的euclid函数有关，我已经对其进行了编码，所以如果我需要使用它的结果那就没问题了 .
我不明白How many numbers below N are coprimes to N?中的代码，所以它不是一个BigInteger的选项（如果我错了，请纠正我）
有人能用简单的英语给我答案吗？
向我展示代码是可以的，这更像是一次学习练习，因为我要提交的答案使用蒙哥马利 . （是的，我知道，奇怪的是，我可以用数学公式计算蒙哥马利但这个拉格朗日加CRT让我完全感到困惑）
通过我发现的一个例子，我已经做到了这一点 . 主要因素是七和五，所以35的phi是24（我有一个工作的Euler totient函数） .
2 回答
有关已完成的示例，请参阅this answer . 它通过对模数因子进行模运算并将结果组合起来，准确地显示了如何以模块化方式对模块进行模数表示 .
要找到所有与N互质的数字，只需在[1，N]上迭代euclid GCD（）算法 . 如果GCD（a，N）== 1那么a，N是互质的