群と有限体
ある自然数nで割った余りの世界(モジュロ演算という)のお話です。
そして、この世界では、「計算の結果、nになると0に戻る性質」があり、一本の[ 0,n ] という線分の両端を張り合わせて円周の上を動いていると見立てられます。この性質はフェルマーの小定理と言います。 https://scrapbox.io/files/6176871d2762c200238e56b6.png
群
群とは、集合に演算がつけられたもののうち、群Gのどの要素 a,b ∈ G 、演算・に対しても次の性質を満たすものです
code: 性質
1) a・b ∈ G
2) a・e = e・a = aとなる単位元eがある
3) a・a’ = a'・a = eとなる逆元a’がある
このうち、加法と乗法を満たす群を加法群、乗法群と言います。
code:加法群
1a=a
2a=a+a
3a=a+a+a
...
このとき、単位元=0,xの逆元=-x
code:乗法群
a^1=a
a^2=a・a
a^3=a・a・a
このとき、単位元=1,xの逆元=$ x^{-1}
また、Gが有限集合のとき、群(G,*)は有限群といいます
そして、一つの要素g からg・gを作り、さらにg・g・gという風に作っていって全部の要素を作り尽くせるような群を巡回群といいます。この要素gを生成元といい、全ての要素は$ g²,g³,...g^nのような形に表現できます。
例えば、6つの元を持つ集合が群となる場合、それが巡回群であるためには、ある要素gが存在し、すべての要素がgの累乗で表現できる必要があります。6つの元を持つ集合$ G = g^0, g^1, g^2, g^3, g^4, g^5 が群となるならば、$ g^6 = g^0 であり、G は巡回群を成します。
巡回群は単に一種類の群であるため、その群がどのように表現されているかによって名前が異なります。例えば、乗法表現で表される巡回群は乗法巡回群と呼ばれます。
https://scrapbox.io/files/61768cb9bb0953001fcf3d71.png
↑1の六乗根
実はこの G は集合 { 0, 1, 2, 3, 4, 5 } に 6 を法とする加法を入れたものに本質的に同じ
例えば、1 + 2 ≡ 3 (mod 6) に g1 · g2 = g3 が対応し 2 + 5 ≡ 1 (mod 6) に g2 · g5 = g1 が対応するといった具合になっている
群の定義より、必ず全ての要素には逆元があるので、gの逆元を表す要素$ g^{-1}が必ず群内に存在し、gをかけたら1に戻り、もう一度かけたらgに戻ることができます。
群内の任意の要素gに対して、gを何度かかけても必ずgの累乗が群内に存在することになります。
これが、冒頭の図の正体です。
code:フェルマーの小定理
1) qは素数なので、{a,2a,3a,…,(q-1)a}の集合の要素全てと互いに素である。
2) そしてこの集合の各要素をqで割って生まれた集合は{1,2…..q-1}と一致する。
全部の要素を掛け合わせると、
a*2a*3a*..*(q-1)a ≡ 1*2*3…*(q-1)
よって、a^(q-1) ≡ 1
$ g^n = gの時、 nを巡回群の位数と言います。つまり巡回群の要素数です。
有限体
加算、減算、乗算、除算が自由に行える世界を体と呼び、要素数が有限な体を有限体といいます。
厳密には以下のような定義
code:体
体Fとその演算+と演算*に対して、
1) 演算+に関してFは群であり、かつ任意の要素a,bに関してa+b = b+aが成り立つ。(これを可換群という)
2) 演算＊に関して、Fは+の単位元0を除いたら可換群をなす。0には逆元がない
3) 二つの演算*と・の関係として、 分配法則が成り立つ
(a+b)*c = a*c+b*c
c*(a+b) = c*a+c*b
要素数Qとすると、有限体はGF(Q)と書けます。任意の素数pに対し、GF(p)が存在します。
余りの世界において、基本的に素数q(割る数)とaが互いに素なら必ずa*b ≡ 1となるbが（q未満に）存在します。
つまり、qが少なくとも素数である時はこの世界の元は逆元を持ち、体になります。
さて、この性質が本当かどうか、余りの世界で試してみましょう。
https://scrapbox.io/files/61a4a7448652d8001d2d781a.png
さて、乗法逆元を求めるというのはつまり、割り算をするということになります。
$ a*b = 3なら
$ b = 3÷a = 3 * 1/aです。
つまり$ b = a^{-1} * 3なので、aの逆元と3を掛け算してやれば、bを割り算として算出できます。
ではこの有限体 において逆元はどうやって求めるのでしょう？この計算を逆モジュラー計算と呼びます。
逆モジュラー計算はフェルマーの小定理を用いた逆算です。
フェルマーの小定理より、$ a^{(q-2)} * a ≡ 1 なので、$ a^{(q-2)}がaの乗法逆元ですね。
これにより、有限体の逆元はすぐに求まります。つまり、有限体上で割り算をする時は、q-2乗する計算が入ることになります