math - 大きな数の剰余の計算

Question

全て、

2^301 mod 77 を計算するにはどうすればよいですか? リンクStackOverflowをチェックアウトしました。しかし、625 mod 221 = 183 mod 221 のステップを理解していませんでした。変換はどのように行われたのでしょうか?

Answer 1

あなたの質問への回答については、こちらの質問をご覧ください。

基本的に、(X * Y) % Z == ((X % Z) * (Y % Z)) % Z.

したがって、出発点として、2^301 % 77 == ((2^150 % 77) * (2^151 % 77)) % 77. 適切な数になるまで分割を続けてから、再結合します。全体を通して、数値を適切なサイズに保つことができます。

Answer 2

おそらく、実際にたどったリンクが含まれていなかったため、投稿の2番目の部分がわかりません. しかし、あなたの問題は、このページを読んで剰余累乗の適切なアルゴリズムを実装することで解決できます