久しぶりの投稿です。暗号に興味を持ったものの、数学的な知識が不足しており解説書の内容が理解するのが難しかったです。
今回は暗号について勉強していた際に出てきた位数、原始元(原始根)について具体例を交えながら勉強していきます。お手数をおかけしますが、独学なので間違っていることがあれば指摘をお願いいたします。
位数とは
位数とは、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(を法として)の原始根」という。
(補足)表ではなく、時計形式で考える
色々なサイトを見ていたところ、下記スライドで時計の世界という概念が紹介されており、分かりやすかったため紹介します。一般的な整数の世界では数字を直線状に並べて考えますが、余りを扱う世界では時計のように考えるとのことです。(イメージとしては数字を巻き付けるイメージです。)
また、この時計の世界では同じ時間に位置する数は合同としてみなすことが出来るため
下記のようにシンプルに表現することが出来ます。
原始元の求め方
ある数$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$
$p$が素数で,整数$n$が$p$で割り切れないならば, $\mod p$での位数は$(p-1)$の約数である
.png)
0 件のコメント:
コメントを投稿