この数学の問題

値が大きすぎて解けません。解く方法を教えてください

(1) 20^3 mod 55

(2) 25^27 mod 55

No.2 ベストアンサー 回答者： alice_44 回答日時： 2013/10/29 13:28

mod 5 と mod 11 で考えると、

数が小さくなって嬉しいかも。
--------------------------------------------------

20^3 (mod 55) の計算

20 ≡ 0 (mod 5) より
20^3 ≡ 0^3 = 0 (mod 5).

20 ≡ -2 (mod 11) より、
20^3 ≡ (-2)^3 = -8 ≡ 3 (mod 11).

5 と 11 が互いに素であることより、
x ≡ 0 (mod 5) かつ
x ≡ 3 (mod 11) となる
x は mod 55 で唯一に定まる。(中国剰余定理)

x = 0 + 5p = 3 + 11q となる　　←[1]
整数 p, q を一組探せばよい。
5p + 11(-q) = 3 を解くことになる。

5・(-2) + 11・1 = 1 を山勘で発見し、
右辺を上記と合わせるため、定数倍して
5・(-6) + 11・3 = 3.
p = -6, q = -3 であれば十分だと判る。
(他の p, q でもよいが、気にしない。)

これを[1]へ代入して、x = -30.
整えて書けば、x ≡ 25 (mod 55) である。
--------------------------------------------------

x ≡ 25^27 (mod 55) も、同様にやる。

x ≡ 0^27 = 0 (mod 5)
と
x ≡ 3^27 = (3^3)^9 = 27^9
　≡ 5^9 = (5^3)^3 = 125^3
　≡ 4^3 = 64 ≡ 9 (mod 11)
より、
x = 0 + 5p = 9 + 11p　　←[2]
と置いて
5p + 11(-1) = 9 を解く。

5・(-2) + 11・1 = 1 を定数倍して
5・(-18) + 11・9 = 9.
p = -18, q = -9 であれば十分だと判る。

[2]へ代入して、x = -90 ≡ 20 (mod 55).

No.4 回答者： Tacosan 回答日時： 2013/10/30 00:45

まあこんなものは

(ab mod n) = (a mod n)(b mod n) mod n
を知っているかどうかだけの話ではあるんだが....

(2) は 25^3 mod 55 あたりを計算できると楽っぽいね.

No.3 回答者： ramayana 回答日時： 2013/10/29 21:15

（１）について

20^3 = 8000 なので、あたりまえに計算しても大した手間にならないでしょう。

（２）について

27 を 2 進法で表す手法で、計算の手間を省くことができます。次のようにします。ANo.1さんやANo.2さんも似たような発想が使われているようですが。

25^2 mod 55 = 20 mod 55
25^4 mod 55 = (25^2)^2 mod 55 = 20^2 mod 55 = 15 mod 55
25^8 mod 55 = (25^4)^2 mod 55 = 15^2 mod 55 = 5 mod 55
25^16 mod 55 = (25^8)^2 mod 55 = 5^2 mod 55 = 25 mod 55
25^27 mod 55 = 25^16*25^8*25^2*25 mod 55 = (25*5)*(20*25) mod 55
　　　= (125 mod 55)*(500 mod 55) mod 55
　　　= 15*5 mod 55 = 20 mod 55

ちなみに、x^d mod N の計算を、かけ算を d-1 回繰り返す方法で実行すると、計算量はほぼ d に比例します。一方、上の方法だと、計算量はほぼ log(d) に比例します。例えば実用的な RSA 暗号を考えると、d が巨大な数値になるので、計算量が d に比例するか log(d) に比例するかは、決定的な差になると思われます。

No.1 回答者： info22_ 回答日時： 2013/10/29 08:38

(1) 20^3 mod 55

=(400*20) mod 55
=((55*7+15)*20) mod 55
=(15*20) mod 55
=300 mod 55
=(55*5+25) mod 55
=25 mod 55
=25

(2) 25^27 mod 55
=(25*(25^2)^13) mod 55
=(25*625^13) mod 55
=(25*(550+75)^13) mod 55
=(25*75^13) mod 55
=(25*(55+20)^13) mod 55
=(25*20^13) mod 55
=(25*20*(20^12)) mod 55
=(500*400^6) mod 55
=((55*9+5)*(55*7+15)^6) mod 55
=(5*15^6) mod 55
=(5*225^3) mod 55
=(5*(55*4+5)^3) mod 55
=5^4 mod 55=625 mod 55
=75 mod 55
=20