somemo programming etc.

プログラマ、雑記、プログラミング関係はLinkから、数式はこっちでまとめていることが多い

【数学】2つの整数の積の剰余とそれぞれの剰余の積の剰余が等しい

数式

(a * b) mod m = ((a mod m) * (b mod m)) mod m 

についての記事です。

アルゴリズムを学ぼうという書籍の問題「aのk乗をmで割った余りを求める」ときに使われていました。

右辺を左辺の形に展開していきます。

余りを数式で定義する

aをmで割った余りをxとすると、aはmの倍数と剰余xの和なので、a = m * n1+ x より

x = a - m * n1

同様にbをmで割った余りをyとすると、

y = b - m * n2

右辺の展開

右辺は (a - m * n1) * (b - m * n2) をmで割った余りとなる。x * yを展開すると、

ab -am(n2) -bm(n1) + m^2(n1)(n2)
= m(-a(n2) -b(n1) +m(n1)(n2)) + ab となる

(a * b) mod m = z とすると
(a * b) = m * n3 + z より

x * y 
= m(-a(n2) -b(n1) +m(n1)(n2)) + m * n3 + z  
= m(-a(n2) -b(n1) +m(n1)(n2) + n3) + z  

まとめ

これをmでわるとmの倍数でないzがあまりとなる。zはa * b をmで割った余りなので、左辺と右辺は等しい。

おまけ

int powmod(int a, int k, int m) {
    logn t = 1;
    for (int i = 0; i < k; i++) {
        t = (t * a) % m;
    }
    return (int) t;
}

実際に余りを求めているコードでは、使われていない。そのため、下記のように疑問を持っている人がいたので計算してみた。

(a * b) mod m について a = bのときを考える
(a * a) mod m
= ((a mod m) * (a mod m)) mod m
= (a * a + mのかかる項) mod m
= (a * a) mod m
となる
しかし、コード上はa mod mでなく, aとなっている
つまり、
(a * a) mod m
= ((a mod m) * a) mod m
 である

これは簡単に成り立つことが分かる
a mod m = a - m *n1 としたので、これにaをかけると
a * a - m * n1 * a = a * a +mのかかる項 となる
a * a * a だとしても、a^3 + mのかかる項となる
a^k のうちa最低1つだけをa mod m = a - m * n1 にすることで成り立ち、2つ以上でも同じになる感じがする
t と a との関係で見ると、t はそもそも a^n のpowmod なので、t * a の aに対して mod m を求めなくても問題ない
-- Haskell で
powmod :: Int -> Int -> Int -> Int
powmod _ 0 _ = 1
powmod a k m = (a `mod` m) * (powmod a (k-1) m) `mod` m

powmod' :: Int -> Int -> Int -> Int
powmod' a k m = let f x y = x * y `mod` m
                in foldr f 1 (replicate k a)

powmod'' :: Int -> Int -> Int -> Int
powmod'' _ 0 _ = 1
powmod'' a k m
    | even k    = (x * x) `mod` m
    | otherwise = (x * x * a) `mod` m
    where x = powmod'' a (k `div` 2) m

再帰のイメージ

a^k mod m
= (a \* a^(k-1)) mod m
= (a mod m \* (a^(k-1) mod m                                )) mod m
= (a mod m \* ((a mod m \* a^(k-2) mod m) mod m)) mod m

計算量を減らすことについて

ak=(ak/2)2=((ak/4)2)2=...より、k回のループを指数の特徴より2分探索のようにわけることで、計算回数を減らせる。本には、減らせることは書いてあるが、指数の特徴よりそうなっていることを示していないので悩んでいる人もいそう。(そこらへんわかっている前提なくらい、ガチな本ではある

参考