a^mをnで割った余りを求める。
mを2^iの和で表す。m=Σ(t[i]×2^i)
a^(2^k)を計算する。a^(2^k)≡s[k]
a^m≡Π(t[i]×s[i]) (mod n)
【例】7^39を83で割った余り
【解】(mod 83)を略記する。
39=32+4+2+1
7^2≡49
7^4≡49^2≡77≡-6
7^8≡(-6)≡36
7^16≡36^2≡51≡-32
7^32≡(-32)^2≡28
7^39=(7^32)×(7^4)×(7^2)×(7^1)
≡28×(-6)×49×7
≡-22
≡61 (mod 83)
A【aとnが互いに素のとき】
①【nが素因数分解できるとき】
【例】5^300を2021で割った余り
【解】
x=5^300とする。
2021=43×47
5^300≡a (mod 43)
かつ
5^300≡b (mod 47)
フェルマーの小定理より、
5^42≡1 (mod 43)
x=(5^42)^7×5^6 (mod 43)
5^2≡25
5^4≡25^2≡23
x≡5^6≡(5^4)×(5^2)≡23×25≡16
フェルマーの小定理より、
5^46≡1 (mod 47)
x=(5^46)^6×5^24≡5^24
5^4≡25^2≡14
5^8≡14^2≡8
5^16≡64≡17
x≡5^24≡(5^16)×(5^8)≡17×8≡42
よって、
x≡16 (mod 43)
x≡42≡-5 (mod 47)
47s≡16 (mod 43)→4s≡16→s≡4
43t≡-5 (mod 47)
→-4t≡-5→4t≡5≡52→t≡13
x≡47×4+43×13≡747 (mod 2021)
指数mが大きく、nが大きく素因数分解できるときは、連立合同式にした方が楽になる。
②【mが大きいとき】
pを素数とする。
フェルマーの小定理を利用
m=(p-1)t+r
a^m≡{a^(p-1)}^t×a^r≡a^r (mod p)
【例】7^200を83で割った余り
【解】(mod 83)を略記する。
フェルマーの小定理より、7^82≡1
200=82×2+36
7^200≡(7^82)^2×7^36≡7^36
36=32+4
7^2≡49
7^4≡49^2≡77≡-6
7^8≡(-6)≡36
7^16≡36^2≡51≡-32
7^32≡(-32)^2≡28
よって、
7^36≡(7^32)×(7^4)≡28×(-6)
≡-168≡-2≡81 (mod 83)
③【mが2^kより少し小さいとき】
【例】7^30を83で割った余り
【解】(mod 83)を略記する。
7^2≡49
7^4≡49^2≡77≡-6
7^8≡(-6)≡36
7^16≡36^2≡51≡-32
7^32≡(-32)^2≡28
x=7^30とする。
(7^2)x≡28
49x≡28
7x≡4
4≡4 (mod 7)
83≡-1 (mod 7)
-s≡-4 (mod 7)→s≡4
7x≡4+83×4≡4+332≡336
x≡48 (mod 83)
B【aとnの最大公約数g≠1のとき】
【例】6^100を52で割った余り
【解】
x=6^100とする。
52=2^2×13
k≧2のとき6^k≡0 (mod 4)より、
x≡0 (mod 4)
フェルマーの小定理より、
6^12≡1 (mod 13)
x≡(6^12)^8×(6^4)≡6^4
6^2≡36≡-3→6^4≡9
x≡9 (mod 13)
よって、
x≡0 (mod 4)
x≡9 (mod 13)
13s≡0 (mod 4)→s≡0
4t≡9 (mod 13)→4t≡-4→t≡12
x≡4×12≡48 (mod 52)
(2022/10/27・10/28・11/4)
