• 追加された行はこの色です。
  • 削除された行はこの色です。
  • 元の位数 へ行く。

*目次 [#f4400a87]

#contents


*はじめに [#y96b7e9f]

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


*元の位数 [#ca2299ef]

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

**法が素数のとき [#qf96eaab]

#divid(s,thorem)
[定義]~
p:素数~
&mimetex("\forall a \in Z_p^*");~
とする。~
このとき、&mimetex("a^x \equiv 1 \, ( mod \, p)");となる'''最小の'''正整数xをaの位数といい、&mimetex("x=ord_p (a)");で表す。
#divid(e,thorem)

#divid(s,notice)
[例]p=5の表で考えてみる。

|a|1|2|3|4|
|aSUP{1};|1|2|3|4|
|aSUP{2};|1|4|4|1|
|aSUP{3};|1|3|2|4|
|aSUP{4};|1|1|1|1|
|aSUP{5};|1|2|3|4|

-&mimetex("ord_5 (2)=4");
--mod 5の世界において、2は4乗して初めて1になるから。
-&mimetex("ord_5 (3)=4");
--mod 5の世界において、3は4乗して初めて1になるから。
-&mimetex("ord_5 (4)=2");
--mod 5の世界において、4は2乗して初めて1になるから。

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

-&mimetex("ord_5 (2)=4");
-&mimetex("ord_5 (3)=4");
-&mimetex("ord_5 (4)=2");

 原始元はp-1となる値aということなので、4(=p-1=5-1)となる値は2と3である(括弧の中の値が原始元と覚えておけばよい)。つまり、&mimetex("Z_5^*");の原始元は2,3ということになる。 ◇
#divid(e,notice)

#divid(s,thorem)
[系]p:素数とする。~
&mimetex("1 \le ord_p (a) \le p-1");
#divid(e,thorem)

#divid(s,proof)
[証明]位数の定義より、&mimetex("ord_p (a)");は1以上の整数である。

 一方、[[フェルマーの小定理]]より、aの値に限らずp-1乗すれば必ず1になるので、&mimetex("ord_p (a)\le p-1");が成り立つ。 □
#divid(e,proof)

**法が自然数のとき [#q745e379]

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


*元の位相に関する定理 [#r93764bf]

#divid(s,thorem)
[定理]pを素数とする。~
「&mimetex("a^m \equiv 1 \, (mod \, p)");」⇒「&mimetex("ord_p (a) | m");」
#divid(e,thorem)

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

#divid(s,notice)
[例]2SUP{4};≡1 (mod 5)は[[フェルマーの小定理]]から成り立つ。

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

 よって、&mimetex("ord_5 (2) =4");と位数を求められる。
#divid(e,notice)

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

#divid(s,thorem)
[系]&mimetex("ord_n(a)");はφ(n)の約数である。
#divid(e,thorem)

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

#divid(s,thorem)
[定理]mSUB{1};,mSUB{2};を2より大きな互いに素なし自然数とし、n=mSUB{1};mSUB{2};とする。~
このとき、nと互いに素な整数aについて、次が成り立つ。~
&mimetex("ord_n(a) \le \frac{\phi(n)}{2}");
#divid(e,thorem)


*参考文献 [#xe2f608e]

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