晴耕雨読

work in the field in fine weather and stay at home reading when it is wet

ラグランジュの定理と群の位数

群論において、ラグランジュの定理とは次のような定理のことです。 なお、群 $G$ の部分群 $H$ によって類別したときの類の数を指数 (index) といい、$|G:H|$ と書きます。

  • ラグランジュの定理

    $G$ を有限群とし、$H$ を $G$ の部分群とする。 このとき部分群 $H$ の位数 $|H|$ は群 $G$ の位数 $|G|$ の約数になる。

このとき、有限群の任意の元 $g \in G$ により生成される巡回群 は $G$ の部分群となり、巡回群の位数は $|\langle g\rangle| = |G|$ となります。 さらに、ラグランジュの定理には次のような系 (同時に成立する関係性) があります。

  • ラグランジュの定理

    有限群 $G$ の任意の元の位数は群 $G$ の位数の約数になる。

ここで有限群 $\mathbb{Z}_q$ について、$q$ が素数の場合、部分群の位数は $q$ の約数である $1$ もしくは $q$ しかありえません。 単位元以外の任意の元 $a$ を選んだとき、巡回群は少なくとも単位元 $e$ と元 $a$ の2つ以上の元を持ちます。よって、元 $a$ の位数は $q$ になります。 よって、有限群 $\mathbb{Z}_q$ について、単位元以外の任意の元の位数は $q$ になります。


有限群の位数

例えば $\mathbb{Z}_6$ は位数が非素数なので、単位元以外の任意の元が作る巡回群の位数は $1,2,3,6$ のどれかになります。

一方で、$\mathbb{Z}_7$ は位数が素数なので、単位元以外の任意の元が作る巡回群の位数は必ず $7$ になります。


楕円曲線上の点集合が成す群の位数

例えば、有限体 $\mathbb{F}_{11}$ 上の楕円曲線 $y^2 \equiv x^3 + x - 3 \pmod{11}$ の位数は $6$ で非素数です (楕円曲線の位数の求め方は ルジャンドル記号による楕円曲線の位数計算 を参照してください)。 Sage で楕円曲線上にある全ての点について、その元の位数をプログラムで出力させると $6$ の約数である $1,2,3,6$ のどれかになります。

$ sage
sage: EC = EllipticCurve(GF(11), [1, -3])
sage: EC.order()
6
sage: for a in EC: print("Point: %s, Order: %s" % (a, a.order()))
Point: (0 : 1 : 0), Order: 1
Point: (3 : 4 : 1), Order: 6
Point: (3 : 7 : 1), Order: 6
Point: (8 : 0 : 1), Order: 2
Point: (9 : 3 : 1), Order: 3
Point: (9 : 8 : 1), Order: 3

一方で、有限体 $\mathbb{F}_{11}$ 上の楕円曲線 $y^2 \equiv x^3 - x + 8 \pmod{11}$ の位数は $7$ で素数です。 なので、Sage で楕円曲線上にある全ての点について、その元の位数をプログラムで出力させると、単位元 (無限遠点) 以外の元では位数が必ず $7$ になります。

$ sage
sage: EC = EllipticCurve(GF(11), [-1, 8])
sage: EC.order()
7
sage: for a in EC: print("Point: %s, Order: %s" % (a, a.order()))
Point: (0 : 1 : 0), Order: 1
Point: (2 : 5 : 1), Order: 7
Point: (2 : 6 : 1), Order: 7
Point: (6 : 3 : 1), Order: 7
Point: (6 : 8 : 1), Order: 7
Point: (7 : 5 : 1), Order: 7
Point: (7 : 6 : 1), Order: 7

以上の理由から、暗号技術で使われている楕円曲線のドメインパラメータは、位数が素数になるように設定されています。