利用者:堀江 公人/sandbox
定義
[編集]2次双曲線群Hpとは、有限巡回群の一種 であって、一定の要件下で、2次双曲線関数
・・・(1-1)
上の整数点が剰余環Z/pZ上で作る群を言う。ここで 、一定の要件とは、
・・・(1-2)
であって、（）はヤコビの記号(Jacobi’s symbol)である。この条件は(1-1)式の分母が０とな り、関数が定義不能になることを防止するために設けら れたが、非常に厳しい条件で、群位数を半減させる。2次 双曲線は3次曲線ではないが、分母が作用して、上記要件 (1-2)式の下で、実質的に3次曲線と同じ機能をする。ま た、剰余環Z/pZ上で定義されるので、(1-1)式分母は、そ の逆元を意味することに注意する。
ヤコビの記号は、(a,n)=1であるようなaにつき
aφ(n) ≡ 1 (mod n) ・・ ・(1-3)
が成立するという、オイラー(Euler)の定理がその基 礎になっている。法ｎが素数ｐであるとき、オイラー関 数(Euler totient)φ(n)=φ(p)=p-1であり、これは(1-3) 式で
a (p-1)/2 ≡ 1 (mod p) 若しくは a (p-1)/2 ≡ -1 (mod p) ・・・(1-4)
を意味する。(1-4)式の前者を満たすa値を「平方数」と いい、後者を満たすa値を「非平方数」という。(1-4)式 はa値が平方数か非平方数かを判別する実用的な式になっ ていて、オイラーの判定基準(Euler’s criterion)と呼 ばれる。ヤコビの記号(1-2)式は、素数ｐを法(modulo)と するとき(x 2+ax+b)値が非平方数である ことを意味する。(x2+ax+b)値は元よりｘ値 に依存する2次関数であるので、この条件は一見緩やかな 様であるが、先に言及したように非常に厳しい条件で、 群位数を半減させる。
ここでは素数p=11の元で、a=3が平方数か非平方数 かを判別してみよう。
3(p-1)/2=35=243≡1 (mod 11)であるので、a=3は平方数である。ａ=2の場合は、
2(p-1)/2=25=32≡10 ≡-1 (mod 11)であるので、a=2は非平方数である。
具体例
[編集]ここでは2次双曲線群の具体例として、法p=11の場合 で(=H11)、(1-1)式で、c=1, d=-3, a=0, b= -7 の場合を挙げる。
・・・(2-1)
(2-1)式に付き、総てのｘ値で計算してみると、下表 (第3欄まで) のような計算結果が生じる。このとき、条 件式(1-2)は
・・・(2-2)
であり、下表第3欄で、この要件を満たすｘ値は x=2,3,5,6,8,9 の6個であり、群位数kGは kG=6である。2次双曲線群H11の 元は、当該ｘ値で直接表示しても良いが、P(x)のように 分別しておくものとする。然らば、H11={ P (2), P(3), P(5), P(6), P(8), P(9)}と表示できる。未 だ群演算を明示していないが、単位元 O=P(2)としてkP (x)を計算すると、kgP(x)=Oとなるkg値により、その部分 群位数kgを知ることができる。そのkg値は、法p=11の下 で、群位数k G=6及びその約数である。
<tbody> </tbody>|
x |
x2-7(mod p) |
(x2-7/p) |
Hp |
部分群位数kg |
|
0 |
4 |
+1 |
- |
- |
|
1 |
5 |
+1 |
- |
- |
|
2 |
8 |
-1 |
P(2) |
1 |
|
3 |
2 |
-1 |
P(3) |
6 |
|
4 |
9 |
+1 |
- |
- |
|
5 |
7 |
-1 |
P(5) |
6 |
|
6 |
7 |
-1 |
P(6) |
3 |
|
7 |
9 |
+1 |
- |
- |
|
8 |
2 |
-1 |
P(8) |
3 |
|
9 |
8 |
-1 |
P(9) |
2 |
|
10 |
5 |
+1 |
- |
- |
群演算の導入
[編集]群演算(+)は、2項演算であり、第1のｘ値 (x1)と第2のｘ値(x2)とを結ぶ第 1の直線が2次双曲線と作る交点(x3)を第1の 半演算とし、その交点(x3)と固定点 (x0 )とを結ぶ第２の直線が2次双曲線と作る交点 (x4)を第2の半演算とし、その双方の半演算 の結果を全体の演算結果(x4)とする。先の元 表示に従えば、P(x1)+P(x2)=P (x4 ) と成る。この方法は、3次曲線である楕円曲線に おいて有限体上の加群が定義される方法と同じである。 ここで(1-1)式の下で、第1の直線をy=mx+Aとして、具体 的な群演算式を求める。
・・・(3-1)
・・・(3-2)
により直線パラメータm, A を定め、次の(3-3)式の ３次方程式の根と係数の関係からx３値を定 める。即ち、
・・・(3-3)
(3-3)式の３次方程式の３根である x1, x2, x3の和 から
・・・(3-4)
(3-1)式及び(3-2)式より
・・・(3-5)
同様に
または、
・・・(3-6)
(3-4)式、(3-5)式、及び(3-6)式より
・・・(3-7)
次に、第２の直線をy=nx+Bとして
・・・(3-8)
・・・(3-9)
・・・(3-10)
の３式より、変数x3, n, B を除き、 x4値をx1、x2の関数 として求める。この結果は、
(3-7)式で、x1,x2→ x0,x3と変数を入れ替えたものと 同じである。
・・・(3-11)
(3-11)式第2項の分子を計算すると
・・・(3-12)
群演算式(3-12)は、パラメータｃ及びｄに依存しな い。これは２次双曲線の完全な３次関数でない面が出た ものと考えられる。では、勝手に決めることができると してc=d=0のように選べば、２次双曲線ではなくなってし まう。他方で、固定点x0をどのように選択するかの基準 もない。そこで、固定点x0の選択を上記パラメータと関 連づけて選択する方法が考えられる。
・・・(3-13)
実際には、２次双曲線群の設計において、 cx0+d=0のように関数(1-1)式のゼロ点に選択 することが多い。特に自由度の残っているパラメータｃ を固定し、c=1, x0=-dと選択することが多い 。
群の成立要件
[編集]以下では2次双曲線群の成立要件を検証する。
（１） 単位元の存在
群演算式(3-12)において、2次双曲線上の整数点 x1,x2の演算結果はx4であり、これは元の表現でP (x1)+P(x2)=P(x4) と表現できた。仮にP(x4)= P(x1 )であれば、そのようなP(x2)は単位元を 与える。(3-12)式で
とすると、
・・・(3-14)
条件(1-2)式により、x2=x0 を得る。即ち、単位元はO=P(x0)であった。
（２）逆元の存在
群演算式(3-12)において、2次双曲線上の整数点 x1,x2の演算結果はx4であり、これは元の表現でP (x1)+P(x2)=P(x4) と表現できた。仮にP(x4)= P(x0 )であれば、そのようなP(x2)は逆元を与 える。(3-12)式で
とすると、
・・・(3-15)
となる。P(x1)の逆元はP (x2)である。ところが、(3-15)式からして、 その分母が0になる場合があり、その場合逆元が存在しな いことになる。そのような元P(x1)は
若しくは
・・・(3-16)
である。然るに、(3-16)式からして
であるので、 が平方数であることが知れる。それ故 、
・・・(3-17)
であって、(1-2)式の要件を満たさないのでP (x1) は2次双曲線群の元ではない。即ち、逆 元は、(1-2)式の要件下で常に存在することが示された。
（３）群演算の閉鎖性
群の構成要件のうち、見落とされやすいのがこの要 件である。2項演算の結果が、元の集合に属していなけれ ばならない、とする。ここでは、(1-2)式の要件を演算結 果であるx4が満たすことを示す。群演算式 (3-12)から、 を計算すれば、
即ち、
・・・(3-18)
を得る。(3-18)式で、O=P(x0)はゼロ元 であり、常に2次双曲線群の元であることから
である。それ故、
・・・(3-19)
となって、(1-2)式をx4値が満たすこと が示された。それ故、P(x4)は2次双曲線群の 元である。
（４）結合法則
結合法則は、群演算の順番によって結果が変わらな い、という秩序を要請する。具体的には、群演算式(3- 12)において
(P(x1)+P(x2))+P (x3) =P(x1)+(P (x2)+P(x3)) ・・・(3-20)
を示せばよい。 (3-12)式の左辺()の結果は
であり、これを左辺全体の群演算式
・・・(3-21)
に代入すると、
即ち、
・・・(3-22)
上記(3-22)式は、変数 x1,x2,x3の対称式で あって、その順番を入れ替えてもx5値は変わ らない。それ故、結合法則が証明された。
４、群位数
2次双曲線群の群位数は、剰余環Z/pZ上で作る群であ るので、多くともｐ個以下である。実際には要件(1-2)式 を満たすｘ値の個数で決まり、既に記載しているように 半分程度に減ることが知られている。そこで、ここでは この群位数を理論的に確定することにする。
要件(1-2)式は、(x2+ax+b) 値が非平方 数であることを要求している。そこで、最初に平方数の 個数を勘定する。その平方数をy2として置こ う。然らば、
(x2+ax+b)=y2 (mod p)・・・(4-1)
であり、この式は
若しくは
・・・(4-2)
と成る。但し、D値は2次方程式の判別式である。値 ４は素数の法に対して平方数であることに注意する。こ のとき、
・・・(4-3)
と置き換えると
(mod p)・・・(4-4)
と表示できる。但し、x,yの組とX,Yの組は2変数で対 応し、1対1である(同型という)。
この(4-4)式のXとYの関係は、初等整数論における対 遇(spouse)として知られている。参考文献(2)の①第７０ 頁には以下の定理が掲示されており、その証明も参考文 献(1)の④第３３頁に掲げて置いた。
【定理】 ａをｐで割り切れない整数とすれば、集 合Ａ＝｛１，２，…，ｐ－２，
ｐ－１｝の中の任意の整数ｒに対して、ｒｓ≡ａ（ ｍｏｄｐ）を満たす整数ｓが集合Ａ
の中にただ一つ存在する。当該整数ｓをｒの配偶と 呼ぶとき、ｓの配偶はｒであり、同一
の数の配偶はただ一つに限る。したがって、配偶の 組み合わせは、原則として、（ｐ－１
）／２個存在する。ただし、ａが平方剰余であると きは、ｒの配偶ｓがｒである場合並び
にｐ－ｒの配偶ｓがｐ－ｒである場合が存在する。 これらの２つの場合を例外として除外
すれば、配偶の組み合わせは、（ｐ－３）／２個存 在する。
【定理終わり】
従って、(4-4)式を満たすX値は、判別式Dが平方数で あるときに(p+1)/2個、判別式Dが非平方数であるときに (p-1)/2個であり、これはｘ値が(4-1)式を満たす個数で もある。然るに、2次双曲線群の群位数kGは 、要件(1-2)式を満たすｘ値の個数であるので、
・・・(4-5)
・・・(4-6)
となる。
第2章の具体例でのH11では、a=0, b=-7 であるので、D=28≡6 (mod 11)であり、
6(p-1)/2=65≡-1 (mod 11) である。従って、(D/p)=-1であるから、(4-5)式により kG=6を得る。
また、異なる素因数r,sの積でn=rsのときには、 （D/r）値と（D/s）値との組み合わせで、その群位数 kGが決まる。即ち、判別式Dの属性が群位数 kGを決定する。この時、法ｎが単独の素因数 ｒのときの群位数をkr 、法ｎが単独の素因数ｓのときの群位数をks とすると、法n=rsのとき kG=krksとなって、 全体の群位数が合成数で、それ等の直積となることに注 意したい。即ち、法ｎがｍ個の異なる素因数で構成され る場合、全体の群位数k Gは
・・・(4-10)
となり、各kiはその判別式Dの属性 (D/pi)で決定される。
2次双曲線群の群位数は、要件(1-2)式の下で各素因 数毎に半減することから、法ｎが合成数であればその利 用範囲が相対的に狭まり、その利用価値も下がる。
５、部分群(生成群)
2次双曲線群の元自身を何回も加算してゆくと、終に kP(x)=Oとなる最小の整数kgを得る。このkg値を部分群位 数と呼ぶが、その部分群位数は必ずしも群位数 kGと一致しない。例えば、単位元O=P (x0 )ではkg=1である。ユークリッドの互助法を使うと、 その部分群(以下、生成群という。)位数kgが群位数 kGの約数であることを示せる。例えば、 kG=nkg+r(0<r<kg, n：正整数)と置いて、矛盾を導けばよい。それでは 、部分群位数kgを有する元の個数、若しくは群位数kgを 有する生成群の個数は何個であろうか？ この答えにな るのが、これから解説する拡張オイラー関数G(kg)である 。その導出等については、参考文献を参照して欲しい。 ここでは、その有用性を開示しておく。拡張オイラー関 数G(kg)は、
・・・(5-1)
と明示で表示できる。ここでkg|kLであ って、そのkLは最大周期と呼ばれ
・・・(5-2)
であって、総ての生成群位数の最小公倍数として求 める。
拡張オイラー関数G(kg)は、i≠jのときに (ki, kj)=1であれば、オイラー 関数φ(kg)に一致する。法ｎが素数ｐの1個だけのとき、 即ち、n=pのときも同じである。
第2章の具体例でのH11では、kg=6の生 成群の個数はφ(6)=2個、kg=3の生成群の個数はφ(3)=2 個、kg=2の生成群の個数はφ(2)=1個、kg=1の生成群の個 数はφ(1)=1個という構成になっていた。 (ki, kj )=h≠1のような一般の場合は、拡張オイラー関数G (kg)によってのみ計算できる。それに拠れば、共通の要 素h≠1により、全体の生成群の個数は、特に高い次数の 生成群において急増する。例えば、法nを構成する素因数 が2個で、r=29,s=59 の場合で、判別式Dが何れも非平方数のとき、下表の ようになる。但し、 n=1711,kr=15,ks=30,kG=450,kL=30である。
<tbody> </tbody>|
rank kg |
φ(kg) |
G(kg) |
|
30 |
8 |
192 |
|
15 |
8 |
192 |
|
10 |
4 |
24 |
|
6 |
2 |
8 |
|
5 |
4 |
24 |
|
3 |
2 |
8 |
|
2 |
1 |
1 |
|
1 |
1 |
1 |
拡張オイラー関数G(kg)は、当該2次双曲線群の構造 を記述する、構造関数としての意義を有する。しかし、 その群位数kG は判別式Dの属性により定まる部分群位数の直積で決 まるのであって、拡張オイラー関数G(kg)が直接部分群位 数値を決めているわけではない。単に、その直積構造下 の詳細構造を記述するに留まる。
離散対数
[編集]2次双曲線群の群演算をk回行うと、例えばkP(x)=P (y)という結果を得るが、P(y)を知って整数ｋを知ること は難しくない。元P(x)に関し最大周期kL回の 演算を行えば、有限巡回群の性質から、その間にP(y)が 出現する。しかし、平均でもkL /2回の群演算を行うので、その計算回数は法ｐの下 でもかなりのになる。通常単独での計算負荷が最も多い のが剰余群ZpZ下の逆元計算で、 (p-1)回の逆元計算を要する。しかし、これは実際に は1回に節約できる。2次双曲線群の群演算をn回行うと、 (3-22)式のように、その演算結果はn+1次対称式として表 示される。それ故、群演算における剰余乗算の回数は、 各次数の対称式での乗算回数の総和は各次数の積の個数 の総和で
回必要である。従って、平均してkL/2回 の群演算が必要で、法n=p(kL=p)の下でも少 なくともp2p 回程度の剰余積演算が必要となる。素数ｐ値が大き なときには、その計算負担は大型計算機の負荷を超える かも知れない。そこで、これを「離散対数を求める困難 さ」という意味で離散対数問題という。楕円曲線群暗号 では、この離散対数を求める困難さを根拠に、素数ｐの 大きさを160ビット以上に要求していた。今日では、計算 機の能力向上でこの数倍は必要になっている。ここでは 、2次双曲線群も、同様に、「離散対数を求める困難さ」 を有していることを示しておいた。
沿革
[編集]楕円曲線群暗号に代わる新たな曲線の探索において 、2005年頃に2次双曲線群(Quadratic Hyperbolic Group) が発見され、その結果は主に公開特許文献等に開示され 、その後10年が経過した。その間、2次双曲線群に掛かる 諸問題が探求され、2009年には群設計用のソフトウェア 「HCG Test Tools」が開発され（参考文献(1) ②）、米国CNETに おいて配布されるに至った。このソフトウェアは、2013 年に至って、上記拡張オイラー関数の表示を中心に強化 された(特許出願済み)｡また、2010年には、実際に暗号作 成ソフトウェア「HCC Test Application」が開発された （参考文献(1) ①）。
2次双曲線群は、若干複雑ではあるが、初等整数論で 容易に理解できる、という利点を有している。また、2次 双曲線群の設計は、当初から曲線パラメータや素数位数 を付与できるという格段のメリットを有する。同じく離 散対数を根拠とする楕円曲線群に比べ、圧倒的に有利と いえるだろう。特に、同一素数位数の群を複数用意でき るメリットは、離散対数の困難さを簡易に倍増させ、か つ、計算容易性を維持できる利点をもたらす。しかしな がら、現実には２次双曲線群の知名度は未だ低い。実用 性だけでは普及しないのかも知れない。
参考文献
[編集]この項目は初等整数論の知識で容易に理解できる事項ばかりなので、参考文献を挙げる必要はない。しかし、更に進んで理解したい者のために幾つか掲げた。
（１）「初等整数論構義（第２版），高木貞治著（共立出版）の第７０～７１頁： 配偶に係る定理を引用している。
（２）堀江 公人―2次双曲線群入門： 上記諸計算の詳細が記載されている。
（３）WEB