計算したい内容:
a b c d . . . mod m
この数値は大きすぎますが、 a 、 b 、 c 、...、 m は単純な 32 ビット int に収まるので、効率的な方法を知っていますか。
何か案は？
警告：この問題は、a b mod mを見つけることとは異なります。
また、 a b c は(a b ) cと同じではないことにも注意してください。後者は a bcと等しくなります。指数は右結合です。
ベストアンサー1
a b c mod m = a b c mod n mod m、ただしn = φ(m)オイラーのトーティエント関数。
m が素数の場合、n = m-1 となります。
編集: Nabb が指摘したように、これは a が m と互いに素である場合にのみ当てはまります。したがって、最初にこれを確認する必要があります。