繰り返し自乗法の問題で困っています

7^327 (mod 853) の計算方法を教えて下さい。
以下の部分まで求めることはできました。

7^1≡7 (mod 853)
7^2≡49 (mod 853)
7^4≡695 (mod 853)
7^64≡
7^256≡

7^64と7^256は値が大きくなりすぎて値を出力できないです…
このような場合はどのように値を出力し、853で割ればよいのでしょうか…？

No.1 ベストアンサー 回答者： t_fumiaki 回答日時： 2021/05/29 21:10

7^2≡49 (mod 853)

7⁴=(7²)²≡49² (mod 853)≡695 (mod 853)

7⁸≡(7⁴)²≡695² (mod 853)≡227 (mod 853)

7¹⁶≡(7⁸)²≡227² (mod 853)≡349 (mod 853)

7³²≡(7¹⁶)²≡349² (mod 853)≡675 (mod 853)

7⁶⁴≡(7³²)²≡675² (mod 853)≡123 (mod 853)

7¹²⁸≡(7⁶⁴)²≡123² (mod 853)≡628 (mod 853)

7²⁵⁶≡(7¹²⁸)²≡628² (mod 853)≡298 (mod 853)



７³²⁷

＝7²⁵⁶×７⁷¹

＝7²⁵⁶×7⁶⁴×7⁴×7²×７

≡298×123×695×49×7 (mod 853)

≡828×695×343 (mod 853)

≡-25×-152×343 (mod 853)

≡388×343 (mod 853)

≡16 (mod 853)

この回答へのお礼

ありがとうございます！
理解できました！

お礼日時：2021/05/30 01:40

No.2 回答者： kairou 回答日時： 2021/05/29 21:31

7^4≡695 って、何？

7²=49 ならば 7³=343, 7⁴=2401 ですが。