位数、原始元(原始根)について勉強する

久しぶりの投稿です。暗号に興味を持ったものの、数学的な知識が不足しており解説書の内容が理解するのが難しかったです。

今回は暗号について勉強していた際に出てきた位数、原始元(原始根)について具体例を交えながら勉強していきます。お手数をおかけしますが、独学なので間違っていることがあれば指摘をお願いいたします。

位数とは

位数とは、aとnを1以上の整数、aとnが互いに素であるとした場合、以下の合同関係が成り立つ最小のkのことです。
$a^k \equiv 1\pmod n$ 

位数とはより引用

この説明だけで理解できる人はいいですが、私は理解が難しかったため表で整理してみました。例えば$\mod 7$でaとkを変えた場合にどのようになるかを表で見てみます。

緑で塗ったセルがaの値、オレンジに塗ったセルがkの値、黄色く塗ったセルが$a^k$を7で割った余りが1になる値です。

表1　aとkの値を変えた場合の7で割った余りについて

ここで位数の定義よりaを7で割った余りが1となる数の中で最小のkとなる値が位数となるので、aの値それぞれに対して最小のkとなるセルの色を変えてみます。(見方としては左から右へ見ていく感じです。)

表2　各aに対して7で割った余りが1となる最小のkについて

原始元(原始根)とは

前置きが長くなりましたが、原始根の定義は下記のとおりです。

(3 以上の)素数$p$と1以上$p$未満の整数$r$が以下の性質を満たすとき、$r$を法$p$に対する原始根と呼ぶ。
 「$r, r^2, \cdots r^{p-2}$のいずれもが$p$で割って余り1でない 」
 (また, $r = 1$ は$p=2$に対する原始根であるとする。)

原始根の定義と具体例（高校生向け)より

先ほどと同様に$\mod 7$の場合の表で見ていきます。定義に従って$a \cdots a^{p-2}$のいずれもが7で割って余りが1ではないaの値を表から求めてみます。

表3を見てもらうと分かる通り、a=3とa=5の時に定義を満たすことが分かるため、3,5は原子根であることが分かります。

表3 原始根を求めてみる

(補足)サイトによって原始元の定義が異なる

そこで $a$ が $p-1$ 乗してはじめて1と合同になるとき， $a$ を $p$ を法としての原始根という． 略して $p$ の原始根ともいう．

$r$が$p$に対する原始根の時、$r,r^2, \cdots, r^{p-1}$を$p$で割った余りは全て異なり、その余りは1から$p-1$を1巡する。
※こちらを原始根の定義とする流儀もあるようです。

原始根の定義と具体例（高校生向け)より

下記のような定義をしている例もあるみたいです。

フェルマーの小定理によると、素数pとそれに互いに素な数 a について、$a^{p-1} \equiv 1{\pmod {p}}$だった。
 また、位数の法則によれば、位数は$p-1$の約数だった。そこで、位数が$p-1$になる数aを「p(を法として)の原始根」という。 

初等整数論/原始根と指数より

(補足)表ではなく、時計形式で考える

色々なサイトを見ていたところ、下記スライドで時計の世界という概念が紹介されており、分かりやすかったため紹介します。

「時計の世界の整数論」第２回プログラマのための数学勉強会

一般的な整数の世界では数字を直線状に並べて考えますが、余りを扱う世界では時計のように考えるとのことです。(イメージとしては数字を巻き付けるイメージです。)

図1 数直線の世界から時計の世界へ

また、この時計の世界では同じ時間に位置する数は合同としてみなすことが出来るため

下記のようにシンプルに表現することが出来ます。

図2 時計の世界では合同

少し話がそれてしまいましたが、この時計を使って表1に記載したa=2とa=5を書いていきます。先ほど説明した通り、a=3は原始元なので、すべての時間がありますが、原始元ではない2については一部欠損している時間があることが分かります。このように表記することで視覚的にも理解することが出来ます。

図 a=2の時とa=3の時で時計で表現した場合

※こちらの表現は下記本の内容を参考にさせていただいてます。

暗号技術のすべて Kindle版

posted with カエレバ

Amazon.co.jpで詳細を見る

原始元の求め方

原始元の求め方が載っていたので紹介します。

ある数$g$が原始元かどうかを確かめる方法

$p-1$が$p-1=q_{0}^{e_{0}} q_{1}^{e_{1}} \cdots q_{t}^{e_{t}}$と素因数分解されたとする。このとき、$g$が$\pmod p$の原始元である必要十分条件は$0\le i\le t$なる全ての$i$に対し、$g^\frac{p-1}{q_i}\not\equiv1\pmod p$となる

$1\lt g\lt p-1$ 

$g$は↑この範囲で当てずっぽうでガンバる

一つの原始元が見つかったら他の原始元は以下のようにしても求められる

$\gcd(i,p-1)=1$になる$i$

原始元より引用

簡単にこちらの内容について自分の理解を書いていきます。

まずは下記の部分についてです。

$g^\frac{p-1}{q_i}\not\equiv1\pmod p$

左辺のgのべき乗の$\frac{p-1}{q_i}$の部分ですが、フェルマーの小定理から導き出される下記定理を使用していると思います。

$p$が素数で,整数$n$が$p$で割り切れないならば, $\mod p$での位数は$(p-1)$の約数である

フェルマーの小定理ってどんなもの？より

愚直に求めるとなると全部に対して原始元かどうかの判定をしなければいけないのですが、この定理を使用することで探索範囲を絞ることが出来るというものです。

まとめ