編集 - 明確化
ラグランジュと中国剰余定理を使用して、Java でべき乗剰余を実装しようとしています。
たとえば、素因数 5 と 11 が与えられた場合、N が 55 の場合、ファイは 40 です。したがって、55 未満の N に互いに素な数が 40 あることがわかります。 、5 と 11 を法とする数回の乗算と、両方の結果を結合するための CRT」
私の問題は、これらの数値をどのように計算するかです。計算を完了するためにそれらを中国の剰余定理に入れる必要がありますが、結果として phi(n) を使用して N を循環させる賢い方法は思いつきません。N は非常に大きな数になり、少なくとも 1024 ビットになります。ここで間違った方向に進んでいる可能性があります。これらすべての素数が必要ですか?
答えは拡張されたユークリッド関数に関連していると思われます。これはすでにコーディングしているので、その結果を使用する必要がある場合は問題ありません。
How many numbers below N are coprimes to N?のコードがわかりません。私にとってはあまり役に立ちませんし、私が見ている数学の論文を理解するのは非常に難しいと思います.合計と積のタイプの表記法は私を少し困惑させます. また、一部の回答では、実際には BigInteger のオプションではない平方根とログを使用しています (間違っている場合は修正してください)。
だれか平易な英語で答えてくれませんか??
コードを見せても問題ありません。提出する回答はモンゴメリーを使用しているため、これは学習課題です。(ええ、知っています。数学の公式からモンゴメリーを計算できるのは奇妙ですが、このラグランジュと CRT には完全に困惑しています)
私はこれまで、私が見つけた例に取り組みました。素因数は 7 と 5 であるため、35 の phi は 24 です (私は有効な Euler totient 関数を持っています)。