Pebble Coding

ソフトウェアエンジニアによるIT技術、数学の備忘録

準同型写像に関するカーネルの元の数についての定理

群環体

準同型写像に関する元の数についての定理を直観的に理解したいと思います。

G,Yを有限群とする。
群Gから群Yへの準同型写像(Homomorphism)を \phi とする。
すなわち、 g_1, g_2 をGの任意の元として、
\phi(g_1 + g_2) = \phi(g_1) + \phi(g_2) が成りたちます。
ここで左辺のプラス +は群Gでの演算,右辺のプラス +は群Yでの演算です。

\phi の核は Ker(\phi) = \{ g \in G | \phi(g) = 0 \}
で定義されます。
核とは、写像の行く先の元が全て群Yの単位元0になる群Gの元の集まりのことです。
\phi の全ての行く先の元を全て集めたものは、一般に、Yの部分群となることが知られています。
(ここでは証明しません。)

\phi の像を \phi(G)と書きます。
このとき、以下が成りたちます。
\#G = (\#Ker(\phi)) (\#\phi(G))
つまり、群Gの元の数は、核 Ker(\phi)の元の数と像 \phi(G)の元の数の積に等しい。

例として、群Gの元の数は20,核 Ker(\phi)の元の数は4だとしましょう。
g_1, g_2, g_3, g_4が核でGの要素だとします。
この4つの元は \phiによって、Yの単位元0に移されます。すなわち、
\phi ( g_1 ) = 0
\phi ( g_2 ) = 0
\phi ( g_3 ) = 0
\phi ( g_4 ) = 0
がなりたっています。
そして、準同型性からGの核でない任意の元 g_iに対して以下が成り立ちます。
\phi ( g_i + g_1 ) = \phi ( g_i ) + \phi ( g_1 )
\phi ( g_i + g_2 ) = \phi ( g_i ) + \phi ( g_2 )
\phi ( g_i + g_3 ) = \phi ( g_i ) + \phi ( g_3 )
\phi ( g_i + g_4 ) = \phi ( g_i ) + \phi ( g_4 )
この右辺の2番目の項は群Yの単位元に等しいです。
Yは群なので、Yの任意の元にYの単位元を加えたものは同じ元のままですね。
するとこの４つの式の右辺は全て同じ \phi(g_i)ということになります。
ということは左辺も全て同じですね。
\phi ( g_i + g_1 ) = \phi ( g_j )
\phi ( g_i + g_2 ) = \phi ( g_k )
\phi ( g_i + g_3 ) = \phi ( g_l )
\phi ( g_i + g_4 ) = \phi ( g_m )
の４つの像は同じYの元であるということになります。
g_j, g_k, g_l, g_mが同じ元なのか異なる元なのかは分かりませんが、
像 \phi ( G )の元の数は群Gの約数になりそうな雰囲気です。

f:id:pebble8888:20180612222907p:plain

これはイメージ図ですが、 g_1, g_2, g_3, g_4が核の元の数4で、
Gの4個の組みの像が同じYの元になってしまうため、像の元の数が5になっている様子を表しています。
先にイメージだけでも掴んでおくと、この定理を利用する際にとても役に立ちます。
また、この定理の証明は別の文献を参照下さい。
私はこの証明は見つけられていませんが、群論の教科書に載っているのではないかと思います。

この定理では群Yの元の個数については何も言っていません。
仮に、群Yが群Gと同じだった場合、つまり、自己準同型写像(Endomorphism)だった場合は、
さらに色々定理が出てきそうだという想像がつきますが、この記事ではここまでとしておきます。

群論における写像 - Pebble Coding

群の定義といろんな具体例 | 高校数学の美しい物語

準同型写像 [物理のかぎしっぽ]

なお、この定理はこの本のAppendixに載ってました。

Elliptic Curves: Number Theory and Cryptography, Second Edition (Discrete Mathematics and Its Applications)

Elliptic Curves: Number Theory and Cryptography, Second Edition (Discrete Mathematics and Its Applications)

  • 作者:Lawrence C. Washington
  • 出版社/メーカー: Chapman and Hall/CRC
  • 発売日: 2008/04/07
  • メディア: ハードカバー

Ker f は群Gの部分群

fを群Gから群Yへの準同型写像とすると、Gの部分集合
Ker f = \{ g \in G | f(g) = 0_Y\}
はGの部分群になる。 0_YはYの単位元とする。
この証明は難しくありません。
この定理から以下は導かれます。
\#G = (\#Ker(\phi)) (\#\phi(G))

#Kerfを数えてみる

例1)
Gを Z/6Z {0, 1, 2, 3, 4, 5}
Yを Z/3Z {0, 1, 2}
f: G \to Y 3で割った余り
Ker f : {0, 3}
\#Ker f = 2

楕円曲線の有理点の数の求め方 schoof アルゴリズムその１

暗号 Schoofアルゴリズム

F_p 上の楕円曲線 y^{2} = x^{3} + a x^{2} + b の有理点個数の求め方です。

ここではSchoofアルゴリズムの理解を目的とし、少しづつ理解を進めます。

まず使うのはHasseの定理です。

Hasse-Weilの定理(楕円関数限定版) - Pebble Coding

有理点の数を#Eで表すと、 -2 \sqrt {p} \leq a \leq 2 \sqrt {p}
a = p + 1 - \#E
が成り立つのでaを求めれば、#Eが確定します。
aはある範囲内の唯一つの整数なので、 a \mod n = c を満たす非負整数n,c が見つかったと仮定します。
ここで、
a = dn + c, c \lt nなので、 n が 4 \sqrt {p}より大きかった場合は、dは0しかありえず、aはcと求まります。

計算する必要があるのは、 a \mod n, n \lt 4 \sqrt {p}だけとなりましたが、
nが大きいと計算量が多過ぎるので、 中国の剰余定理を用いて、もう少し分解します。
中国剰余定理の証明と例題（二元の場合） | 高校数学の美しい物語

中国の剰余定理は、２元の場合だけを書くと、 l1 と l2 が互いに素なとき
a = b1 \mod l1
a = b2 \mod l2
を満たす a が 0 以上 l1 l2 未満の範囲に唯1つ存在する。
というもので、これは任意の元の数に拡張しても成り立ちます。

l_iをいくつかもってきて全ての積を作ったものをnとします。
l_iは全て、互いに素な素数とします。
n = l_1 l_2 ... l_n
a \mod l_1 = c_1
a \mod l_2 = c_2
...
a \mod l_n = c_n
を計算して、あとはユークリッドの互除法を用いてaを計算します。

Schoof's algorithm - Wikipedia

暗号技術入門 第3版

暗号技術入門 第3版

Amazon

素体を拡大する

群環体

素体 F_pを拡大してみます。
F_3を拡大して、拡大体 F_{{3}^{2}}を作ることにします。
体の拡大には既約多項式を使います。
ここでは、規約多項式 x^{2} + 2 x + 2 = 0を使います。
F_3を作る場合は素数3で割った余りを使うというルールでした。
F_3の元は{0, 1, 2}の3つですが、加法の単位元が0で乗法の単位元が1です。

F_{{3}^{2}}を作る場合のルールは、既約多項式のxを使って、
xを素体に追加して、xを整数1とは独立したものとして計算し、
x^{2}が出現した場合は x^{2} = - 2x - 2 = x + 1 に置き換えるというものです。
また1の係数やxの係数は3で割った余りを使います。

元は{0, 1, 2, x, 2x, 1 + x, 1 + 2x, 2 + x, 2 + 2x}の9個になります。
一般に拡大体 F_{{p}^{n}}の元の数は {{p}^{n}}個です。

これらの元同士の加算には x^{2}の項は出てこないため、3で割った余りを使うだけで、簡単なので省略します。
これらの元同士の乗算は面倒なので表にしてみました。

0 1 2 x 2x 1+x 1+2x 2+x 2+2x
0 0 0 0 0 0 0 0 0 0
1 0 1 2 x 2x 1+x 1+2x 2+x 2+2x
2 0 2 1 2x x 2+2x 2+x 1+2x 1+x
x 0 x 2x x+1 2+2x 1+2x 2 1 2+x
2x 0 2x x 2+2x 1+x 2+x 1 2 1+2x
1+x 0 1+x 2+2x 1+2x 2+x 2 2x x 1
1+2x 0 1+2x 2+x 2 1 2x 2+2x 1+x x
2+x 0 2+x 1+2x 1 2 x 1+x 2+2x 2x
2+2x 0 2+2x 1+x 2+x 1+2x 1 x 2x 2

例としてひとつ計算してみます。
(2x+2) * (2x +2 )= 4 x^{2} + 8x + 4 = x^{2} + 2x + 1 = x + 1 + 2x + 1 = 3x + 2 = 2

ここでは、綺麗に1列に同じ元が出てこないようになっていますね。
既約多項式を使わないと、このようにはならず、列に同じ元が２つ以上出てくるようになってしまいます。

規約多項式は x^{2} + 2 x + 2 = 0以外にも存在します。
例えば、 x^{2} + 1 = 0 や x^{2} + x + 1 = 0も規約多項式です。
これを使って掛け算の表を作った場合、異なる表になりますが、元の役割を入れ替えることで、
一つ目の規約多項式を使った場合と同じ表になることが知られているそうです。(同型と言います。)
規約多項式は計算量が少なくなるように係数が小さい方がよいので、
通常 x^{2} + 2 x + 2 = 0などは使いません。

素数が3の時の拡大体 F_{{3}^{2}} を手に入れることができましたが、
素数が3より大きい時に規約多項式をどのように選べば良いでしょうか。
ひとつの例としては、n = p として、
x^{n} + p x^{n-1} + p x^{n-2} + ... + p x + p = 0を選べば良いです。
これは、アイゼンシュタインの既約判定法を用いて作ったものですが、
係数が小さい方が計算量が少なくてすみますから、通常これは選びません。

アイゼンシュタインの既約判定法 - Wikipedia

最も効率が良い規約多項式を得るには、別の構成方法を用いるようです。

参考:
http://lupus.is.kochi-u.ac.jp/shiota/misc/field/FiniteField.html

体の拡大は、もとの体に規約多項式の解を添加しているとも言えます。

なお、規約多項式 x^{2} + 1 = 0 や x^{2} + x + 1 = 0を使った場合は、
この2つの解をそれぞれ、 \alpha, \betaとすると、 (x - \alpha) (x - \beta) = 0なので、
\alpha \beta = 1が満たされ、 \beta = {\alpha}^{-1}と書けることを覚えておくと、どこかで役にたつかも知れません。

乗法群

拡大した体 F_{3^{2}}の乗法群を考えます。
表を見れば分かりますが、0を除いた{1, 2, x, 2x, 1+x, 1+2x, 2+x, 2+2x}の8個がこの乗法群の元になることが確かめられます。
単位元は1です。
この乗法群の位数は8ですから、
任意の元を8乗すると単位元になるはずです。 a \in F_{{3}^{3}}^{\times}
として、
a^{8} = a^{{3}^{3} -1 } = 1

この群の元の位数は群位数の約数になるので1, 2, 4, 8のどれかです。
位数8の元の一つを試しに計算してみます。
(1+2x)^{2} = 2+2x
(1+2x)^{3} = (1+2x)(2+2x) = x
(1+2x)^{4} = (1+2x)x = 2
(1+2x)^{5} = 2(1+2x)=2+x
(1+2x)^{6} = (1+2x)(2+x) = 1+x
(1+2x)^{7} = (1+x)(1+2x) = 2x
(1+2x)^{8} = 2x(1+2x) = 1

べき部分を一般化します。
a \in F_{3^{n}}^{\times} のとき、
a^{3^{n}-1} = 1
さらに一般化すると、
a \in F_{p^{n}}^{\times}, pは素数, nは整数のとき、
a^{p^{n}-1} = 1
逆に、
a^{p^{n}-1} = 1が成り立つとき、
a \in F_{p^{n}}^{\times}
が成り立つことが知られています。

BabyStep GiantStep法(BSGS法)

暗号

DLP問題を解くアルゴリズムの一つとしてBabyStep GiantStep法があります。

www.pebblewind.com

DLP問題とは、対称群の位数nに対して、生成元をg、群のある元をaとして、
{g}^{x} = aを満たすxを求める問題です。
ここで、解はただ一つのみ必ず存在することは前提とします。
なので、解が存在するかどうかを調べる必要はありません。
問題はどうやって計算量を少なく求めるかです。

xは{0, 1, 2, ..., n-1}のいずれかです。
xをある数の倍数に小さい数を加えたものとして計算できれば、少ない計算量で求めることができるんじゃね？
ってのがこのアルゴリズムのアイデアです。

まずある数の倍数として適当な値とはどのくらいの大きさかを考えます。
x = qm + rと表した時、xは最大でn-1なのですから、
mはnの平方根くらいの大きさなら、qとrを小さい方から闇雲に設定した時、xは0からn-1の全てを
最も効率よく網羅できそうですね。
そこでmはnの平方根を整数に切り上げたものに取ることにします。
そしてxをmで割った商をq, 余りをrとします。

{g}^{qm + r} = a を変形して、
{{g}^{m}}^q = a {g}^{-r}とします。
この右辺の値を全ての余りのケースについて計算しておきます。
つまり、 a {g}^{0}, a {g}^{-1}, a {g}^{-2}, ..., a {g}^{-m+1}を計算しておきます。
これをベビーステップ集合と言います。

次に左辺をqの小さい方から順番に計算していき、ベビーステップ集合内の値と一致するまで繰り返します。
手順として d = {g}^{m}をまず計算し、 {d}^{1}, {d}^{2}, {d}^{3}, ...のように計算していきます。
これをジャイアントステップ集合と言います。
一致するものが見つかった場合は、
{d}^{q} = a {g}^{-r}となり、qとrが確定したということですから、
{g}^{mq} {g}^{r} = aとなるので、x = mq + r と求まります。

大事なのは計算量です。
少なくとも、ベビーステップ集合の計算で、 m = \sqrt n回のかけ算が必ず必要となります。
したがって、このアルゴリズムのオーダーは \sqrt nとなり、 n > {2}^{160} 程度あれば、
ハイパーコンピューターをもってしても解くことは不可能となります。

別の取り方

ベビーステップ集合の取り方は他にもあります。
{g}^{qm + r} = a を変形して、
{g}^{r} = {a} {{g}^{-m}}^q とし左辺をベビーステップ集合としてもよいです。

主要な仮想通貨のネットワークハッシュレート

仮想通貨

いくつかの主要な仮想通貨のネットワークハッシュレートを調べてみました。
値が大きいほど、ある種の攻撃に対して耐性を持ちます。