概要

ほとんどの公開鍵暗号アルゴリズムは剰余計算を基礎としている。剰余計算とは、除法において、余りを求める計算の事である。例えば８９を９で割ると商が９で余りが８となる。この余り８を求める計算が剰余計算である。剰余計算の演算記号にはｍｏｄを用いる。そして、その結果は「ｎを法とする」または「ｍｏｄ ｎ」と呼ばれる。先程の例を用いると、８９を９で割るときの余りを求める計算を８９ ｍｏｄ ９と表現する。つまり８９ ｍｏｄ ９＝８となる。

記号の意味

８９ ｍｏｄ ９　→　「８９を９で割った余り（の計算）」
８９ ｍｏｄ ９＝８　→　「８９を９で割った余りが８」

基本性質

（ａ，ｂ，ｎ，ｘは1以上の任意の整数）

（１）　ａ ｍｏｄ ｎ＜ｎ

（２）　０以上ｎ未満ならばｍｏｄ ｎを取らなくても同じ。

（例）

　　　　（２×３−４×５）ｍｏｄ ２０＝２×３−４×５

　　　　１^１００ ｍｏｄ ｎ＝１^−１００ ｍｏｄ ｎ＝１

（３）　ａ ｍｏｄ ｎ＝ｂ　→　適当なｘでａ＝ｘｎ＋ｂとなる。

　　　　適当なｘ、ｂ（ｂ＜ｎ）でａ＝ｘｎ＋ｂ　→　ａ ｍｏｄ ｎ＝ｂ

　　　　(例)１２３４ ｍｏｄ １００＝３４　→　１２３４＝１２×１００＋３４

（４）　ａ ｍｏｄ ｎ＝ｂ　→　ａ−ｂはｘｎで割り切れる。

　　　　逆にａ−ｂがｎで割り切れ、ｂ＜ｎ　→　ａ ｍｏｄ ｎ＝ｂ

（５）　ｍｏｄ ｎは計算中に取っても最後に１回取っても計算結果は同じ。

　　　　(例)｛（１ ｍｏｄ ｎ）×（２ ｍｏｄ ｎ）×（３ ｍｏｄ ｎ）｝ｍｏｄ ｎ

　　　　＝（１×２×３） ｍｏｄ ｎ

Yahoo! Japan

Yahoo! Deutschland

This page hosted by Get your own Free Homepage