群演算
モジュロ演算(モジュラ演算)の中でひとつの数字を軸にして掛け算(べき乗)をすると難しくなるよ 元の数字とかけ合わせると1に戻る逆元という数字もあるので割り算もできるかもしれず
べき乗のべきを足し算引き算できるようになると見えてる数字と違うよねという話
RFC 6090 Section 2
2.2. 群演算 Group Operations
この節では、数学的群に関する用語と表記法をいくつか定義します。これらは後で必要になります。背景となる参考文献は多数あります。例えば、D1966 を参照してください。 群(Group)とは、G の元(element)と、G の任意の2つの元を結合(combine)して G の3つ目の元を返す演算(operation)を組み合わせたものです。演算(operation)は * と表記され、その適用は G の任意の2つの元 a と b に対して a * b と表記されます。演算は結合的です。つまり、G の任意の a、b、c に対して、a * (b * c) は (a * b) * c と等しくなります。群演算を元 a に N-1 回繰り返し適用することは、G の任意の元 a と任意の正の整数 N に対して $ a^Nと表記されます。つまり、$ a^2 = a * a、$ a^3 = a * a * a、などとなります。群演算の結合性により、$ a^n の計算は一義的になります。項をどのような形でグループ化しても同じ結果になります。
上記の群演算の定義では、乗法表記が用いられています。場合によっては、加法表記と呼ばれる別の表記法が用いられ、a * b は a + b と、$ a^N は N * a と表記されます。乗法表記では、$ a^N はべき乗と呼ばれ、加法表記では同等の演算はスカラー乗算と呼ばれます。この文書では、一貫性を保つために、一貫して乗法表記を使用しています。付録 E では、これら 2 つの表記法の対応関係について説明しています。
すべての群には、単位元と呼ばれる特別な元があり、これを e と表記します。G の各元 a について、e * a = a * e = a となります。慣例により、$ a^0 は G の任意の a について単位元と等しくなります。
すべての群元 a には、a * b = b * a = e となる一意の逆元(inverse element) b があります。a の逆元は、乗法表記では $ a^{-1} と表記されます。 （加法表記では、a の逆数は -a と表記されます。）
任意の正整数 X に対して、$ a^{-X} は $ (a^{-1})^X と定義されます。
この規則を用いると、べき乗は期待通り、つまり任意の整数 X と Y に対して次のように振舞います。
$ a^{X+Y} = (a^X)*(a^Y)
$ (a^X)^Y = a^{(XY)} = (a^Y)^X。
暗号アプリケーションでは、通常、有限群(finite groups)（有限個の元(elements)を持つ群）を扱います。このような群では、群の元の数は群の位数(order of the group)とも呼ばれます。ある正整数 X に対して $ a^X = e が成り立ち、かつ a の位数がそのような X の中で最小のものであるとき、群の元 a は有限位数(finite order)を持つといいます。そのような X が存在しない場合、a は無限位数を持つ(have infinite order)といいます。有限群のすべての元は有限位数(finite order)を持ち、元の位数は常に群の位数の約数です。
群元 a が位数 R を持つ場合、任意の整数 X および Y に対して、
$ a^X = a^{X \mod R}、
$ a^X = a^Y は、X が Y mod R と合同である場合に限り、
集合 H = { $ a, a^2, a^3, ... , a^R=e } は G の部分群を形成し、これは a によって生成される(generated)巡回部分群(cyclic subgroup)と呼ばれ、a は H の生成元(generator)であると言われる。
一般的には、H を生成する群元は複数存在する。M が R と互いに素であるような $ a^M の形をとる群元は、H を生成する。任意の非負整数 M に対して、$ a^M は $ g^{M \mod R} に等しいことに注意されたい。
位数 R の元 a と、1 から R-1 まで（両端を含む）の整数 i が与えられた場合、元 $ a^i は M1983 の 2.1 節で概説されている「平方乗法」（Knuth, Vol. 2, セクション4.6.3）、またはその他の方法によって計算できる。