大きな数のmod(剰余)

でかい数のmod

#

例として、 $$ 36^{364} $$ の\(\mod 69\)を計算することを考える。

\(36^{364}\)という数は、コンピュータさん曰く、

これを効率的に手計算する方法があるらしい。

その方法は

• 任意の自然数\(a \in \natnums \)は\(a = 2^{p_1} + 2 ^ {p_2} + \dots \quad (p_i < p_{i+1})\) の形で表すことができる(2進法の原理(🔗参考))
• \( a \equiv p^x \mod n\) かつ \(b \equiv p ^y \mod n \) ならば
  \(ab \equiv p^{x+y} \mod n \) である(\(\mod n\)に関する指数法則)

を利用する。

合同式の性質などをほとんど知らなかったので、学習して🔗別記事(合同式の基本的な性質)にメモを残しておいた。

さて、記号を定義し直して \(a, \space b, \space n \in \natnums\)に関して、 $$ a^b \mod n $$ を計算することを考える。

まず、1つ目の法則より、\(b\)は $$ b = 2^{p_1} + 2 ^ {p_2} + \dots \quad (p_i < p_{i+1}) $$ の形で表すことができる。

よって $$ a^b = a^{2^{p_1} + 2 ^ {p_2} + \dots} = a^{2^{p_1}} a^{2^{p_2}} \dots \quad (1) $$ と変形できる。

一番右の辺の\(a^{2^{p_1}} a^{2^{p_2}} \dots\)に着目する。

各\(a^{2^{p_i}}\)に関して、その\(\mod n\)を\(m_i\)とすると、 $$ m_i \equiv a^{2^{p_i}} \mod n $$ と表せるので、合同式の積の性質より、 $$ m_1 m_2 \dots \equiv a^{2^{p_1}} a^{2^{p_2}} \dots \mod n \quad (2) $$ を得る。

\((1)\)より、明らかに\(a^b \equiv a^{2^{p_1}} a^{2^{p_2}} \dots \mod n\)であり、このことと\((2)\)より、\(m_1 m_2 \dots \equiv a^b \mod n\)を得る。

つまり、代わりに各\(a^{2^{p_i}}\)の\(\mod n\)(\(= m_i\))を計算すれば良いことがわかる。

ここで、 $$ a^{2^{k+1}} = a^{2 \cdot 2 ^{k}} = a^{2^{k}} \cdot a^{2^{k}} $$ であることに着目すると、\(a^{2^0}\)さえ計算すれば、 $$ a^{2^{1}} = a^{2^0} \cdot a^{2^0} $$ なので、\(a^{2^0} \mod n\)を2乗するだけで\(a^{2^{1}} \mod n\)を計算することができる。

このことを利用すると、\(a^{2^0} \mod n\)から始めて、2乗して\(\mod n\)をとる操作を繰り返すことによって、\(a^{2^{p_i}} \mod n\)を計算することができる。

実際に計算

#

\(36^{364} \mod 69\)を上述の方法で実際に計算してみる。

Pythonさん曰く

>>> bin(364)
'0b101101100'

とのことなので、 $$ 364 =2^2 + 2^3 + 2^5 + 2^6 + 2^8 $$ である。

一応検算コードを載せておく。

>>> pow(2,2) + pow(2,3) + pow(2,5) + pow(2,6) + pow(2,8)
364

よって、 $$ 36^{364}= 36^{2^2 + 2^3 + 2^5 + 2^6 + 2^8}= 36^{2^2} \cdot 36^{2^3} \cdot 36^{2^5} \cdot 36^{2^6} \cdot 36^{2^8} $$ と表せる。

$$ 36^{364} \equiv 36^{2^2} \cdot 36^{2^3} \cdot 36^{2^5} \cdot 36^{2^6} \cdot 36^{2^8} \mod 69 $$ なので、右辺の\(36^{2^k}\)をそれぞれ計算していく。

\(k=0\) $$ 36^{2^0}= 36^1 = 36 \\ 36^{2^0} \mod 69 = 36 \\ $$

\(k=1\) $$ 36^{2^1} \equiv 36^{2^0} \cdot 36^{2^0} \mod 69 \\ (36 \mod 69)^2 = 36^2 =1296, \space 1296 \mod 69 = 54 \\ 36^{2^1} \mod 69 = 54 $$

以降、同様に\(36^{2^{k}} \mod 69\)を\(36^{2^{k-1}} \mod 69\)の2乗の\(\mod 69\)を取ることによって計算していく。

$$ 36^{2^2} \mod 69 = 18 \\ 36^{2^3} \mod 69 = 48 \\ 36^{2^4} \mod 69 = 27 \\ 36^{2^5} \mod 69 = 39 \\ 36^{2^6} \mod 69 = 3 \\ 36^{2^7} \mod 69 = 9 \\ 36^{2^8} \mod 69 = 12 \\ $$

\(k=2, 3, 5, 6, 8\)のものをかけ合わせて、\(\mod 69\)をとる。(pythonでやったが、本当に手計算でやる場合、数が大きくなってきたら途中で適当に\(\mod 69\)を取って良い。¹)

$$ (18 \cdot 48 \cdot 39 \cdot 3 \cdot 12) \mod 69 = 36 $$

よって $$ 36^{364} \mod 69 = 36 $$ を得る。

念の為、pythonさんに問い合わせたところ、

>>> pow(36,364) % 69
36

と返ってきたので大丈夫そうだ。

応用

#

🔗RSA暗号に関して、でかい数の\(mod\)を計算することがあるらしい。

おわり 感想

#

合同式を初めてみたときに、わけが分からなすぎて苦手意識があったが、少しだけ解消された。

当時は英語が全く読めなかったので、\(mod\)とか出てくるとそれだけで厳つさを感じていた。

\(\equiv\)

\(mod\)(modulo)は日本語では剰余というらしい。
読み方が分からなかったので、今調べたら　じょうよ　と読むとのこと。