Security Akademeia

目次 †

目次
はじめに
元の位数
- 法が素数のとき
- 法が自然数のとき
元の位相に関する定理
参考文献

↑

はじめに †

　数学の世界において位数と一言にいっても様々な意味を持つ。ここではあくまで集合の要素（元）の位数について言及する。集合の位数とは異なるので注意（集合の位数と言った場合は、集合の要素数を意味する）。

↑

元の位数 †

　まずは法が単純に素数の場合を考える。

↑

法が素数のとき †

[定義]
p：素数
$\forall~a~\in~Z_p^*$
とする。
このとき、 $a^x~\equiv~1~\,~(~mod~\,~p)$ となる最小の正整数xをaの位数といい、 $x=ord_p~(a)$ で表す。

[例]p=5の表で考えてみる。

a	1	2	3	4
a1	1	2	3	4
a2	1	4	4	1
a3	1	3	2	4
a4	1	1	1	1
a5	1	2	3	4

- mod 5の世界において、2は4乗して初めて1になるから。
- mod 5の世界において、3は4乗して初めて1になるから。
- mod 5の世界において、4は2乗して初めて1になるから。

　位数とセットで知っておくべき概念として原始元という概念がある。これは位数がp-1となるときの値aのことである。これも上記のp=5の例で考えてみる。

$ord_5~(2)=4$
$ord_5~(3)=4$
$ord_5~(4)=2$

　原始元はp-1となる値aということなので、4（＝p-1=5-1)となる値は2と3である（括弧の中の値が原始元と覚えておけばよい）。つまり、 $Z_5^*$ の原始元は2,3ということになる。　◇

[系]p：素数とする。
$1~\le~ord_p~(a)~\le~p-1$

[証明]位数の定義より、 $ord_p~(a)$ は1以上の整数である。

　一方、フェルマーの小定理より、aの値に限らずp-1乗すれば必ず1になるので、 $ord_p~(a)\le~p-1$ が成り立つ。　□

↑

法が自然数のとき †

[定義]nを自然数、aをnと互いに素な整数とする。
$a^s~\equiv~1~\pmod{m}$ を満たす最小の自然数sを法nに関するaの位数といい、 $ord_n(a)$ と表す。

↑

元の位相に関する定理 †

[定理]pを素数とする。
「 $a^m~\equiv~1~\,~(mod~\,~p)$ 」⇒「 $ord_p~(a)~|~m$ 」

この定理はpが大きいほど有効に働く。位数を求めるときに便利である。

[例]24≡1 (mod 5)はフェルマーの小定理から成り立つ。

　一方、4を割り切る整数は4,2,1しかない。1のときは明らかなので、ここで2を考えてみる。22≡(4 mod 5)≠1である。

　よって、 $ord_5~(2)~=4$ と位数を求められる。

[定理]nが自然数、aをnと互いに素な整数とする。このとき、次は同値である。
[1] $ord_n(a)~=~s$
[2]以下の2条件が成り立つ。
(a)sは自然数で、 $a^s~\equiv~1~\pmod{n}$
(b) $a^m~\equiv~1~\pmod{n}$ ならば、mはsの倍数である。

[系] $ord_n(a)$ はφ(n)の約数である。

[定理]nが自然数、aをnと互いに素な整数とする。このとき、次は同値である。
[1] $ord_n(a)~=~s$
[2]以下の2条件が成り立つ。
(a)sは自然数で、 $a^s~\equiv~1~\pmod{n}$
(b) $a^m~\equiv~1~\pmod{n}$ ならば、mはsの倍数である

[定理]m1,m2を2より大きな互いに素なし自然数とし、n=m1m2とする。
このとき、nと互いに素な整数aについて、次が成り立つ。
$ord_n(a)~\le~\frac{\phi(n)}{2}$

↑

参考文献 †

ゼミノート
『現代暗号の基礎数理』
『応用代数学入門』

Top / 元の位数元の位数