■ モジュラス(modulus)数学

 モジュラス数学とは,割り算をしたときの余りだけに着目する数学です。 例として 13 を基準として考えてみましょう。13 を基準とすることを13を法とするといいます。57 を 13 で割り算すると

となるので,13 を法としたとき 57 と 5 は同じ数字だと考えます。このことを

と書きます。他の例をあげると

となりますね。

■ 逆元

 かけ算をするときは 3 にをかけると 1 となります。このようにある数字に対してかけ算すると 1 になるような数字のことを逆元といいます(かけ算の場合は逆数という呼び方が一般的です)。13 を法としたとき,5 の逆元を求めてみましょう。

となることより,5 の逆元は 8 となります。ユークリッドの互除法という計算を行うことで逆元は容易に計算が可能です。

■ 繰り返し二乗法

 繰り返し二乗法 のような計算を効率的に計算する計算法です。そのままかけ算すると 9 回のかけ算をしなくてはなりませんが,次のようにするとかけ算の回数を減らすことが出来ます。

 コンピュータ内では何回かけ算をしたかが重要な問題となりますので

全部で 4 回のかけ算で済ますことが出来ました。同様にして,の計算でも 9 回のかけ算で済ますことができますので,繰り返し二乗法を使うことでアッという間に計算できます。

■ 最大公約数

 最大公約数 と書くことにします。または(書くのが面倒くさいので)もっと手抜きをして単に と書くことにします(gcd は greatest common divisor の意味,中学校や高校の教科書では gcm (greatest common measure) と書かれている。)。特に となるとき 互いに素であるといいます。例を挙げると

となりますね。

■ オイラー関数

 オイラー関数 とは である整数 のうち となる整数の個数のことである。

 例として とは である整数(つまり )のうち となる整数(つまり互いに素である整数)の個数のことなので

であることから の 4個ということになり となります。オイラー関数については次の性質が成り立つ。

■ オイラー関数の性質(1)

 が素数ならば, となる。

 例として 13 は素数だから,となる。なぜなら とは である整数(つまり )のうち となる整数の個数のことであるが,13 は素数なので のいずれの数とも互いに素となるのは当たり前です。もし,互いに素でない数が見つかれば約数が見つかったことになり,13 が素数であるという仮定に反します。

 ですから が素数のときはオイラー関数の計算は極めて簡単です。(合成数のときは少し工夫が必要となります)

■ オイラー関数の性質(2)

 ならば,となる。

 例としてなので, と計算することが可能である。(オイラー関数の性質(1)を使った。)

 同様に なので までは計算できますが, は 12 が素数でないので簡単には計算できません。 の計算については参考文献をご覧下さい。

■ フェルマーの定理

  を素数とする。このとき であるどのような に対しても が成り立つ。

 例として 13 は素数であるので, となる全ての に対して となる。具体的には

となる。

 実際は の計算は

という具合に繰り返し二乗法と13を法とした計算を組み合わせて大きな数字を扱わないようにすることで,効率よく計算出来ます。

■ オイラーの定理

 を正の整数とする(素数である必要はない)。このとき であれば が成り立つ。

 例として m = 15 とすると

となることより であれば が成り立つということであると書き直せる。

 そこで のうち,15 と互いに素であるものを求めると

であることより となる。実際に計算してみると

となり,定理が正しいことが確かめられた。

 実際には 15を法として考えればよいので,フェルマーの定理のところで説明したようにこのように大きな数字は扱わずに済む。

■ 指数法則(1)

が成り立つ。

 例として次のように書いた方が分かり易いかな?。

となるので

のような計算をした方が簡単だ!。

■ 指数法則(2)

が成り立つ。

 例として次のように書いた方が分かり易いかな?。

となるので

のような計算をした方が簡単だ!。

前へ 次へ

メニューへ戻る