双曲線暗号の設計ツール
【課題】２次双曲線群はその位数が一定で初等的取り扱い方が可能であるが、複数の単位暗号化装置を具備する鍵生成装置において多数の曲線パラメータの組を特定する作業が必要になる。例えば、整数論的関数で、法ｐ及び曲線パラメータa,b,cを定めなければならない。従って、これ等の曲線パラメータ等を簡易に生成できるツール(ソフトウェア)を提供する。
【解決手段】双曲線暗号の設計ツールであって、素数テストツール、２次双曲線群設計ツール、２次双曲線群解析ツール、拡張２次双曲線群解析ツール等から構成されている複合ツールで、このツールだけで設計と解析が完結する構成を有している。
【解決手段】双曲線暗号の設計ツールであって、素数テストツール、２次双曲線群設計ツール、２次双曲線群解析ツール、拡張２次双曲線群解析ツール等から構成されている複合ツールで、このツールだけで設計と解析が完結する構成を有している。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、拡張された２次双曲線群の離散対数を利用した双曲線暗号の設計ツール(ソフトウェア)及び鍵生成方法に関するものである。
【背景技術】
【０００２】
２００５年の７月に楕円曲線暗号に代わる双曲線暗号の探索において２次双曲線群が発見された後、その成果は２００７年２月特許出願された「二次双曲線群を使用する鍵生成方法、復号方法、署名検証方法、鍵ストリーム生成方法および装置」(特許文献１)に結び付けられた。その後２次双曲線群の研究が進み、法ｎが合成数である拡張２次双曲線群、特に法ｎが素数ｐのべき乗（pn）である場合に拡張され、拡張２次双曲線半群、拡張オイラー関数、逆元計算後回し法、２次双曲線群を用いた素因数分解の方法等の成果が２００８年３月の特許出願「双曲線暗号の鍵生成方法」(特許文献２)に開示されるに至った。
【特許文献１】特開2008-203548号
【特許文献２】特開2009-223035号
【０００３】
楕円曲線暗号で使用される楕円曲線関数は３次関数であり、双曲線暗号で使用される２次双曲線関数は整数論的関数ではあるが実質的には３次関数であるので、楕円関数を限定すれば双曲線関数と等価になる。どの様な数学的な条件下で等価になるかはまだ明らかではないが、双曲線暗号に近い形で楕円曲線暗号を形成することは可能だろう。更に、前記特許文献で案出した同値対や拡張２次双曲線半群等の概念が類似の形態で出現する可能性は高い。しかし、２次双曲線群は具体的に種々の条件が特定されているので、より明確な結果が出現すると予想される。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
２次双曲線群はその位数が一定で初等的取り扱い方が可能であることから、その理解に困難な点はないが、その全体像が複雑であることは否めない。特に２次曲線の判別式Ｄ及び当該２次曲線自体が平方非剰余であること等の制限から、複数の単位暗号化装置を具備する鍵生成装置において多数の曲線パラメータの組を特定する作業が必要になる。例えば、
【数１】
・・・・（１―１）
という整数論的関数で、法ｐ及び曲線パラメータa,b,cを定めなければならない。
従って、これ等の曲線パラメータ等を簡易に生成できるツール(ソフトウェア)があれば大変に便利である。また、双曲線暗号はまだ開発が始まったばかりであり、初心者が簡易に２次双曲線群を構成でき、かつ、その解析ができれば、その理解を助け、双曲線暗号の普及に拍車が係るに違いない。
【０００５】
曲線パラメータ特定作業を簡易に生成できるツールとはどの様なものだろうか。双曲線暗号を全く知らない者がその曲線パラメータを特定するとき、その選択肢を行使でき、色々と試してみる自由度を有していなければならないだろう。そもそも法ｐの特定はどうすべきだろうか。選択した法ｎが素数なのか合成数なのかも知らなければならない。当該２次双曲線群の最大位数kqを得るためには、ベースポイントP(x)の選択にも配慮しなければならない。選択し特定した２次双曲線群の下で双曲線暗号を構成したとき、その２次双曲線群がその利用に適したものか否かを判定するためには、初心者でも容易に解析でき、かつ、その結果を表示できるツールにしておきたい。
【０００６】
作成した２次双曲線群を具体的に利用するためにはファイル構成を採用することが望ましい。他のアプリケーションソフトウェアでの簡便な利用が可能になる。
【課題を解決するための手段】
【０００７】
本発明に係る双曲線暗号の設計ツール(HCC Design Tools)は複合ツールであり、素数テストツール(Prime Test Tool)、２次双曲線群設計ツール(HCG
Design tool)、２次双曲線群解析ツール(HCG Analysis tool)、拡張２次双曲線群解析ツール(Extended HCG Analysis
tool)等から構成されており、このツールだけで設計と解析が完結する構成を有している。
【０００８】
素数テストツールは法ｎが素数か否か判定し、素数ｐをその後利用するときはその採択を決定できる構成を有している。Germann素数判定機能、素因数分解表示機能はこの素数テストツールの特徴になっている。
【０００９】
２次双曲線群設計ツールでは、曲線パラメータの選択窓を有し、諸条件を満たす曲線パラメータ値が提示される。設計者はその中から任意に曲線パラメータを選択でき、かつ、新たな曲線パラメータへの更新も行うことができる。選択された曲線パラメータは、その旨の表示が行われる。特定の２次双曲線群に対応する採用された曲線パラメータの組は、保持され容易にその表示を行うことができ、かつ、必要な装置分だけ保存することができる。この組の一覧は、グリッドビュウ(Grid View)においてリスト化し、編集できる機能を有している。
【００１０】
２次双曲線群解析ツールでは、確認された曲線パラメータで特定された２次双曲線群の解析及び集計が行われ、その部分群の全体が明らかにされる。位数kgを有する共役部分群の個数、ベースポイントP(x)、及び当該部分群の構成要素の表示はこの解析ツールの特徴に成っている。設計者は特定された２次双曲線群の全体像、及び構成を知り、その採否を決定する材料にすることができる。
【００１１】
拡張２次双曲線群解析ツールは、拡張２次双曲線群の解析、特に法ｎが合成数である場合の拡張オイラー関数(GCD totient)の解析を行うことができる。拡張オイラー関数は、発明者により新たに発見された整数論的関数で、この特許明細書でその詳細が明らかにされる。しかし、このツールでは設計ツールとして、その項別級数表示、要素(GCD
set)解析等を行って、その結果を表示するにとまっている。ただ、拡張オイラー関数のグラフィクスツール(Graphics tool)も用意し、研究者等の利用の便宜を図った。
【発明の効果】
【００１２】
本発明に係る双曲線暗号の設計ツールは、複合ツールで設計と解析が完結する構成を有し設計者に使い易くなっている。各ツールの固有な構成からは以下の効果を奏する。
【００１３】
素数テストツールは本発明に係る設計ツールで採用される法ｐを選択する機能を有しており、単なるテストだけを行うものではない。そのGermann素数判定機能は、選択した２次双曲線群の位数が法ｐの下でも素数であることを保証する。これは任意にベースポイントを採択する自由を設計者に提供する効果を奏する。従って、設計者が係る法ｐを採用する手助けになる。素因数分解表示機能は、言うまでも無く法ｎが合成数でどの様な素因数から構成されるかを簡明に知らしめる。
【００１４】
２次双曲線群設計ツールの曲線パラメータの選択窓は、諸条件を満たす曲線パラメータの候補を提示し、その選択を設計者に委ねる効果を有する。提示されるパラメータ値は何度でも更新することができるので、設計者は小さ過ぎるパラメータ値若しくは法ｐに近いパラメータ値を避け、適当な大きさの値を選択できる。特定の２次双曲線群に対応する採用された曲線パラメータの組は、ソフトウェア内で保持され、容易にその表示を行うことができ、かつ、必要な装置分だけ保存することができると共に、何時でも更新することができる。特に、グリッドビュウによりリスト化し、編集できる機能を有しているので、簡易に必要な数の組を揃えるのに便宜である。
【００１５】
２次双曲線群解析ツールでは、曲線パラメータで特定された２次双曲線群の解析及び集計が行われ、その部分群の全体が明らかにされることから、設計者は採用した曲線パラメータの組が適当な群構成を有していることを確認でき、特に群位数が合成数kgである場合に当該群位数の約数を位数とする部分群の確認を行うことができる。法ｎがGermann素数で、その群位数が素数である場合には、ゼロ元を除く全てのベースポイントが最大位数kgであることを確認することができる。
【００１６】
拡張２次双曲線群解析ツールで取り扱う拡張オイラー関数Φは、拡張２次双曲線群の位数kg及びその約数を位数とする共役部分群の個数を与える重要な意義があり、位数kgを有する部分群の個数はΦ(kg)個である。ここで共役とは位数kgが同一で同型である部分群間の関係を言う。その項別級数表示は、従来のオイラー関数との対比を明示するもので、その拡張性を明示する表示方法である。積集合の要素表示は、ＧＣＤ演算と部分群位数kiの積を集合(積集合)と捉えた場合の１要素を与えるもので、位数ｋ(k=Πki)の構造を明らかにする。従って、要素表示の具体的計算は位数ｋの構造そのものを明らかにする。
【００１７】
拡張オイラー関数のグラフィクスツールは、拡張オイラー関数Φを具体的に計算しグラフ表示するものであり、従来のオイラー関数φとの差異を視覚的に明示する効果を奏する。
【発明を実施するための最良の形態】
【００１８】
以下、本発明に係る種々の実施例について説明する。
【００１９】
＜第１実施例＞
図１は、本発明の２次双曲線群設計ツール(ソフトウェア)の全体図であり、素数テストツール、２次双曲線群設計ツール、２次双曲線群解析ツール、及び拡張２次双曲線群解析ツール等から構成されている。このように各ツールを１個のソフトウェアに統合し、かつ、フロントに並べたので、設計者にとって使い回しの良いツールとして利用することができる。設計者は、図１左上の素数テストツールで法ｐを決めた後に、図１右の２次双曲線群設計ツールで曲線パラメータの各組を採用し、図１左中の２次双曲線群解析ツールで採用した２次双曲線群の適否を確認し、採用した各２次双曲線群をファイルの形で保存することができる。
【００２０】
このソフトウェアの開発は、２００８年５月にマイクロソフト社の「Visual Studio 2008」を用いて、VC++で行われた。NET.Framework V3.5のWindows(登録商標)プログラムである。開発開始後、約半年の作業で原型が出来上がり、その後半年掛けてバグ抜きや改良が行われた。同時にデモンストレーション用のアプリケーションソフトウェアも開発されたが、本発明との直接の関連が薄いので別の機会に開示する予定である。ただ、このツールで採用された２次双曲線群のパラメータファイルが利用できる構成が採用されている。
【００２１】
図２は、本発明の素数テストツールであり、本発明に係る設計ツールで採用される法ｐを選択する機能を有しており、単なるテストだけを行うものではない。素数判定の方法には「篩（ふるい）法(sieve method)」を用いており、高級な方法は採用していない。その１の理由は本発明に係るツールが主にデモンストレーションを目的として開発され、法ｐが大きなビット数を有することは前提としていないことを挙げる。法ｐに大きな数値を選択した場合、その後の群演算に大きな負担となり、事実上群演算は困難になる。その第２の理由は、単純ループで割り算を行うのでＰＣによる高速演算に向いている、ことにある。
【００２２】
図３は、法ｎとしてn=1023をテストした結果を表示してある。この結果は、
「n=3^1*11^1*31^1」、「_1023 is not a prime」であるので、法ｎが合成数で素因数3,11,31の積であることを示す。次に図３において法ｎとしてn=1031をテストした結果を表示してある。この結果は、「n=1031^1」、「1031
is a prime」であるので、法ｎが素数であることを示す。テストは第１のテキストボックス(textBox1)にｎ値を入力し、テストボタン「Test」を押下することにより行われる。
【００２３】
篩法の具体的なアルゴリズムは図４に示されている。図４で、「Start」から開始し、最初に法ｎの候補値である数値を入力し、「Test」を押下すると、最初は小さな素因数(2,3,5,7)を割り数値ｋとした直接の割り算が行われる。素数密度の関係からも、ｎ値に小さな素因数が含まれる可能性が高いからである。
【００２４】
その余りが０であればその素因数を値ｎが有するので当該割り数値ｋを保存し、余りが０でなければその素因数を値ｎが有していない、と判定できる。
【００２５】
その素因数をｎ値が有していれば、新たなテスト値をn←n/kとして、残りの素因数を探し出すことになる。但し、素因数のべき乗の場合を考え、同一の素因数による割り算が繰り返され、割り切れない場合にのみ前記割り数値ｋの更新が行われる。割り数値ｋの値が候補値である値ｎの平方根(√n)を越えた場合には、１以外の如何なる素因数をも有していないので、当該ｎ値を素数と判定できる。
【００２６】
本発明に係る素因数分解表示の方法は、以下に示すように主に２通りあるが、実際には後者の方法が採用されている。
【００２７】
第１の方法は素因数分解が終了し、素因数の個数Ｉが判明した場合に、各素因数毎にテキスト列を増やしてゆく方法（テキスト増加法）である。例えば、法ｎとしてn=1023を選択したとき、最初に空文字列「String^myText=””」が定義された後に、各素因数毎に「myText=3^1」＞「myText=3^1*11^1」＞「myText=3^1*11^1*31^1」とテキストの長さを増やしてゆき、リスト(listBox1)への書き込みは一度に行う
「listBox1->Items->Add(myText)」。
【００２８】
第２の方法は、リスト内の当該行のデータ「myText=listBox1->Items[i]->ToString()」を読み取り、新たなデータを追加し「myText=ｍyText+”*”+p+”^”+a」(p:当該素因数、a:当該ベキ数)
、当該行を削除した後に追加後のデータを書き込む方法（書き込み行更新法）で、書き込みと削除は素因数の個数ＩにつきＩ回行われる。即ち、各素因数毎に当該行の表示が「n=3^1」＞「n=3^1*11^1」＞「n=3^1*11^1*31^1」と切り替わってゆく。この方法は既にある表示をそのまま生かす点で便利である。
【００２９】
図５は、本発明に係るGermann素数判定方法を開示したフロー図である。最初に試し数ｐを入力し、前記図４に示した篩法のアルゴリズムにより当該ｐ値が素数か否か判定し、その後q=(p+1)/2を計算した後、再び篩法のアルゴリズムにより当該ｑ値が素数か否か判定する。当該ｑ値が素数であれば、対応する素数ｐはGermann素数である。当該ｑ値が素数でなければ、対応する素数ｐはGermann素数ではない。
【００３０】
図６は、本発明に係るGermann素数判定機能を実行した図である。試し数n=1237を素数テストした結果素数と判明したので、当該行「1237 is a
prime.」を青く選択した後に「Judge」ボタンを押すと、Germann素数判定が行われる。
【００３１】
Germann素数とは、素数ｐに対し値q=(p+1)/2も素数であるような素数ｐを言う。このような素数の組はその存在密度は高くないが、無限に存在することが知られている。２次双曲線群では、法phの場合、その群位数kはk=ph-1(p+1)/2であるので、h=1の場合は法ｐがGermann素数であることは当該２次双曲線群で素数位数を獲得することを意味する。
【００３２】
そして、その群位数が素数である場合には、ゼロ元を除く全てのベースポイントが最大位数kを有する部分群であることが、理論上明らかになっている。即ち、この様な２次双曲線群では位数qを有するφ(q)=q-1個の部分群と位数１を有するゼロ元１個で構成される。従って、ゼロ元を避ければ、ベースポイントP(x)が最大位数を与えるか否かの判定をする必要がない。
【００３３】
図７は、法ｐが素数と判定された後に、その後の曲線パラメータの選定において当該法ｐを採用する方法を開示する。判定された素数を青く選択した後にラジオボタン(radio button)「Yes」をクリックすると、「p=1237 is adopted.」と表示されて、その後の法ｐの採用が確定する。
【００３４】
図８は、２次双曲線群設計ツールの上段部を示す。上部には２次双曲線方程式が画像(picutureBox1)として表示され、これから決定すべき曲線パラメータの配置を確認することができる。このソフトウェアでは最初に曲線パラメータｃを決定する構成にしたが、先に曲線パラメータｃを決定する構成にしても良い。何れにしても、判別式D/4=c2+4aが平方非剰余になるように双方を選択しなければならない。２次双曲線群の群位数kをk=(p+1)/2の関係に保つためである。
【００３５】
曲線パラメータｃ及びａでは何れの値も法ｐにおける剰余群(Z/pZ)に従うので、通常値ｐ以下の値を入力する。テキストボックス(textBox2)に直接入力しても良いし、「Generate‘c’」ボタンを押して乱数から採用しても良い。ただ、前記法ｐの指定が行われていない場合には、この選択はできないようになっている。曲線パラメータｃの採用は「Select‘c’」ボタンの押下により行われ、「c=1
is adopted.」のように表示される。
【００３６】
また、同時に、前記判別式の条件を満たす複数の曲線パラメータａ値４個がリストボックス(listBox2)に列挙される。曲線パラメータａの選択は乱数に基づいているので、「Select‘c’」ボタンの押下を再度行うと別の候補値４個が提示される。これは設計者が適当な選択をする便宜となる。図９のように、リストボックス内の１個の値を青く選択し、「Select‘a’」ボタンの押下を行うと、その採用と共に「a=311
is adopted.」のように表示される。
【００３７】
図１０は設計ツールの中段部で、曲線パラメータｂ値及びｄ値を定める。最初に「Renewal」ボタンを押下すると、曲線パラメータｂ及びｄの候補がリストボックス(liastBox3)内に表示される。この条件は(d2+cd-a),(b2+cb-a)が平方非剰余となることである。即ち、(x2+cx-a)
が平方非剰余となるようなｘ値を乱数の中から選び出し、リストアップする。
【００３８】
このうち、曲線パラメータｄはゼロ元P(d)≡Oを定めることに相当し、曲線パラメータｂは関数値のゼロ点であるが、必ずしもゼロ元とは関係がない。しかし、特殊な関係であるｂ＝ｄのような制約下でも、２次双曲線群の特性が損なわれることはない。「Select‘d’」ボタン若しくは「Select‘b’」ボタンを押すと、それぞれのパラメータ値の採用が決められ、「d=55
is adopted.」若しくは「b=189 is adopted.」のように表示される。
【００３９】
図１１は設計ツールの下段部で、曲線パラメータの組の保存を行う。保存スタックは２０段用意されており、２０組の各曲線パラメータを保存することができる。現スタック番号はテキストボックス(textBox3)に表示されており、この番号は「Num.Up」ボタンの押下で上昇し、「Num.Down」ボタンの押下で下降する。従って、素数テストツールで定めた法ｐ値、本設計ツールの上段で定めた曲線パラメータｃ値、ａ値、本設計ツールの中段で定めた曲線パラメータｄ値、ｂ値の組が、一体として当該スタック番号に記憶される。
【００４０】
曲線パラメータ等の設定が終了した時点で、「Import」ボタンを押すと、前記曲線パラメータ等が現に表示されているスタック番号に記憶され、仮に前データが存在した場合にも上書きが行われる。また、インポートされた曲線パラメータ等はリストボックス(listBox4)内に表示される。なお、現スタック番号の記憶内容がリストボックス内に表示されるので、「Num.Up」ボタン若しくは「Num.Down」ボタンの押下で、その表示も変化する。
【００４１】
「SetData」ボタンは解析のために現に表示されたデータを使うためのもので、その押下により、解析用の場所に当該曲線パラメータ等を複写する。橙色の「EditParam」ボタンは、選択された複数のパラメータの組をリストアップし、その一覧を表示する等ために使われる。これについては以下に詳しく解説する。
【００４２】
図１２は、本発明によるパラメータリスト(ParamList)であり、採用された曲線パラメータ等の一覧（右段）と共に、群計算の初期条件等を指定する領域（左段）を有している。このパラメータリストは、前記「EditParam」ボタンの押下により出現する。前記スタックは採用された曲線パラメータ等の記憶はできるが、その一覧には支障がある。そこで、本発明によるパラメータリストが採用され、その訂正等の便宜を図った他、併せて設計者が群計算の初期条件等を指定できるようにもした。このような初期条件は、前記アプリケーションソフトウェアへ提供され、利用されるもので、このツールとの直接の関係はない。
【００４３】
図１２右段のGridViewで作成されたパラメータリストは、本発明が曲線パラメータ等の生成ツールであることを配慮し、数多くのショートカットメニュー(Sort
Cut Menu)を有している。ショートカットメニューはリスト(gridView1)内で右クリックすると出現し、図１３のような内容を有している。パラメータリスト内の数値は自由に変更できるが、前記諸条件を満たす保証は一切ない。その変更は、「OK」ボタンを押すと、更新されて保存される。この更新は、前記スタックにおいても行われる。「Cancel」ボタンでは何の変更も反映されない。
【００４４】
図１３のショートカットメニューで、「ClearRowData」メニューは当該選択行のデータを全て０値にする。「RestoreRowData」メニューは、前記変更が行われた後にスッタクに記憶された元の値に戻したいときに使われる。「DeleteSelectedRow」メニューは、当該選択された行を削除し、新たに最終行(第２０行目)に１行追加する操作である。従って、当該行以下の既存のデータ行が１個ずつ繰り上がる。「CopySelectedRow」メニューは、当該選択された行のデータをコピーし、保存用のスタックに退避する。「PasteCopiedRow」メニューは、前記保存用スタックのデータを当該選択行に貼り付ける。「InsertNewdRow」メニューは、選択行の位置に新たに１行挿入する操作である。選択行以下の既存の行は１行ずつ繰り下がり、最終行は消滅する。
【００４５】
「ReCreateRowData」メニューは、自動設計ツールでもある。与えられた「Modulo p」値を法ｐとする曲線パラメータを、前記諸条件を満たすように、乱数を利用して自動生成する。従って、このメニューの利用のためには、予め適切な法ｐ値を当該選択行上に入力しておかなければならない。自動選択の後に当該行のデータを元に戻すには、「RestoreRowData」メニューを使うことができる。
【００４６】
図１４には、「ReCreateAllData」メニューを実行した後のリストが表示されている。「ReCreateAllData」メニューも自動設計ツールで、全ての行のデータを第１行目の「Modulo
p」値のもとで自動選択する。従って、このメニューの利用のためには、予め適切な法ｐ値を第１行目に入力しておかなければならない。自動生成で、偶然にパラメータ値の２個が同一値の場合は、当該後に生成されるデータにつき再度の自動生成が行われるが、通常同一値が出現することは稀である。
「SetDataToAnalyze」メニューは、前掲の「SetData」ボタンと同じ役割であり、当該選択行のデータを解析のために提供する。その実行は、当該選択行のデータを解析用の場所に複写する。
【００４７】
図１２左段の群計算の初期条件等を指定する領域は、このツールとの直接の関係はなく、アプリケーションソフトウェアのために提供されているが、一応の説明をする。「Initia Oop Cycles」項目は、群計算の暗号化開始設定を遮蔽するために必要な群計算の回数を指定する。秘密鍵との連携が取られる。「KeyMargin」項目は、群演算の最低演算回数を指定するもので、これも秘匿性の向上のためである。「InitialWorkingKey」項目は、複数の暗号化装置が連帯して作動するときの初期値を与える。
【００４８】
「InitialBP(x)」項目は、ベースポイントを与えるｘ値を選択する項目で、x値は任意に入力できるが、所定の要件を満たさなければならないことから、そのテストが行われる。選択行の曲線パラメータ等の下でそのベースポイントが有効か否かは、「BP
Test」ボタンの押下で判定され、その結果が表示される。「EncryptMethod」項目は、その暗号化方式の選択のために使われる。
【００４９】
図１５は、本発明に係る２次双曲線群解析ツールの全体図であり、与えられた曲線パラメータ等の下での２次双曲線群の構造を明らかにする。
【００５０】
図１６は、本発明に係る解析集計アルゴリズムを示したフロー図で、それぞれ上半部は解析プロセス、下半部を集計プロセスを開示する。
【００５１】
解析プロセスでは、ベースポイントと成り得る全てのｘ値が対象となり、そのベースポイントP(x)を出発点とする部分群Q(x)の位数kgが調べられる。最初にx=0の条件から始め、
【数２】
が平方非剰余であるかを調べる。具体的には、
【数３】
が計算され、その値が-1(平方非剰余)か+1(平方剰余)であるかを調べる。そのτ(x)値が平方非剰余であれば、そのベースポイントP(x)は当該２次双曲線群の元であり、当該ベースポイントP(x)を出発点とする部分群Q(x)の位数kgを調べる。
【００５２】
k=1から始め、kP(x)を計算し、その値がゼロ点Ｏ=P(d)に一致するかが調べられる。実際にはx=dであれば足りる。k=kgのとき、kgP(x)=Ｏであれば、そのkg値が当該部分群Q(x)の位数になる。計算された群位数は、当該ｘ値と共にテキストファイルに出力される。その後の集計プロセスの便宜のためである。x値は剰余群Z/pZのもとで定義されているのでｐ個の値が可能である。２次双曲線群の理論によれば、平方非剰余を与えるｘ値の数は法ｐの下では最大(p+1)/2個で、当該２次双曲線群の元の数、位数ｋに一致する。即ち、
【数４】
である。
【００５３】
前記解析プロセスの終了後、集計プロセスを始める。最初にファイルの先頭から１行ずつ読み出し、当該計算された位数kgを読み取り、既に同一のkg値が存在する場合にはその値の計数個数を＋１する。同一のkg値が存在しない場合には当該kg値の欄を新たに設け、その計数個数を１個とする。この方法により最後の行を処理した後、群位数kgの大きさの順番に並べ替える。表示リストには、存在したkg値の異なる値の数の分だけ大きさの順に項別表示する。
【００５４】
図１７は、解析で用いる曲線パラメータ値等の確認を行っている。「ConfirmSet」ボタンを押すと、前記「SetData」ボタン等で指定した曲線パラメータ値等の確認を、リスト(listBox5)内の表示により行うことができる。
この例では「p=1031,a=244,b=167,c=1,d=145」と表示されている。
【００５５】
図１８は、解析実行のために「Analyze」ボタンを押したときの、その実行結果を表示している。その解析プロセスは図１５上段に示されている。実行結果は、ファイルにも出力されるが、リストにも表示することにした。例えば、「Q(1);
kg=129;」とあるのは、ベースポイントP(1)を始点として群演算を開始したとき、129P(1)に至ったとき始めてゼロ元Ｏと一致したことを意味する。従って、このベースポイントP(1)を有する部分群Q(1)の位数はkg=129と言うことになる。なお、法ｐの値が大きく、群演算の負担が大きいときには、プログレスバーでその実行の進行度を知ることができる。
【００５６】
リスト内には全ての実行結果が表示されているが、このままでは群構造全体の有効な情報を引き出すことはできない。そこで、「DataSum」ボタンを押して、データの集計、整理を自動的に行う。この集計は前記ファイルの検索により実行され、その集計プロセスは図１５下段に示されている。
【００５７】
例えば、「The number of Ｑ(x) with kg=516 is 168.」とあるのは、この２次双曲線群で位数kgを有する部分群Ｑ(x)でkg=516であるものの個数は、全部で１６８個であることを意味する。リスト上部には、「rank
k=516」と表示され、発見された部分群位数のうち最大のものを表示している。これは２次双曲線群の群位数ｋが５１６であることを示している。２次双曲線群の理論によれば、位数kgを有する共役部分群Ｑ(x)の個数は、法ｐが素数であるときφ(kg)個であるので、φ(516)=168により、その理論の確認をすることができる。しかし、ここでは理論と関係なく、群演算のみが実行されその結果が表示されている、と言う点に注意しなければならない。理論は現象を説明するために後から付けた理屈に過ぎない。
【００５８】
設計者は、図１９のリスト内の１行を青く選択した後に「Precisely」ボタンを押すと、その集計結果の詳細を知ることができる。図２０は、その様な詳細結果の一例で、図１９のリスト内の第２行目選択した場合の結果である。群位数kg=258を与える共役部分群Q(x)の個数は８４個あり、それ等の一覧が昇順に「Q(16);Q(17);Q(31);Q(43);・・・」のように表示されている。
【００５９】
ここでは、更に各部分群の詳細な構成を表示することができる。図２１は、その様な詳細結果の一例で、図２０に示された部分群Q(16)の詳細な構造を示してある。この表示は、図２０の該当部分群を青く選択した後、再び「Precisely」ボタンを押すとその表示をすることができる。
「1P=(16,326),2P=(397,609),3P=(683,901),4P=(865,372),5P=(723,335),・・・」と表示されたのは部分群Q(16)の２５８個の各元に対応する。各数値は、例えば1P=P(16)、2P=
P(16)+P(16)の意味である。
【００６０】
演算結果の取得には、リストボックス内で右クリックしたときに現れるショートカットメニューを利用することができる。「Copy」、「Paste」、及び「SellectAll」のように、複写、貼り付け、及び全選択のメニューを用意した。
【００６１】
図６は、本発明に係る拡張２次双曲線群の解析ツールである。拡張２次双曲線群では、法ｎは合成数で、法が素数の場合に比べてかなり複雑な構造を有する。実際この数年間で理論的な究明が進んで、かなりの事実が明らかになっている。しかし、未だ明らかでなく、数値計算のみの手探りの分野も少なくない。このツールを提供する目的は、主に研究・開発の用途である。
【００６２】
設計者が、法ｎの候補と考える数値をテキストボックス(textBox4)に入力し、「CalcEHCG」ボタンを押下すると、図２２に示すように、リストボックス(listBox6)内に種々の計算結果が表示される。何を計算したのかは、順次説明することにする。
【００６３】
図２３では、n=1027の場合に、その計算結果を全て明示した。
第１行目の「EHCG
modulo: n=1027=13^1*79^1」は、法ｎの素因数分解表示で、これにより実際に法ｎが合成数であることが示される。
第２行目の「GruopRank:
k=280=7*40」は、拡張２次双曲線群の群位数がk=280であることを示し、次の積表示は拡張形でない２次双曲線群の群位数k1,k2との関係が示されている。法ｎの構成素因数p1=13,p2=79から生成される２次双曲線群の群位数k1,k2は、k1=(p1+1)/2=7,
k2=(p2+1)/2=40であり、ここではk=k1k2の関係が成立していることを確認できる。GCD(k1,k2)≡(k1,k2)=1だからである。(k1,k2)≠1の例は、後で取り扱う。
第３行目の「Max rank of sub-groups: kq=280;」は、群位数の最大値がkq=280であることを示している。２次双曲線群の理論によればkq=LCM(k1,k2)≡[k1,k2]であり、kq=
[7,40]=280であるので、理論値と一致する。
【００６４】
第４行目以下には、本発明に係る拡張オイラー関数(GCD totient)Φm(x)の計算結果が示され、従来のオイラー関数(Euler’s totient)φとの比較が行なわれている。
例えば「φ(280)=96;Φ(280)=96;」とするのは、双方の値が一致することを示すが、この理由は(k1,k2)=1だからであり、(k1,k2)≠1の場合はこの様にならない。なお、次数m=2であるが、省略表示されている。
「Φ(280):=+280*1-140*1-56*1+28*1-40*1+20*1+8*1-4*1」の各項の係数は１であるので、
拡張オイラー関数の値はオイラー関数の値と一致する。これは、次のオイラー関数に係る級数公式と等価である。但し、μはメービウス関数である。
【数５】
・・・・（６―１）
【００６５】
後半の「Σφ(d|kq)=280;ΣΦ(d|kq)=280=1*kq;」という表示は、次のオイラー関数に係る公式
【数６】
・・・・（６―２）
を、実際に各項を計算して確認している。ここでも(k1,k2)=1の場合は、拡張オイラー関数の値はオイラー関数の値と一致する。
【００６６】
次の行の「Σ(-1)^(kq/d)Φ(d|kq)=0=-96+48+24-24-16+24+12+8+6+4-4+6+4+2+1+1」は拡張オイラー関数の計算式であるが、次のオイラー関数に関する公式
【数７】
・・・・（６―３）
に対応している。
【００６７】
次の行の「Presentation of the GCD Set」は、本発明に係る拡張オイラー関数の導出の過程で考慮される積集合(the GCD
Set)の要素(GCD component)hの計算値であり、ｍ次までの要素が全て計算されている。
【００６８】
図２４では、n=1035の場合に、その計算結果を全て明示した。
第１行目の「EHCG
modulo: n=1035=3^2*5^1*23^1」は、法ｎの素因数分解表示で、これにより実際に法ｎが合成数であることが示される。
第２行目の「GruopRank:
k=216=6*3*12」は、拡張２次双曲線群の群位数がk=216であることを示し、次の積表示は拡張形でない２次双曲線群の群位数k1,k2,k3との関係が示されている。法ｎの構成素因数p1=3,p2=5,p3=23から生成される２次双曲線群の群位数k1,k2,k3は、k=ph-1(p+1)/2であるので、k1=6,
k2=3, k2=12であり、ここではk=k1k2k3の関係が成立していることを確認できる。(k1,k2,k3)=3≠1であるので、群位数間に共通の素因数が存在する。なお、次数m=3であるが、省略表示されている。
第３行目の「Max
rank of sub-groups: kq=12;」は、群位数の最大値がkq=12であることを示している。２次双曲線群の理論によればkq=
[k1,k2,k3]=[6,3,12]=12であり、理論値と一致する。
【００６９】
第４行目以下には、本発明に係る拡張オイラー関数Φm(x)の計算結果が示され、従来のオイラー関数φとの比較が行なわれている。
例えば「φ(12)=4;Φ(12)=104;」とするのは、双方の値が一致しないことを示すが、この理由は
(k1,k2)≠1だからである。(k1,k2)≠1の場合、拡張オイラー関数Φm(x)の級数表示の各項における係数は１以上の整数になる。例えば、「Φ(12):=+12*18-6*18-4*2+2*2」では、それぞれの整数係数は18,18,2,2である。これは拡張オイラー関数Φm(x)の級数表示が
【数８】
・・・・（６―４）
と言う形になるからである。Fは倍率関数と呼んでいるが、F=1であれば(６―１)式と一致する。
【００７０】
後半の「Σφ(d|kq)=12;ΣΦ(d|kq)=216=18*kq;」という表示は、次の拡張オイラー関数に係る公式
【数９】
・・・・（６―５）
を、実際に各項を計算して確認している。
【００７１】
次の行の「Σ(-1)^(kq/d)Φ(d|kq)=0=-104+78-4+26+3+1」は、拡張オイラー関数に係る公式(証明は後出)
【数１０】
・・・・（６―６）
の計算値であり、理論との一致を確認することができる。
【００７２】
次の行の「Presentation of the GCD Set」は、本発明に係る拡張オイラー関数の導出の過程で考慮される積集合の要素hの計算値であり、ｍ次までの要素が全て計算されている。
【００７３】
図２２の「Graphics」ボタンは、拡張オイラー関数のグラフィックツールを起動する。これについての詳細を以下に説明する。
【００７４】
図２５は、拡張オイラー関数のグラフィックツールで、主に視覚上オイラー関数との差異を明らかにする。特に無限遠(n→∞)での拡張オイラー関数の漸近曲線等の研究道具として最適である。図２５の「X-mag」値及び「Y-mag」値は表示倍率の変更を可能にし、「Origin」値は原点の移動を可能にする。下段の「Reset」ボタンは、グラフ上に様々な書き込みを行ったものをクリアするときに使い、常に図２５の初期状態を回復する。
【００７５】
図２６は前記グラフィックツールで、「DispAll」ボタンを押したときの更新表示で、オイラー関数値(Green) φ(n)と拡張オイラー関数値(Cyan) Φm(n)の表示を行っている。双方の値が一致している場合には、色の濃さの違いからオイラー関数値(Green)だけが記載されているように見える。
【００７６】
図２７は、オイラー関数値と拡張オイラー関数値の比(Ratio)の表示で、前記グラフィックツールで、「Ratio」ボタンを押したときの更新表示である。表示上、比(Ratio)は黒点で示されている。拡張オイラー関数値Φm(n)とオイラー関数値φ(n)との比は理論的にも整数で、割り切れると言うことが知れていて、その確認を行うことができる。また、当該比の平均値(AveRatio)が赤線で、Ｌｏｇ平均値(LogRatio)が青線で、それぞれ示されている。
関数値の表示等を行った後に、マーカ(marker)の書き込みをすることができる。
【００７７】
図２８は、ｎ値にn=550を指定し「Express」ボタンを押したときの図面であり、当該ｎ値に該当する場所に、当該ｎ値から派生する部分群の最大位数kqにつき、拡張オイラー関数値Φm(kq)を赤線で、オイラー関数値φ(kq)を青線で示した図である。欄外には、kq=30,
φ(kq)=8, Φ(kq)=32, Ratio=4と数値が示される。このマーカは、表示窓(pictureBox1)上でのマウスの左クリックでも表示することができる。
【００７８】
図２９は、関数表示機能の例示であり、前記マーカと同様の補助表示を与える。表示窓(pictureBox1)上でのマウスの右クリックで生じるコンテキストメニューでは、関数表示の一つを選択することができる。経験から、y=x^0.7以上の傾斜を有する関数は採用されず、y=Log(1+x)のような関数が幾つか選ばれた。図中、y=x^0.5の関数が青い点線で表示され、拡張オイラー関数値の増加傾向や、拡張オイラー関数の漸近形を知る手掛かりになる。
【００７９】
２次双曲線群の理論
ここからは、２次双曲線群の理論、特に本発明に係る拡張２次双曲線群の解析ツールで紹介されている上記拡張オイラー関数(GCD totient)についての説明をする。この理論は双曲線暗号の数学的な背景を強化するものである。
【００８０】
拡張オイラー関数の着想は、既に特開2009-223035号で開示されていた。 その関数形を推定する方法は、２次双曲線群の群計算を合成数である法ｎの下で行い、全ての部分群の群位数を計算し、計数すると言うものである。位数kgを与える共役部分群Q(x)の個数がΦ(kg)個であるとしたとき、既にＧＣＤ関数への依存性が見出されていた。例えば、法ｎがn=p1p2という２個の素因数の積であ表されたとき、当該素因数から派生する部分群の位数k1,k2につき、
【数１１】
・・・・（８―１）
と言う形をしていた。
【００８１】
理論の出発点は、幾つかの合理的な仮定に基づいている。法ｐの下ではオイラー関数と拡張オイラー関数は一致していた。従って、(６―２)式が成立する。この式が意味するところは、部分群(剰余群)で位数ｄ｜ｎを有するものの個数はφ(d)個であり、その総個数は群位数であるｎになることである。従って、拡張オイラー関数につき
【数１２】
・・・・（８―２）
が成立すると考えることは自然である(仮定１)。但し、ｋは拡張２次双曲線群の群位数で、kqは最大位数である。即ち、共役部分群で群位数ｄを有するものの個数をΦ(d)個としたとき、その総個数は群位数ｋになる。
【００８２】
ここで、可能な群位数ｄを最大位数kqの約数に限定している。前記文献でも指摘していたが、拡張２次双曲線群では群位数ｋと最大位数kq(<=k)とは、通常一致しない。群位数ｋは、当該拡張２次双曲線群が異なるｋ個の要素(P(x))を有すると言うことである。従って、全ての部分群の位数kgがその最大値kqを越えず、ｋ個の要素の一部集合に止まるということは有り得そうである。ｋ個の要素は何れも何処かの部分群の要素であるが、全部が纏まって入っている部分群は存在しない、そう言う状態である。
【００８３】
群位数ｋは、法ｎを構成する素因数piから派生する部分群位数kiの積として与えられる(仮定２)。
【数１３】
・・・・（８―３）
ここで値ｍは法ｎを構成する素因数piの個数である。数学的には、m=ν(n)と表示する。
この仮定には、法ｐがその巡回群を規定する、と言う基本的な考え方に立っている。従って、法ｎが合成数でも、値ｎを構成する各素因数が生成される巡回群を規定する、と考えることは自然である。この理解には状態数の考え方が有効である。各部分群はki個の状態を有するので、全体の状態数(組み合わせ)はその積で与えられる。
【００８４】
法pihが生成する２次双曲線群では、ki=pih-1(pi+1)/2である。ここで、素因数ｐからは剰余群Z/pZしか生成されないとする考え方は狭い。現に２次双曲線群が存在し、異なる位数を有する。従って、部分群位数kiの値を固定しないで考えることが、理論の拡張につながる。
【００８５】
最大位数kq(<=k)は、kq=[k1,,,km]で与えられる(仮定３)。一応仮定として扱うが、この仮定にはメービウス関数μとの関連で幾分の根拠がある。本来(８―２)式の級数和に対しては約数ｄ｜ｋを扱うべきであるが、係る約数ｄのうちkqよりも大きなものについては、kqが最小公倍数であるのでd=x*kqと言う形になり、ｘ値に内在する素因数ｐにつき必ずｄ値にはp2という平方数、若しくはそれ以上のべき乗数が内在する。従って、μ(d)=0である。これは最大位数kqを越える部分群が存在しないか、考慮する必要がないことを意味している。(８―２)式には直接的にメービウス関数μが明示されていないが、次のメービウス変換の公式からして、この考え方は正しいと思われる。変換公式に現れる約数ｄは双方の式で同一だからである。
【数１４】
・・・・（８―４）
【数１５】
・・・・（８―５）
【００８６】
次に、（８―２）式が成立する場合に、上記メービウス変換を利用して拡張オイラー関数を明示の形で求めることを考える。この過程は遠大であるので、最初に拡張オイラー関数導出の手順の概略を書いておく。
（１）群位数ｋを最大位数kqの関数として表示する。
[1]部分群位数kiを構成要素とする積集合(GCD set)を考え、同次ＧＣＤ積に係る「簡略化定理」を導く。
[2]同次ＧＣＤ積を組み合わせて１次ＬＣＭを構成する。積集合の要素hの公式と、高次ＬＣＭも解説する。
[3]約数d|kqに係る公式を導く。
（２）上記メービウス変換を利用して拡張オイラー関数を明示の形で求める。導出の後は、その一般化も行っておく。
【００８７】
さて、上記手順に従い以下に詳細な説明を行う。
最初は部分群位数kiを基本構成要素とする積集合(GCD
set)の導入である。この集合の対象は群位数ｋであり、部分群位数kiを基本構成要素とし、その演算には部分群位数ki間のＧＣＤ演算を使う。ＧＣＤ演算で区分された各領域ｈはこの積集合の構成要素(GCD
factor)であり、ＧＣＤ演算の次元に従って同一の次元を有する。法ｎの構成素因数がｍ個であれば、最大次数はｍ次である。ＧＣＤ演算の組み合わせは2m個あり、従ってこの積集合の要素数も2m個である。ＧＣＤ演算なので各要素間には共通の素因数を有する場合がある。即ち、一般に(ha,hb)≠1(a≠b)である。但し、a,bはｍ次までの添え字列である。
【００８８】
図３０には４次(m=4)の積集合を例示した。図３０で、横線領域は２次の同次要素ha,bだけを示すもので、互いに接点のみを有しmC2個が連結する。これは鎖(Chain)結合している。縦線領域は３次の同次要素ha,b,cだけを示すもので、互いに接点のみを有しmC3個が連結する。ここでa次の同次ＧＣＤ積
を
【数１６】
・・・・（８―６）
と定義する。組み合わせ記号とは添え字の並びが違うので区別できる。a個の添え字は同一の値を有しないので全ての組み合わせmCa個の積が取られる。
【００８９】
このとき添え字ｍ値を１個増やすとどうなるのか考えてみる。
添え字ｍが1個増えると、それは部分群位数km+1が追加されたことを意味し、全ての１の要素hi1-iaから次数が１次高い要素hi1-iam+1が1個生成され、同時に要素hi1-iaの内容は要素hi1-iam+1の分だけ減じる。図３１を参照して欲しい。即ち、部分群位数が1個追加されると、次数aの同次ＧＣＤ積はmCa個からm+1Ca個になり、積の個数が増える。全体では要素の個数は2m個から2m+1個へ増える。
全体で見ると次数a固定の同次ＧＣＤ積
から新たに1次高い同次ＧＣＤ積
【数１７】
・・・・（８―７）
が生成され、新たに生成された次数aの同次ＧＣＤ積は
だけである。ここで(i1,,,ia)はａ個の添え字の全ての組み合わせにつき積演算を行うという意味である。
【００９０】
(８―７)式から次数aの同次ＧＣＤ積
は
【数１８】
・・・・（８―８）
と表せる。即ち、
【数１９】
・・・・（８―９）
である。これは組み合わせ公式
【数２０】
を反映している。
【００９１】
ここで積集合のＬＣＭ演算、
【数２１】
について考える。図３１の上記位数km+1の積集合の追加で、平原(plain=各要素の単純積)を構成する領域は、追加前のＧＣＤ演算の姿を基準にすると
【数２２】
であり、新たに生成された１次高い要素
【数２３】
で割り切ることにより得られた。これを同次ＧＣＤ積の立場から見ると、全ての同次ＧＣＤの単純積なので、前記追加後1次高い同次ＧＣＤ積で割るとその重複が解消され、再び平原（各要素の単純積）が現れる。
【００９２】
同次ＧＣＤ積（８―６）式では全ての同次数のＧＣＤが単純積として現れているので、位数ｋの積集合の1次の同次ＧＣＤ積を
【数２４】
と考えたとき、
【数２５】
とすると１次同次ＧＣＤ積内の重複が解消される。
【００９３】
しかし、まだ２次同次ＧＣＤ積
内の重複が解消されていない。そこで、
【数２６】
とすれば２次鎖まで重複が解消され、最終的には整った形式
【数２７】
により全ての次数での重複が解消され、等号が成立する。
は１個でその重複はないからである。
【００９４】
上式はm値が奇数の場合で、m値が偶数の場合は
が分母側にくる。この関係から、
【数２８】
・・・・（８―１０）
が成立する。これは位数ｋとその最大位数kqの間の関係を明示する。
【００９５】
ここで前記同次ＧＣＤ積構造Emを以下のように定義する。
【数２９】
・・・・（８―１１）
【００９６】
このときEmとEm+1の関係を調べる。新たに位数km+1の積集合が追加された場合、上記同次ＧＣＤ積
から1次高い
が生成され(８―８)式のように
と表せたのであるから、ｍ値の偶奇の反転を考慮して
【数３０】
となる。
【００９７】
ここで
は新たに生成された最高次の同次ＧＣＤ積(１個)で、上記重複解消の対象とならない。従って、
【数３１】
である。
【００９８】
いまEmの形に合わせて同次ＧＣＤ積構造
【数３２】
・・・・（８―１２）
と置けば、
【数３３】
と表せる。
【００９９】
ここで(８―７)式より最高次の同次ＧＣＤ積(１個)につき
【数３４】
であるから
【数３５】
・・・・（８―１３）
である。これは位数ｋとその最大位数kqの間の関係を同次ＧＣＤ積構造Emの漸化式で表し得たことを意味する。
【０１００】
ここで
は新たに生成された２次の同次ＧＣＤ積で、
【数３６】
・・・・（８―１４）
であり、
と共に漸化式の一部である。
【０１０１】
下準備ができたので、次の「簡略化定理」を証明しておく。
‖定理８―１‖
のとき、約数
に対し
【数３７】
が成立する。
【０１０２】
‖証明‖
いま
として１次高い同次ＧＣＤ積を考える。位数km+1の積集合の追加で、d=km+1と仮定した場合である。実際には新たな位数の追加は無いが、従前の式をそのまま利用できる。従って、（８―１０）、（８―１１）式から
【数３８】
・・・・（８―１５）
である。然るに
であるから、
【数３９】
、かつ、(８―１３)式が成立する。従って、
【数４０】
であり、
【数４１】
・・・・（８―１６）
と求めることができる。
【０１０３】
ここでFmを変数d=km+1の関数として表示するためにFm+1を考える。（８―１２）式より
【数４２】
であるので、（８―７）式より
【数４３】
と求められる。
【０１０４】
実際には新たな位数の追加は無かったのであるから、
【数４４】
・・・・（８―１７）
である。最高次数は分子から分母へ、若しくはその逆になっている。
これは(８―１７)式のような複雑な式が、
の条件下では(８―１６)式のような簡単な関係と等価であることを示す。
‖q.e.d‖
【０１０５】
さて、１個のＧＣＤを集合要素ｈの積として表現することは容易い。積集合の或る領域がki1,ki2,,,kiaの共通要素であった場合、それは１個で
と表されるが、これは要素
を意味していない。各要素ｈは全てのＧＣＤ演算により分割された後の姿なので、その他の位数kjについてのＧＣＤ演算が行われて始めてその領域が確定する。
が要素
と一致するのはその他の位数kjについてのＧＣＤ演算で影響を受けない場合だけである。
【０１０６】
最初に
であったところに、新たにkj1を追加すると、
となり、以下同様に
と急速に増加する。
【０１０７】
一般的には、kjbまで追加すると
【数４５】
となる。右辺は全体で(b+1)項ある。例えば上式の最終項の積は変数j1j2...jb(1<=b<=m-a)の重複がない全ての組み合わせ
個の積につき取る意味であり、上式全体で
個の要素の積につき取られる。従って、全ての細分が行われると(b=m-a)、
個の要素の積につき、
【数４６】
・・・・（９―１）
と言う形になり、「ＧＣＤの要素表示」を得ることができた。
【０１０８】
これは要素
から派生する次数が＋１以上の全ての要素と積をとることを意味している。即ち、積集合において当該要素より次数の高い内側の要素だけに関係し、次数の低い外側の要素とは関係がない。このように１個のＧＣＤ値を要素の積として表現することは容易であるが、逆に１個の要素ｈをＧＣＤの積として表現すること、即ち(９―１)式の逆変換を行うことは容易ではない。
【０１０９】
さて、要素ｈの単純積の内最大のものがＬＣＭであることを考えると、或るＧＣＤを要素ｈの単純積で表すことは、高次(higher order)ＬＣＭという関係を意識させる。本来の最小公倍数[kj1,,,kjb]は１次最小公倍数であり、０次最小公倍数とは部分群位数kiそのものと考える。
【０１１０】
そこで、以下に高次ＬＣＭを考えてみる。
始めに、次数aが固定状態(fix)の次数a+bの同次ＧＣＤ積
の次数bに係る部分積を
【数４７】
・・・・（９―２）
と定義したとき、b個の添え字jbは同一の値を有しないのでbに係る全ての組み合わせ
個の積が取られる。但し、添え字列[i1,,,ia]は、表記された添え字が固定状態であることを意味し、ＬＣＭとは関係ない。
【０１１１】
ここで、（８―８）式と同様に新たにkm+1を追加すると
【数４８】
・・・・（９―３）
が成立し、
【数４９】
・・・・（９―４）
である。これは組み合わせ公式
【数５０】
を反映している。
【０１１２】
ここで積集合の複数次最小公倍数ついて考える。a次ＬＣＭ、
は１個の同次ＧＣＤ積
を対象にし、kjxの追加でもその高原(tableland)の高度(=次数)を維持する積集合をいう。
【０１１３】
さて、次数a+xの同次ＧＣＤ積
には１次高い同次ＧＣＤ積
が重複しており、その高原の高度を維持するにはその１次高い同次ＧＣＤ積
で割らなければならない。言わば、「高地を削って台地を作り出す」のである。
【０１１４】
【数５１】
により、新たに追加したkj1に係る同次ＧＣＤ積
の重複を除ける。但し、
【数５２】
である。
【０１１５】
しかし、
にもその重複が存在する。従って、
【数５３】
となり、最終的には
【数５４】
for(b=m-a)・・・・（９―５）
により等号が成立し、a次ＬＣＭの明示式を得た。但し、値bと値aとの偶奇は等しいものとした。偶奇が異なれば、最高次数の同次ＧＣＤ積
は分母側に来る。
【０１１６】
同次ＧＣＤ積
を対象にした部分最小公倍数
は、その重なりがないことから通常、次数aの全ての要素の単純積
に一致する。
は少なくとも1個の要素hi1...iaを含み、
に係る重なりが無い場合は
であって、値aより大きな次数の要素を含まないからである。
【０１１７】
【数５５】
・・・・（９―６）
この（９―６）式で固定添え字をなくしb→m とすれば、本来の１次ＬＣＭ、
に一致する。ここではa個の添え字が固定状態(fix)の場合を扱っているので、
【数５６】
であるから、（９―５）式より
【数５７】
for(b=m-a) ・・・・（９―７）
である。
【０１１８】
従って、変数aと変数mの偶奇が同じものと仮定した場合は、
【数５８】
・・・・（９―７）
である。変数aと変数mの偶奇が異なるものと仮定した場合は、
【数５９】
・・・・（９―８）
である。
(９―７)、(９―８)式により、要素ｈのＧＣＤ表示を得ることができた。予想されたように、a次以上のＧＣＤだけで構成される。
【０１１９】
ここで、図３２に、n=351509の拡張オイラー関数の計算結果を表示した。下部にある要素計算は、(９―７)、(９―８)式を用いている。計算結果を図面で表示したものが図３３である。そこでは、群位数kiを構成する要素ｈの全ての積が群位数ki自身を与える。
法ｎを構成する４個(m=4)の素因数17,23,29,31が生成する部分群の位数9,12,15,16に対し、例えばk1=9では、
【数６０】
であり、積集合の理論値と一致する。
【０１２０】
拡張オイラー関数導出の最終段階は、（８―４）、(８―５)式のメービウス変換を利用して拡張オイラー関数を明示の形で求めることである。その最初のステップは、定理８―１と同様に、(８―１７)式を分解し、約数ｄに依存する項とそうでない項に分別することである。
では、
【数６１】
・・・・（１０―１）
【数６２】
・・・・（１０―２）
としたとき、変数ｄをkiの１つと考えて
を右辺で展開すると、変数ｄに依存する積と依存しない積に分けることができ、
【数６３】
・・・・（１０―３）
となる。
【０１２１】
このとき定理８―１を利用すると、
【数６４】
・・・・（１０―４）
が導かれる。また、(１０―１)、(１０―２)式の比較から、
としたとき、
【数６５】
・・・・（１０―５）
が成立する。なお、（８―１２）式の
とこの
は一致する。
【０１２２】
従って（１０―４）式から、
【数６６】
・・・・（１０―６）
であり、群位数ｋをkqの関数として導くことができた。そこで（８―４）、(８―５)式のメービウス変換を利用できる体勢が整った。
【０１２３】
(８―５)式で
としたとき、
(１０―６)式と定理８―１とから
【数６７】
・・・・（１０―７）
であるが、ここでは（６―４）式との対応に注意したい。即ち、（８―１６）式は拡張オイラー関数の級数形であって、（６―４）式で倍率関数と呼んでいたものと等しい。
【０１２４】
次数ｍを入れた表現で、
【数６８】
・・・・（１０―８）
である。但し、m=ν(n)は法ｎが有する異なる素因数の個数である。(１０―８)式はＧＣＤ積を有し、本発明に係る拡張オイラー関数を「GCD
totient」と呼ぶ理由を明示している。
【０１２５】
次に、この（１０―８）式がkg|kqに対し正しいのか、数値的に検証する。
n=1001=7*11*13の場合、k1=4,k2=6,k3=7、従ってkq=84の拡張２次双曲線群では、
kg=84,42,28,21,14,12,7,6,4,3,2,1に対しΦ(kg)=48,36,24,12,18,8,6.6,4,2,3,1であった。(１０―８)式によれば、
【数６９】
となり、群計算から得た集計結果と一致した。
【０１２６】
(１０―６)式にメービウス変換(８―４)、(８―５)式を適用すると、
【数７０】
・・・・（１０―９）
であるが、(ki,kq)=kiであり、左辺は群位数ｋに等しい。再び(８―２)式(仮定１)に戻ってきた事から、これまでの過程で矛盾は発生していない。逆に言えば、(１０―９)式を出発点にしていれば、(１０―８)式に容易に到達できたわけである。
【０１２７】
ここで、kqではなく、(１０―９)式を次のように約数kg|kqに拡張できるのか考えたい。その出発点は（１０―９）式で
【数７１】
・・・・（１１―１）
が成立すると仮定することである。（１１―１）式は、kg=kq,kg=1で成立しているが、その中間で成立しているかは定かではない。
【０１２８】
しかし、(６―２)式からオイラー関数につき
【数７２】
が成立し、拡張オイラー関数では倍率関数Ｆを用いて
【数７３】
・・・・（１１―２）
が成立すると仮定すると、この倍率関数Ｆが(８―１２)式、(８―１７)式に対応すると考えれば、（８―１６）式、定理８―１より、
【数７４】
が自然に導かれる。従って、(１１―１)式成立の証明はないが、約数kg|kqに拡張するとき(１１―１)式成立に矛盾はない。
【０１２９】
‖定理１１−１‖kg=xy,
(x,y)=1としたとき、（１１―１）式がkg=x,kg=yで成立するとすれば、（１１―１）式はkg=xyでも成立する。
【０１３０】
‖証明‖ （１１―１）式から、(x,y)=1としたとき、
、かつ、
が成立する。
仮定により、
、
であるので、
が成立する。
‖q.e.d‖
【０１３１】
ＧＣＤおよび拡張オイラー関数の何れもが乗積的だからである。しかし、このことは(１１―１)式が証明されたことを意味していない。にもかかわらず、群計算の計数結果は(１１―１)式の成立を支持している。以下は数値計算の結果である。
EHCG modulo:
n=1001; Max rank of sub-groups: kq=84;
The number of
Q(x) with kg is total Φ(kg).
φ(84)=24;Φ(84)=48;Ratio=2;Φ(84):=+84*2-42*2-28*2+14*2-12*2+6*2+4*2-2*2
φ(42)=12;Φ(42)=36;Ratio=3;Φ(42):=+42*2-21*1-14*2+7*1-6*2+3*1+2*2-1*1
φ(28)=12;Φ(28)=24;Ratio=2;Φ(28):=+28*2-14*2-4*2+2*2
φ(21)=12;Φ(21)=12;Ratio=1;Φ(21):=+21*1-7*1-3*1+1*1
φ(14)=6;Φ(14)=18;Ratio=3;Φ(14):=+14*2-7*1-2*2+1*1
φ(12)=4;Φ(12)=8;Ratio=2;Φ(12):=+12*2-6*2-4*2+2*2
φ(7)=6;Φ(7)=6;Ratio=1;Φ(7):=+7*1-1*1
φ(6)=2;Φ(6)=6;Ratio=3;Φ(6):=+6*2-3*1-2*2+1*1
φ(4)=2;Φ(4)=4;Ratio=2;Φ(4):=+4*2-2*2
φ(3)=2;Φ(3)=2;Ratio=1;Φ(3):=+3*1-1*1
φ(2)=1;Φ(2)=3;Ratio=3;Φ(2):=+2*2-1*1
φ(1)=1;Φ(1)=1;Ratio=1;Φ(1):=+1*1
Σφ(d|kq)=84;ΣΦ(d|kq)=168=2*kq;
【０１３２】
そこで、当面は(１１―１)式を拡張オイラー関数の定義式にすべき、と考える。
【数７５】
・・・・（１１―３）
である。その証明はできていない。
【０１３３】
(１１―１)式の形式を維持して、更にkgから自然数ｘに拡張することもできる。
【数７６】
・・・・（１２―１）
但し、m=ν(n)であり、あくまで法ｎの下で定義される整数論的関数である。
【０１３４】
(１２―１)式から、メービウス変換により
【数７７】
・・・・（１２―２）
である。
【０１３５】
拡張オイラー関数Φ(x)は定義域が狭く、(１１―２)式ではkg|kqなるkg値のみしか定義されていない。無理に全自然数ｘで定義しようとすればx|~kqでは、ｘ値がp|~kqであるｐ値を素因数として有し、当該ｐ値に対し(１３―２)式よりΦ(p)=0であるので、定理１２―３よりやはりΦ(x)=0である。また、ｘ値が全てkqと共通する素因数のみで構成された場合、x>kq,(x,kq)=y≠1なるｘ値に対しては、ｙ値を構成する素因数pに付き、必ずp2等のべき乗値を含み、μ(x)=0である。これは最大位数kqを越える部分群が存在しないか、考慮する必要がないことを意味している。
これを容認すると、（１２―２）式のように約数kg|kqから自然数ｘに拡張できる。
【０１３６】
以下に、(１２―２)式で定義される拡張オイラー関数の性質について調べる。この結果は、本発明に係る拡張オイラー関数(GCD totient)が、基本的で、かつ、原始的(primitive)な関数であることが判明している。
最初に拡張オイラー関数が乗積的な(multiplicative)関数であることを示す。まずは、予備定理を証明しておく。
【０１３７】
素因数の積集合におけるＧＣＤには特別な性質が成立する。
‖予備定理１２−１‖素因数の積集合Ｓで(A,B)=1ならば、
【数７８】
が成立する。ただし、
である。
【０１３８】
‖証明‖ｘの１の素因数piにつき、それぞれ
、
、
であるが、(A,B)=1ならばeA 若しくはeBが0である。eA=0であれば、
、
であり、
が成立する。
同様にeB=0であれば、
が成立する。
従って、何れの場合でも
が成立する。
ｘの１の素因数piにつき与式が成立するので、ｘの他の素因数pjでその積pipjを考える。
そこでは(pi,pj)=1であるから、ＧＣＤの可換性により、同様の議論から
が成立し、結局、
が成立する。従って、他のｘの素因数についても同様に扱える。
例えば、
につき
であり、これは
を意味する。
‖q.e.d‖
【０１３９】
次にオイラー関数φが乗積的(multiplicative)であることを示しておく。
‖予備定理１２−２‖
ならば、
【数７９】
である。
【０１４０】
‖証明‖オイラー関数φの級数展開
【数８０】
において、
【数８１】
であるが、
としたとき、
、
、
より
であるので、メービウス関数の乗積的な性質から
【数８２】
・・・・[1] が成立する。
次に、
のときは総和の積はその組み合わせの積にわたる総和に等しいので、
【数８３】
・・・・[2]
が成立する。従って、
【数８４】
である。
‖q.e.d‖
【０１４１】
次に拡張オイラー関数Φが乗積的(multiplicative)であることを示す。
‖定理１２−３‖
ならば、
【数８５】
である。
【０１４２】
‖証明‖拡張オイラー関数Φの級数展開
において、
【数８６】
であるが、
としたとき、
、
、及び
より
、かつ、
であるので、上記[1]及び[2]が成立する。
更に、ＧＣＤの乗積的な性質から、
ならば、
【数８７】
・・・・[3]
が成立する(予備定理１２―１)。従って、
【数８８】
である。
‖q.e.d‖
ここでは、拡張オイラー関数Φの乗積的性質が部分群位数kiに依存していないことが重要である。即ち、拡張オイラー関数Φの乗積的性質は素因数から生成された群の性質に依存していない。
【０１４３】
オイラー関数についての公式が拡張オイラー関数でも成立するのか検討してみる。
例えば、（６―４）式で示した
と言う公式は以下のように拡張できる。
【０１４４】
‖定理１２−４‖
【数８９】
但し、k=Пki,
である。
【０１４５】
‖証明‖
kqが奇数なら、d|kqも奇数であり、かつ、kq/dも奇数である。
従って、
【数９０】
である。
kqが偶数なら、kq=2ekg,
d=2fdg; と置くと、kg/dgが奇数であることから、
【数９１】
であり、以下のように変数分離できる。
【数９２】
このうち後の[]は奇数約数に係る和で、最初の[]は、
【数９３】
である。但し、級数和の範囲
で１の素因数のみからか構成されるので、後出する定理(１３−１)により
【数９４】
である。従って、
【数９５】
である。
‖q.e.d‖
【０１４６】
次に数値例を示す。
（１）kqが奇数の例
EHCG modulo:
n=493=17^1*29^1
GruopRank:
k=135=9*15
Max rank of
sub-groups: kq=45;
Σ(-1)^(kq/d)Φ(d|kq)=-135=-72-32-18-4-8-1
（２）kqが偶数の例
EHCG modulo:
n=11339=17^1*23^1*29^1
GruopRank:
k=1620=9*12*15
Max rank of
sub-groups: kq=180;
Σ(-1)^(kq/d)Φ(d|kq)=0=-432+216-208+216-108+104-8+54+104-52+4+54+26+4-2+26+1+1
ここでは、kq=22*45であるので、e=2,kg=45である。
-Φ(180)+Φ(90)+Φ(45)=0;
より、Φ(45){-22+2+1}=0とも書き直せる。同様に
-Φ(60)+Φ(30)+Φ(15)=0;
-Φ(36)+Φ(18)+Φ(9)=0;-Φ(20)+Φ(10)+Φ(5)=0;
-Φ(12)+Φ(6)+Φ(3)=0; -Φ(4)+Φ(2)+Φ(1)=0; が成立している。
【０１４７】
次に、拡張オイラー関数(GCD totient)Φ(x)が特定の条件下でオイラー関数φ(x)に帰着することを示しておく。
‖定理１３−１‖合成数である法ｎから派生する部分群の位数kiにつき、互いに共通する素因数を有しない場合には、拡張オイラー関数Φ(x)はオイラー関数φ(x)に一致する。
即ち、
で部分群位数ki=ki(pi)、群位数k=Πki、最大位数kq=[k1,k2,,,km]である場合に、任意の添え字i,jにつき(ki,
kj)=1ならば、Φ(x)=φ(x)である。
【０１４８】
‖証明‖(ki,
kj)=1ならば、拡張オイラー関数
において、GCDの乗積的性質(予備定理１２―１)により
【数９６】
であるが、k=khkq、(x/d)|kqであるので、約数x/dは群位数kで割り切れる。よって、
【数９７】
である。そこで、
【数９８】
である。
‖q.e.d‖
【０１４９】
次に、拡張オイラー関数Φ(n)の積表示を検討する。オイラー関数については、
【数９９】
・・・・（１３―１）
という積表示があるが、拡張オイラー関数Φ(n)でもその積表示があれば有用である。
【０１５０】
最初にΦ(pe)を検討する。最初に(１２―１)式で、x=
peと置いてみる。値xが1個の素因数で構成されるので、メービウス関数μ(d)の定義から、xの約数のうちd=1,pの場合だけを検討すれば足りる。
【数１００】
・・・・（１３―２）
である。素因数の個数m=1であるので、上式より
Φ(pe)=φ(pe)=
pe-pe-1である。
素因数の個数m>1であれば、変数xの素因数pに係る指数eに等しいかより大きなeiに係るkiの個数α(>=0)につき
である。
従って、（１３―２）式より
【数１０１】
・・・・（１３―３）
若しくは
【数１０２】
・・・・（１３―４）
と求められる。それ故、一般にkiに依存するのでΦ(pe)の値が一意に定まることはない。
【０１５１】
ここで拡張オイラー関数Φ(x)とオイラー関数φ(x)の比(Ratio)を検討する。既に本発明に係るグラフィックツールにおいて、オイラー関数値と拡張オイラー関数値の比の表示で説明していたように、以下の定理が成立する。
‖定理１３−２‖拡張オイラー関数Φ(x)はオイラー関数φ(x)で割り切れる。
【０１５２】
‖証明‖
（１３―１）、（１３―２）、(１３―３)式より、x= peの場合、
【数１０３】
・・・（１３―５）
若しくは
【数１０４】
となり、α(>=1)で、拡張オイラー関数Φ(pe)はオイラー関数φ(pe)で割り切れることが分かる。然るに、kg=peであるとすれば、kg|kq
及びkq=[k1,…,km]であるので部分群位数kiの中に素因数pに関しei>=eであるようなものが必ずあり、α>=1である。
ｘを構成する他の素因数も同様である。
従って、(１３―５)式より、拡張オイラー関数Φ(x)はオイラー関数φ(x)で割り切れる。
‖q.e.d‖
【０１５３】
この議論ををもう少し説明しておく。kq=[k1,…,km]より、k1,…,kmの中で素因数pに関し最高次数eMaxを有するものkMがあり、その他の指数はこれより小さいか等しく、素因数pに関し割り切れる。従ってkqの素因数pに関する次数はeMaxである。然らばe<=eMaxであるから、少なくともei>=eであるようなkiが存在し、e<=ei<=eMaxである。従って、x=kg|kqである変数xにおいて、その各素因数pjでαj>=1であることから、xに係る素因数の個数m1=ν(x)に対しΣαj>=ν(x)である。なお、比の中には法ｎや位数kiに含まれない新たな素因数がΣpiから派生する。
【０１５４】
ここで数値例で検証する。
法n=11339,k1=9,k2=12,k3=15,kq=180の拡張２次双曲線群で、
kg=3とした場合、φ(3)=2及び（１３―２）式より
であるので、
比
である。(１３―７)式を使った場合、p=3,e=1,α=3であるので、
であり、理論計算と一致した。この素因数q=13は新たに派生した素因数である。
【０１５５】
法n=351509,k1=9,k2=12,k3=15,k4=16,kq=720の拡張２次双曲線群で
kg=180とした場合、φ(180)=48及び
Φ(180)=+180*36-90*18-60*36+30*18-36*36+18*18+12*36-6*18=2592,
Ratio=54である。
(１３―５)式を使った場合、kg=180=22*32*5,k1=32,k2=22*3,k3=3*5,k4=24であるから、
p1=2, e1=2,α1=2;
p2=3, e2=2,α2=1; p3=5, e3=1,α3=1; であり、
Φ(22)/φ(22)=
20+1(2+1)=6; Φ(32)/φ(32)= 32+0(1)=9;
Φ(5)/φ(5)= 50+0(1)=1;
従って、Φ(180)/φ(180)=6*9*1=54
であり、理論計算と一致した。同様に、kg=24, φ(24)=8及び
Φ(24)=+24*36-12*36-8*4+4*4=416,
Ratio=52である。
(１３―５)式を使った場合、kg=24=23*3,k1=32,k2=22*3,k3=3*5,k4=24であるから、
p1=2, e1=3,α1=1;
p2=3, e2=1,α2=3;であり、
Φ(23)/φ(23)=
22+0(1)=4; Φ(3)/φ(3)= 30+0(9+3+1)=13;
従って、Φ(24)/φ(24)=4*13=52であり、理論計算と一致した。
【０１５６】
（１３―４）式において、ｘを構成する素因数qは必ずしもｎを構成する素因数pと一致しないので、本来
と表現すべきである。しかし、ｎを構成する素因数piは部分群位数kiを与えるだけで拡張オイラー関数Φ(x)の表現上直接現れない。そこで、ここでは素因数ｑを用いた表現はしないことにする。従って、素因数piは全てk若しくはkiに係る素因数のみで、法ｎとの直接の関係は無い。（１３―４）式より
【数１０５】
・・・・（１３―６）
となって、拡張オイラー関数Φ(x)の積表示を得ることができた。但し、素因数ｐjに関しベキ数ejに等しいかより大きなベキ数eiを有するkiの個数αjにつきαj>=1である。
【０１５７】
後の議論のために、拡張オイラー関数Φ(x)とオイラー関数φ(x)の比(Ratio)を明示の形で求めておく。
【数１０６】
・・・・（１３―７）
である。また、次の表示も見易い。
【数１０７】
・・・・（１３―８）
である。但し、素因数ｐjに関しベキ数ejに等しいかより大きなベキ数eiを有するkiの個数αjにつきαj>=1である。
【０１５８】
定理１３−２から、直ちに次の定理が導かれる。
‖定理１３−３‖
(a,n)=1であるようなaにつき
【数１０８】
である。
【０１５９】
‖証明‖拡張オイラー関数Φ(x)は定義域が狭く、通常x|kqなるｘ値のみしか定義されていない。無理に全自然数で定義しようとすればx|~kqでは、(１３―２)式よりΦ(x)=0である。そこで、x|kqなるｘ値に対しては、（３−１３）式により
とおけば、
【数１０９】
であり、x|~kqなるｘ値に対しては、
【数１１０】
である。
‖q.e.d‖
【０１６０】
次に2次双曲線群から導かれた拡張オイラー関数Φ(x)を他の拡張オイラー関数と比べてみることにする。整数論の教科書によれば著名なものとしてジョルダンのオイラー関数(Jordan’s
totient) Jm(x)がある。変数ｘを構成する素因数pjにつき
【数１１１】
・・・・（１３―９）
である。これをΦ(x)の積表示（１３―６）式と比べてみれば、添え字ｍを追加して
【数１１２】
・・・・（１３―１０）
であるので、似ていることがわかる。
【０１６１】
‖定理１３−４‖拡張オイラー関数Φ(x)は、ki=k0(固定)とすれば、ジョルダンのオイラー関数Jm(x)に帰着する。
【０１６２】
‖証明‖
（１３―１０）式で、ki=k0(固定)とすれば、kq=LCM(k0,k0,,,k0)=k0, x|kqであるのでkqは変数ｘで割り切れる。また、変数αjは変数ｘに係る素因数ｐjに関しベキ数ejに等しいかより大きなベキ数eiを有する「kiの個数」であり従って、ki=k0(固定)とすればαjはmの倍数でαj=m
or 0である。 2次双曲線群ではαj>=1であった。従って、
【数１１３】
・・・（１３―１１）
である。（１３―１１）式は2次双曲線群から導かれた拡張オイラー関数Φ(x)が、特定の条件下で、ｍ次のジョルダン・オイラー関数と一致することを示している。
‖q.e.d‖
【０１６３】
このことから、本発明に係る拡張オイラー関数(GCD totient)が、数ある拡張オイラー関数の中でも基本的で、かつ、原始的な関数であることがわかる。しかしながら、ki=k0(固定)とと言う条件は、異なる素因数から派生する部分群が全て同一の位数を有することを意味し、通常では有り得ない。この意味で、ジョルダン・オイラー関数は、その汎用性が失われている特殊関数である。
【産業上の利用可能性】
【０１６４】
以上のように、本発明に係る拡張オイラー関数等は未だ知られていないことが多く、研究段階の関数である。中でも拡張オイラー関数は拡張２次双曲線群の共役部分群の個数を規定する明確な意味があり、数学上も有用な関数と考えられる。そこで、本発明では拡張２次双曲線群解析ツールを設け、かつ、拡張オイラー関数のグラフィクスツールも付属させた。従って、この双曲線暗号の設計ツールが、双曲線暗号の初心者ばかりでなく、設計者、及び研究者に非常に有用である、と考えている。
【０１６５】
暗号の世界では、ＤＥＳ、ＲＳＡ暗号が依然有用と考えられているが、要求されるセキュリティのレベルも向上して、ビット数の増大で計算負担も増大し、暗号の簡単な利用ができない状況に至っている。双曲線暗号は、少ないビット数計算でも多ビット暗号と等価の計算困難性を容易に付加できるので、次世代の暗号として普及する可能性がある。
【図面の簡単な説明】
【０１６６】
【図１】２次双曲線設計ツールの全体図である。
【図２】素数テストツールでのn=1023のテスト結果である。
【図３】素数テストツールでのn=1031のテスト結果である。
【図４】素数テストツールでの篩法アルゴリズムのフロー図である。
【図５】素数テストツールでのGermann素数判定アルゴリズムのフロー図である。
【図６】素数テストツールでのn=1237のテスト結果である。
【図７】素数テストツールでの法ｐの採用方法を説明した図である。
【図３Ａ】設計ツールの上段部、曲線パラメータｃの採用を説明した図である。
【図９】設計ツールの上段部、曲線パラメータａの採用を説明した図である。
【図１０】設計ツールの中段部、曲線パラメータｄ及びｂの採用を説明した図である。
【図１１】設計ツールの下段部、データ保存を説明した図である。
【図１２】曲線パラメータのパラメータリストの全体図である。
【図１３】パラメータリストのショートカットメニューを説明した図である。
【図１４】ショートカットメニューの「ReCreateAllData」を実行したリスト図である。
【図１５】２次双曲線群解析ツールの全体図である。
【図１６】２次双曲線群解析ツールの解析集計アルゴリズムを示すフロー図である。
【図１７】２次双曲線群解析ツールの解析用曲線パラメータ等の確認を説明した図である。
【図１８】２次双曲線群解析ツールの解析結果を説明した図である。
【図１９】２次双曲線群解析ツールの集計結果を説明した図である。
【図２０】２次双曲線群解析ツールの詳細結果の表示を説明した図である。
【図２１】２次双曲線群解析ツールの詳細結果の表示、その２を説明した図である。
【図２２】拡張２次双曲線群解析ツールの指定した拡張２次双曲線群の計算結果を説明した図である。
【図２３】拡張２次双曲線群解析ツールの指定した拡張２次双曲線群の計算結果、その２を説明した図である。
【図２４】拡張２次双曲線群解析ツールの指定した拡張２次双曲線群の計算結果、その３を説明した図である。
【図２５】拡張２次双曲線群解析ツールに付属するグラフィックツールの全体図である。
【図２６】拡張オイラー関数のグラフィックツールにおけるオイラー関数値と拡張オイラー関数値の表示を説明した図である。
【図２７】拡張オイラー関数のグラフィックツールにおけるオイラー関数値と拡張オイラー関数値の比(Ratio)の表示を説明した図である。
【図２８】拡張オイラー関数のグラフィックツールにおけるマーカの書き込みを説明した図である。
【図２９】拡張オイラー関数のグラフィックツールにおける関数表示機能を説明した図である。
【図３０】４次の積集合を説明した図である。
【図３１】群位数の追加を説明した図である。
【図３２】拡張オイラー関数による群位数ｋの要素計算(n=351509) を説明した図である。
【図３３】群位数ｋの要素表示(n=351509,m=4) を説明した図である。
【符号の説明】
【０１６７】
【技術分野】
【０００１】
本発明は、拡張された２次双曲線群の離散対数を利用した双曲線暗号の設計ツール(ソフトウェア)及び鍵生成方法に関するものである。
【背景技術】
【０００２】
２００５年の７月に楕円曲線暗号に代わる双曲線暗号の探索において２次双曲線群が発見された後、その成果は２００７年２月特許出願された「二次双曲線群を使用する鍵生成方法、復号方法、署名検証方法、鍵ストリーム生成方法および装置」(特許文献１)に結び付けられた。その後２次双曲線群の研究が進み、法ｎが合成数である拡張２次双曲線群、特に法ｎが素数ｐのべき乗（pn）である場合に拡張され、拡張２次双曲線半群、拡張オイラー関数、逆元計算後回し法、２次双曲線群を用いた素因数分解の方法等の成果が２００８年３月の特許出願「双曲線暗号の鍵生成方法」(特許文献２)に開示されるに至った。
【特許文献１】特開2008-203548号
【特許文献２】特開2009-223035号
【０００３】
楕円曲線暗号で使用される楕円曲線関数は３次関数であり、双曲線暗号で使用される２次双曲線関数は整数論的関数ではあるが実質的には３次関数であるので、楕円関数を限定すれば双曲線関数と等価になる。どの様な数学的な条件下で等価になるかはまだ明らかではないが、双曲線暗号に近い形で楕円曲線暗号を形成することは可能だろう。更に、前記特許文献で案出した同値対や拡張２次双曲線半群等の概念が類似の形態で出現する可能性は高い。しかし、２次双曲線群は具体的に種々の条件が特定されているので、より明確な結果が出現すると予想される。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
２次双曲線群はその位数が一定で初等的取り扱い方が可能であることから、その理解に困難な点はないが、その全体像が複雑であることは否めない。特に２次曲線の判別式Ｄ及び当該２次曲線自体が平方非剰余であること等の制限から、複数の単位暗号化装置を具備する鍵生成装置において多数の曲線パラメータの組を特定する作業が必要になる。例えば、
【数１】
・・・・（１―１）
という整数論的関数で、法ｐ及び曲線パラメータa,b,cを定めなければならない。
従って、これ等の曲線パラメータ等を簡易に生成できるツール(ソフトウェア)があれば大変に便利である。また、双曲線暗号はまだ開発が始まったばかりであり、初心者が簡易に２次双曲線群を構成でき、かつ、その解析ができれば、その理解を助け、双曲線暗号の普及に拍車が係るに違いない。
【０００５】
曲線パラメータ特定作業を簡易に生成できるツールとはどの様なものだろうか。双曲線暗号を全く知らない者がその曲線パラメータを特定するとき、その選択肢を行使でき、色々と試してみる自由度を有していなければならないだろう。そもそも法ｐの特定はどうすべきだろうか。選択した法ｎが素数なのか合成数なのかも知らなければならない。当該２次双曲線群の最大位数kqを得るためには、ベースポイントP(x)の選択にも配慮しなければならない。選択し特定した２次双曲線群の下で双曲線暗号を構成したとき、その２次双曲線群がその利用に適したものか否かを判定するためには、初心者でも容易に解析でき、かつ、その結果を表示できるツールにしておきたい。
【０００６】
作成した２次双曲線群を具体的に利用するためにはファイル構成を採用することが望ましい。他のアプリケーションソフトウェアでの簡便な利用が可能になる。
【課題を解決するための手段】
【０００７】
本発明に係る双曲線暗号の設計ツール(HCC Design Tools)は複合ツールであり、素数テストツール(Prime Test Tool)、２次双曲線群設計ツール(HCG
Design tool)、２次双曲線群解析ツール(HCG Analysis tool)、拡張２次双曲線群解析ツール(Extended HCG Analysis
tool)等から構成されており、このツールだけで設計と解析が完結する構成を有している。
【０００８】
素数テストツールは法ｎが素数か否か判定し、素数ｐをその後利用するときはその採択を決定できる構成を有している。Germann素数判定機能、素因数分解表示機能はこの素数テストツールの特徴になっている。
【０００９】
２次双曲線群設計ツールでは、曲線パラメータの選択窓を有し、諸条件を満たす曲線パラメータ値が提示される。設計者はその中から任意に曲線パラメータを選択でき、かつ、新たな曲線パラメータへの更新も行うことができる。選択された曲線パラメータは、その旨の表示が行われる。特定の２次双曲線群に対応する採用された曲線パラメータの組は、保持され容易にその表示を行うことができ、かつ、必要な装置分だけ保存することができる。この組の一覧は、グリッドビュウ(Grid View)においてリスト化し、編集できる機能を有している。
【００１０】
２次双曲線群解析ツールでは、確認された曲線パラメータで特定された２次双曲線群の解析及び集計が行われ、その部分群の全体が明らかにされる。位数kgを有する共役部分群の個数、ベースポイントP(x)、及び当該部分群の構成要素の表示はこの解析ツールの特徴に成っている。設計者は特定された２次双曲線群の全体像、及び構成を知り、その採否を決定する材料にすることができる。
【００１１】
拡張２次双曲線群解析ツールは、拡張２次双曲線群の解析、特に法ｎが合成数である場合の拡張オイラー関数(GCD totient)の解析を行うことができる。拡張オイラー関数は、発明者により新たに発見された整数論的関数で、この特許明細書でその詳細が明らかにされる。しかし、このツールでは設計ツールとして、その項別級数表示、要素(GCD
set)解析等を行って、その結果を表示するにとまっている。ただ、拡張オイラー関数のグラフィクスツール(Graphics tool)も用意し、研究者等の利用の便宜を図った。
【発明の効果】
【００１２】
本発明に係る双曲線暗号の設計ツールは、複合ツールで設計と解析が完結する構成を有し設計者に使い易くなっている。各ツールの固有な構成からは以下の効果を奏する。
【００１３】
素数テストツールは本発明に係る設計ツールで採用される法ｐを選択する機能を有しており、単なるテストだけを行うものではない。そのGermann素数判定機能は、選択した２次双曲線群の位数が法ｐの下でも素数であることを保証する。これは任意にベースポイントを採択する自由を設計者に提供する効果を奏する。従って、設計者が係る法ｐを採用する手助けになる。素因数分解表示機能は、言うまでも無く法ｎが合成数でどの様な素因数から構成されるかを簡明に知らしめる。
【００１４】
２次双曲線群設計ツールの曲線パラメータの選択窓は、諸条件を満たす曲線パラメータの候補を提示し、その選択を設計者に委ねる効果を有する。提示されるパラメータ値は何度でも更新することができるので、設計者は小さ過ぎるパラメータ値若しくは法ｐに近いパラメータ値を避け、適当な大きさの値を選択できる。特定の２次双曲線群に対応する採用された曲線パラメータの組は、ソフトウェア内で保持され、容易にその表示を行うことができ、かつ、必要な装置分だけ保存することができると共に、何時でも更新することができる。特に、グリッドビュウによりリスト化し、編集できる機能を有しているので、簡易に必要な数の組を揃えるのに便宜である。
【００１５】
２次双曲線群解析ツールでは、曲線パラメータで特定された２次双曲線群の解析及び集計が行われ、その部分群の全体が明らかにされることから、設計者は採用した曲線パラメータの組が適当な群構成を有していることを確認でき、特に群位数が合成数kgである場合に当該群位数の約数を位数とする部分群の確認を行うことができる。法ｎがGermann素数で、その群位数が素数である場合には、ゼロ元を除く全てのベースポイントが最大位数kgであることを確認することができる。
【００１６】
拡張２次双曲線群解析ツールで取り扱う拡張オイラー関数Φは、拡張２次双曲線群の位数kg及びその約数を位数とする共役部分群の個数を与える重要な意義があり、位数kgを有する部分群の個数はΦ(kg)個である。ここで共役とは位数kgが同一で同型である部分群間の関係を言う。その項別級数表示は、従来のオイラー関数との対比を明示するもので、その拡張性を明示する表示方法である。積集合の要素表示は、ＧＣＤ演算と部分群位数kiの積を集合(積集合)と捉えた場合の１要素を与えるもので、位数ｋ(k=Πki)の構造を明らかにする。従って、要素表示の具体的計算は位数ｋの構造そのものを明らかにする。
【００１７】
拡張オイラー関数のグラフィクスツールは、拡張オイラー関数Φを具体的に計算しグラフ表示するものであり、従来のオイラー関数φとの差異を視覚的に明示する効果を奏する。
【発明を実施するための最良の形態】
【００１８】
以下、本発明に係る種々の実施例について説明する。
【００１９】
＜第１実施例＞
図１は、本発明の２次双曲線群設計ツール(ソフトウェア)の全体図であり、素数テストツール、２次双曲線群設計ツール、２次双曲線群解析ツール、及び拡張２次双曲線群解析ツール等から構成されている。このように各ツールを１個のソフトウェアに統合し、かつ、フロントに並べたので、設計者にとって使い回しの良いツールとして利用することができる。設計者は、図１左上の素数テストツールで法ｐを決めた後に、図１右の２次双曲線群設計ツールで曲線パラメータの各組を採用し、図１左中の２次双曲線群解析ツールで採用した２次双曲線群の適否を確認し、採用した各２次双曲線群をファイルの形で保存することができる。
【００２０】
このソフトウェアの開発は、２００８年５月にマイクロソフト社の「Visual Studio 2008」を用いて、VC++で行われた。NET.Framework V3.5のWindows(登録商標)プログラムである。開発開始後、約半年の作業で原型が出来上がり、その後半年掛けてバグ抜きや改良が行われた。同時にデモンストレーション用のアプリケーションソフトウェアも開発されたが、本発明との直接の関連が薄いので別の機会に開示する予定である。ただ、このツールで採用された２次双曲線群のパラメータファイルが利用できる構成が採用されている。
【００２１】
図２は、本発明の素数テストツールであり、本発明に係る設計ツールで採用される法ｐを選択する機能を有しており、単なるテストだけを行うものではない。素数判定の方法には「篩（ふるい）法(sieve method)」を用いており、高級な方法は採用していない。その１の理由は本発明に係るツールが主にデモンストレーションを目的として開発され、法ｐが大きなビット数を有することは前提としていないことを挙げる。法ｐに大きな数値を選択した場合、その後の群演算に大きな負担となり、事実上群演算は困難になる。その第２の理由は、単純ループで割り算を行うのでＰＣによる高速演算に向いている、ことにある。
【００２２】
図３は、法ｎとしてn=1023をテストした結果を表示してある。この結果は、
「n=3^1*11^1*31^1」、「_1023 is not a prime」であるので、法ｎが合成数で素因数3,11,31の積であることを示す。次に図３において法ｎとしてn=1031をテストした結果を表示してある。この結果は、「n=1031^1」、「1031
is a prime」であるので、法ｎが素数であることを示す。テストは第１のテキストボックス(textBox1)にｎ値を入力し、テストボタン「Test」を押下することにより行われる。
【００２３】
篩法の具体的なアルゴリズムは図４に示されている。図４で、「Start」から開始し、最初に法ｎの候補値である数値を入力し、「Test」を押下すると、最初は小さな素因数(2,3,5,7)を割り数値ｋとした直接の割り算が行われる。素数密度の関係からも、ｎ値に小さな素因数が含まれる可能性が高いからである。
【００２４】
その余りが０であればその素因数を値ｎが有するので当該割り数値ｋを保存し、余りが０でなければその素因数を値ｎが有していない、と判定できる。
【００２５】
その素因数をｎ値が有していれば、新たなテスト値をn←n/kとして、残りの素因数を探し出すことになる。但し、素因数のべき乗の場合を考え、同一の素因数による割り算が繰り返され、割り切れない場合にのみ前記割り数値ｋの更新が行われる。割り数値ｋの値が候補値である値ｎの平方根(√n)を越えた場合には、１以外の如何なる素因数をも有していないので、当該ｎ値を素数と判定できる。
【００２６】
本発明に係る素因数分解表示の方法は、以下に示すように主に２通りあるが、実際には後者の方法が採用されている。
【００２７】
第１の方法は素因数分解が終了し、素因数の個数Ｉが判明した場合に、各素因数毎にテキスト列を増やしてゆく方法（テキスト増加法）である。例えば、法ｎとしてn=1023を選択したとき、最初に空文字列「String^myText=””」が定義された後に、各素因数毎に「myText=3^1」＞「myText=3^1*11^1」＞「myText=3^1*11^1*31^1」とテキストの長さを増やしてゆき、リスト(listBox1)への書き込みは一度に行う
「listBox1->Items->Add(myText)」。
【００２８】
第２の方法は、リスト内の当該行のデータ「myText=listBox1->Items[i]->ToString()」を読み取り、新たなデータを追加し「myText=ｍyText+”*”+p+”^”+a」(p:当該素因数、a:当該ベキ数)
、当該行を削除した後に追加後のデータを書き込む方法（書き込み行更新法）で、書き込みと削除は素因数の個数ＩにつきＩ回行われる。即ち、各素因数毎に当該行の表示が「n=3^1」＞「n=3^1*11^1」＞「n=3^1*11^1*31^1」と切り替わってゆく。この方法は既にある表示をそのまま生かす点で便利である。
【００２９】
図５は、本発明に係るGermann素数判定方法を開示したフロー図である。最初に試し数ｐを入力し、前記図４に示した篩法のアルゴリズムにより当該ｐ値が素数か否か判定し、その後q=(p+1)/2を計算した後、再び篩法のアルゴリズムにより当該ｑ値が素数か否か判定する。当該ｑ値が素数であれば、対応する素数ｐはGermann素数である。当該ｑ値が素数でなければ、対応する素数ｐはGermann素数ではない。
【００３０】
図６は、本発明に係るGermann素数判定機能を実行した図である。試し数n=1237を素数テストした結果素数と判明したので、当該行「1237 is a
prime.」を青く選択した後に「Judge」ボタンを押すと、Germann素数判定が行われる。
【００３１】
Germann素数とは、素数ｐに対し値q=(p+1)/2も素数であるような素数ｐを言う。このような素数の組はその存在密度は高くないが、無限に存在することが知られている。２次双曲線群では、法phの場合、その群位数kはk=ph-1(p+1)/2であるので、h=1の場合は法ｐがGermann素数であることは当該２次双曲線群で素数位数を獲得することを意味する。
【００３２】
そして、その群位数が素数である場合には、ゼロ元を除く全てのベースポイントが最大位数kを有する部分群であることが、理論上明らかになっている。即ち、この様な２次双曲線群では位数qを有するφ(q)=q-1個の部分群と位数１を有するゼロ元１個で構成される。従って、ゼロ元を避ければ、ベースポイントP(x)が最大位数を与えるか否かの判定をする必要がない。
【００３３】
図７は、法ｐが素数と判定された後に、その後の曲線パラメータの選定において当該法ｐを採用する方法を開示する。判定された素数を青く選択した後にラジオボタン(radio button)「Yes」をクリックすると、「p=1237 is adopted.」と表示されて、その後の法ｐの採用が確定する。
【００３４】
図８は、２次双曲線群設計ツールの上段部を示す。上部には２次双曲線方程式が画像(picutureBox1)として表示され、これから決定すべき曲線パラメータの配置を確認することができる。このソフトウェアでは最初に曲線パラメータｃを決定する構成にしたが、先に曲線パラメータｃを決定する構成にしても良い。何れにしても、判別式D/4=c2+4aが平方非剰余になるように双方を選択しなければならない。２次双曲線群の群位数kをk=(p+1)/2の関係に保つためである。
【００３５】
曲線パラメータｃ及びａでは何れの値も法ｐにおける剰余群(Z/pZ)に従うので、通常値ｐ以下の値を入力する。テキストボックス(textBox2)に直接入力しても良いし、「Generate‘c’」ボタンを押して乱数から採用しても良い。ただ、前記法ｐの指定が行われていない場合には、この選択はできないようになっている。曲線パラメータｃの採用は「Select‘c’」ボタンの押下により行われ、「c=1
is adopted.」のように表示される。
【００３６】
また、同時に、前記判別式の条件を満たす複数の曲線パラメータａ値４個がリストボックス(listBox2)に列挙される。曲線パラメータａの選択は乱数に基づいているので、「Select‘c’」ボタンの押下を再度行うと別の候補値４個が提示される。これは設計者が適当な選択をする便宜となる。図９のように、リストボックス内の１個の値を青く選択し、「Select‘a’」ボタンの押下を行うと、その採用と共に「a=311
is adopted.」のように表示される。
【００３７】
図１０は設計ツールの中段部で、曲線パラメータｂ値及びｄ値を定める。最初に「Renewal」ボタンを押下すると、曲線パラメータｂ及びｄの候補がリストボックス(liastBox3)内に表示される。この条件は(d2+cd-a),(b2+cb-a)が平方非剰余となることである。即ち、(x2+cx-a)
が平方非剰余となるようなｘ値を乱数の中から選び出し、リストアップする。
【００３８】
このうち、曲線パラメータｄはゼロ元P(d)≡Oを定めることに相当し、曲線パラメータｂは関数値のゼロ点であるが、必ずしもゼロ元とは関係がない。しかし、特殊な関係であるｂ＝ｄのような制約下でも、２次双曲線群の特性が損なわれることはない。「Select‘d’」ボタン若しくは「Select‘b’」ボタンを押すと、それぞれのパラメータ値の採用が決められ、「d=55
is adopted.」若しくは「b=189 is adopted.」のように表示される。
【００３９】
図１１は設計ツールの下段部で、曲線パラメータの組の保存を行う。保存スタックは２０段用意されており、２０組の各曲線パラメータを保存することができる。現スタック番号はテキストボックス(textBox3)に表示されており、この番号は「Num.Up」ボタンの押下で上昇し、「Num.Down」ボタンの押下で下降する。従って、素数テストツールで定めた法ｐ値、本設計ツールの上段で定めた曲線パラメータｃ値、ａ値、本設計ツールの中段で定めた曲線パラメータｄ値、ｂ値の組が、一体として当該スタック番号に記憶される。
【００４０】
曲線パラメータ等の設定が終了した時点で、「Import」ボタンを押すと、前記曲線パラメータ等が現に表示されているスタック番号に記憶され、仮に前データが存在した場合にも上書きが行われる。また、インポートされた曲線パラメータ等はリストボックス(listBox4)内に表示される。なお、現スタック番号の記憶内容がリストボックス内に表示されるので、「Num.Up」ボタン若しくは「Num.Down」ボタンの押下で、その表示も変化する。
【００４１】
「SetData」ボタンは解析のために現に表示されたデータを使うためのもので、その押下により、解析用の場所に当該曲線パラメータ等を複写する。橙色の「EditParam」ボタンは、選択された複数のパラメータの組をリストアップし、その一覧を表示する等ために使われる。これについては以下に詳しく解説する。
【００４２】
図１２は、本発明によるパラメータリスト(ParamList)であり、採用された曲線パラメータ等の一覧（右段）と共に、群計算の初期条件等を指定する領域（左段）を有している。このパラメータリストは、前記「EditParam」ボタンの押下により出現する。前記スタックは採用された曲線パラメータ等の記憶はできるが、その一覧には支障がある。そこで、本発明によるパラメータリストが採用され、その訂正等の便宜を図った他、併せて設計者が群計算の初期条件等を指定できるようにもした。このような初期条件は、前記アプリケーションソフトウェアへ提供され、利用されるもので、このツールとの直接の関係はない。
【００４３】
図１２右段のGridViewで作成されたパラメータリストは、本発明が曲線パラメータ等の生成ツールであることを配慮し、数多くのショートカットメニュー(Sort
Cut Menu)を有している。ショートカットメニューはリスト(gridView1)内で右クリックすると出現し、図１３のような内容を有している。パラメータリスト内の数値は自由に変更できるが、前記諸条件を満たす保証は一切ない。その変更は、「OK」ボタンを押すと、更新されて保存される。この更新は、前記スタックにおいても行われる。「Cancel」ボタンでは何の変更も反映されない。
【００４４】
図１３のショートカットメニューで、「ClearRowData」メニューは当該選択行のデータを全て０値にする。「RestoreRowData」メニューは、前記変更が行われた後にスッタクに記憶された元の値に戻したいときに使われる。「DeleteSelectedRow」メニューは、当該選択された行を削除し、新たに最終行(第２０行目)に１行追加する操作である。従って、当該行以下の既存のデータ行が１個ずつ繰り上がる。「CopySelectedRow」メニューは、当該選択された行のデータをコピーし、保存用のスタックに退避する。「PasteCopiedRow」メニューは、前記保存用スタックのデータを当該選択行に貼り付ける。「InsertNewdRow」メニューは、選択行の位置に新たに１行挿入する操作である。選択行以下の既存の行は１行ずつ繰り下がり、最終行は消滅する。
【００４５】
「ReCreateRowData」メニューは、自動設計ツールでもある。与えられた「Modulo p」値を法ｐとする曲線パラメータを、前記諸条件を満たすように、乱数を利用して自動生成する。従って、このメニューの利用のためには、予め適切な法ｐ値を当該選択行上に入力しておかなければならない。自動選択の後に当該行のデータを元に戻すには、「RestoreRowData」メニューを使うことができる。
【００４６】
図１４には、「ReCreateAllData」メニューを実行した後のリストが表示されている。「ReCreateAllData」メニューも自動設計ツールで、全ての行のデータを第１行目の「Modulo
p」値のもとで自動選択する。従って、このメニューの利用のためには、予め適切な法ｐ値を第１行目に入力しておかなければならない。自動生成で、偶然にパラメータ値の２個が同一値の場合は、当該後に生成されるデータにつき再度の自動生成が行われるが、通常同一値が出現することは稀である。
「SetDataToAnalyze」メニューは、前掲の「SetData」ボタンと同じ役割であり、当該選択行のデータを解析のために提供する。その実行は、当該選択行のデータを解析用の場所に複写する。
【００４７】
図１２左段の群計算の初期条件等を指定する領域は、このツールとの直接の関係はなく、アプリケーションソフトウェアのために提供されているが、一応の説明をする。「Initia Oop Cycles」項目は、群計算の暗号化開始設定を遮蔽するために必要な群計算の回数を指定する。秘密鍵との連携が取られる。「KeyMargin」項目は、群演算の最低演算回数を指定するもので、これも秘匿性の向上のためである。「InitialWorkingKey」項目は、複数の暗号化装置が連帯して作動するときの初期値を与える。
【００４８】
「InitialBP(x)」項目は、ベースポイントを与えるｘ値を選択する項目で、x値は任意に入力できるが、所定の要件を満たさなければならないことから、そのテストが行われる。選択行の曲線パラメータ等の下でそのベースポイントが有効か否かは、「BP
Test」ボタンの押下で判定され、その結果が表示される。「EncryptMethod」項目は、その暗号化方式の選択のために使われる。
【００４９】
図１５は、本発明に係る２次双曲線群解析ツールの全体図であり、与えられた曲線パラメータ等の下での２次双曲線群の構造を明らかにする。
【００５０】
図１６は、本発明に係る解析集計アルゴリズムを示したフロー図で、それぞれ上半部は解析プロセス、下半部を集計プロセスを開示する。
【００５１】
解析プロセスでは、ベースポイントと成り得る全てのｘ値が対象となり、そのベースポイントP(x)を出発点とする部分群Q(x)の位数kgが調べられる。最初にx=0の条件から始め、
【数２】
が平方非剰余であるかを調べる。具体的には、
【数３】
が計算され、その値が-1(平方非剰余)か+1(平方剰余)であるかを調べる。そのτ(x)値が平方非剰余であれば、そのベースポイントP(x)は当該２次双曲線群の元であり、当該ベースポイントP(x)を出発点とする部分群Q(x)の位数kgを調べる。
【００５２】
k=1から始め、kP(x)を計算し、その値がゼロ点Ｏ=P(d)に一致するかが調べられる。実際にはx=dであれば足りる。k=kgのとき、kgP(x)=Ｏであれば、そのkg値が当該部分群Q(x)の位数になる。計算された群位数は、当該ｘ値と共にテキストファイルに出力される。その後の集計プロセスの便宜のためである。x値は剰余群Z/pZのもとで定義されているのでｐ個の値が可能である。２次双曲線群の理論によれば、平方非剰余を与えるｘ値の数は法ｐの下では最大(p+1)/2個で、当該２次双曲線群の元の数、位数ｋに一致する。即ち、
【数４】
である。
【００５３】
前記解析プロセスの終了後、集計プロセスを始める。最初にファイルの先頭から１行ずつ読み出し、当該計算された位数kgを読み取り、既に同一のkg値が存在する場合にはその値の計数個数を＋１する。同一のkg値が存在しない場合には当該kg値の欄を新たに設け、その計数個数を１個とする。この方法により最後の行を処理した後、群位数kgの大きさの順番に並べ替える。表示リストには、存在したkg値の異なる値の数の分だけ大きさの順に項別表示する。
【００５４】
図１７は、解析で用いる曲線パラメータ値等の確認を行っている。「ConfirmSet」ボタンを押すと、前記「SetData」ボタン等で指定した曲線パラメータ値等の確認を、リスト(listBox5)内の表示により行うことができる。
この例では「p=1031,a=244,b=167,c=1,d=145」と表示されている。
【００５５】
図１８は、解析実行のために「Analyze」ボタンを押したときの、その実行結果を表示している。その解析プロセスは図１５上段に示されている。実行結果は、ファイルにも出力されるが、リストにも表示することにした。例えば、「Q(1);
kg=129;」とあるのは、ベースポイントP(1)を始点として群演算を開始したとき、129P(1)に至ったとき始めてゼロ元Ｏと一致したことを意味する。従って、このベースポイントP(1)を有する部分群Q(1)の位数はkg=129と言うことになる。なお、法ｐの値が大きく、群演算の負担が大きいときには、プログレスバーでその実行の進行度を知ることができる。
【００５６】
リスト内には全ての実行結果が表示されているが、このままでは群構造全体の有効な情報を引き出すことはできない。そこで、「DataSum」ボタンを押して、データの集計、整理を自動的に行う。この集計は前記ファイルの検索により実行され、その集計プロセスは図１５下段に示されている。
【００５７】
例えば、「The number of Ｑ(x) with kg=516 is 168.」とあるのは、この２次双曲線群で位数kgを有する部分群Ｑ(x)でkg=516であるものの個数は、全部で１６８個であることを意味する。リスト上部には、「rank
k=516」と表示され、発見された部分群位数のうち最大のものを表示している。これは２次双曲線群の群位数ｋが５１６であることを示している。２次双曲線群の理論によれば、位数kgを有する共役部分群Ｑ(x)の個数は、法ｐが素数であるときφ(kg)個であるので、φ(516)=168により、その理論の確認をすることができる。しかし、ここでは理論と関係なく、群演算のみが実行されその結果が表示されている、と言う点に注意しなければならない。理論は現象を説明するために後から付けた理屈に過ぎない。
【００５８】
設計者は、図１９のリスト内の１行を青く選択した後に「Precisely」ボタンを押すと、その集計結果の詳細を知ることができる。図２０は、その様な詳細結果の一例で、図１９のリスト内の第２行目選択した場合の結果である。群位数kg=258を与える共役部分群Q(x)の個数は８４個あり、それ等の一覧が昇順に「Q(16);Q(17);Q(31);Q(43);・・・」のように表示されている。
【００５９】
ここでは、更に各部分群の詳細な構成を表示することができる。図２１は、その様な詳細結果の一例で、図２０に示された部分群Q(16)の詳細な構造を示してある。この表示は、図２０の該当部分群を青く選択した後、再び「Precisely」ボタンを押すとその表示をすることができる。
「1P=(16,326),2P=(397,609),3P=(683,901),4P=(865,372),5P=(723,335),・・・」と表示されたのは部分群Q(16)の２５８個の各元に対応する。各数値は、例えば1P=P(16)、2P=
P(16)+P(16)の意味である。
【００６０】
演算結果の取得には、リストボックス内で右クリックしたときに現れるショートカットメニューを利用することができる。「Copy」、「Paste」、及び「SellectAll」のように、複写、貼り付け、及び全選択のメニューを用意した。
【００６１】
図６は、本発明に係る拡張２次双曲線群の解析ツールである。拡張２次双曲線群では、法ｎは合成数で、法が素数の場合に比べてかなり複雑な構造を有する。実際この数年間で理論的な究明が進んで、かなりの事実が明らかになっている。しかし、未だ明らかでなく、数値計算のみの手探りの分野も少なくない。このツールを提供する目的は、主に研究・開発の用途である。
【００６２】
設計者が、法ｎの候補と考える数値をテキストボックス(textBox4)に入力し、「CalcEHCG」ボタンを押下すると、図２２に示すように、リストボックス(listBox6)内に種々の計算結果が表示される。何を計算したのかは、順次説明することにする。
【００６３】
図２３では、n=1027の場合に、その計算結果を全て明示した。
第１行目の「EHCG
modulo: n=1027=13^1*79^1」は、法ｎの素因数分解表示で、これにより実際に法ｎが合成数であることが示される。
第２行目の「GruopRank:
k=280=7*40」は、拡張２次双曲線群の群位数がk=280であることを示し、次の積表示は拡張形でない２次双曲線群の群位数k1,k2との関係が示されている。法ｎの構成素因数p1=13,p2=79から生成される２次双曲線群の群位数k1,k2は、k1=(p1+1)/2=7,
k2=(p2+1)/2=40であり、ここではk=k1k2の関係が成立していることを確認できる。GCD(k1,k2)≡(k1,k2)=1だからである。(k1,k2)≠1の例は、後で取り扱う。
第３行目の「Max rank of sub-groups: kq=280;」は、群位数の最大値がkq=280であることを示している。２次双曲線群の理論によればkq=LCM(k1,k2)≡[k1,k2]であり、kq=
[7,40]=280であるので、理論値と一致する。
【００６４】
第４行目以下には、本発明に係る拡張オイラー関数(GCD totient)Φm(x)の計算結果が示され、従来のオイラー関数(Euler’s totient)φとの比較が行なわれている。
例えば「φ(280)=96;Φ(280)=96;」とするのは、双方の値が一致することを示すが、この理由は(k1,k2)=1だからであり、(k1,k2)≠1の場合はこの様にならない。なお、次数m=2であるが、省略表示されている。
「Φ(280):=+280*1-140*1-56*1+28*1-40*1+20*1+8*1-4*1」の各項の係数は１であるので、
拡張オイラー関数の値はオイラー関数の値と一致する。これは、次のオイラー関数に係る級数公式と等価である。但し、μはメービウス関数である。
【数５】
・・・・（６―１）
【００６５】
後半の「Σφ(d|kq)=280;ΣΦ(d|kq)=280=1*kq;」という表示は、次のオイラー関数に係る公式
【数６】
・・・・（６―２）
を、実際に各項を計算して確認している。ここでも(k1,k2)=1の場合は、拡張オイラー関数の値はオイラー関数の値と一致する。
【００６６】
次の行の「Σ(-1)^(kq/d)Φ(d|kq)=0=-96+48+24-24-16+24+12+8+6+4-4+6+4+2+1+1」は拡張オイラー関数の計算式であるが、次のオイラー関数に関する公式
【数７】
・・・・（６―３）
に対応している。
【００６７】
次の行の「Presentation of the GCD Set」は、本発明に係る拡張オイラー関数の導出の過程で考慮される積集合(the GCD
Set)の要素(GCD component)hの計算値であり、ｍ次までの要素が全て計算されている。
【００６８】
図２４では、n=1035の場合に、その計算結果を全て明示した。
第１行目の「EHCG
modulo: n=1035=3^2*5^1*23^1」は、法ｎの素因数分解表示で、これにより実際に法ｎが合成数であることが示される。
第２行目の「GruopRank:
k=216=6*3*12」は、拡張２次双曲線群の群位数がk=216であることを示し、次の積表示は拡張形でない２次双曲線群の群位数k1,k2,k3との関係が示されている。法ｎの構成素因数p1=3,p2=5,p3=23から生成される２次双曲線群の群位数k1,k2,k3は、k=ph-1(p+1)/2であるので、k1=6,
k2=3, k2=12であり、ここではk=k1k2k3の関係が成立していることを確認できる。(k1,k2,k3)=3≠1であるので、群位数間に共通の素因数が存在する。なお、次数m=3であるが、省略表示されている。
第３行目の「Max
rank of sub-groups: kq=12;」は、群位数の最大値がkq=12であることを示している。２次双曲線群の理論によればkq=
[k1,k2,k3]=[6,3,12]=12であり、理論値と一致する。
【００６９】
第４行目以下には、本発明に係る拡張オイラー関数Φm(x)の計算結果が示され、従来のオイラー関数φとの比較が行なわれている。
例えば「φ(12)=4;Φ(12)=104;」とするのは、双方の値が一致しないことを示すが、この理由は
(k1,k2)≠1だからである。(k1,k2)≠1の場合、拡張オイラー関数Φm(x)の級数表示の各項における係数は１以上の整数になる。例えば、「Φ(12):=+12*18-6*18-4*2+2*2」では、それぞれの整数係数は18,18,2,2である。これは拡張オイラー関数Φm(x)の級数表示が
【数８】
・・・・（６―４）
と言う形になるからである。Fは倍率関数と呼んでいるが、F=1であれば(６―１)式と一致する。
【００７０】
後半の「Σφ(d|kq)=12;ΣΦ(d|kq)=216=18*kq;」という表示は、次の拡張オイラー関数に係る公式
【数９】
・・・・（６―５）
を、実際に各項を計算して確認している。
【００７１】
次の行の「Σ(-1)^(kq/d)Φ(d|kq)=0=-104+78-4+26+3+1」は、拡張オイラー関数に係る公式(証明は後出)
【数１０】
・・・・（６―６）
の計算値であり、理論との一致を確認することができる。
【００７２】
次の行の「Presentation of the GCD Set」は、本発明に係る拡張オイラー関数の導出の過程で考慮される積集合の要素hの計算値であり、ｍ次までの要素が全て計算されている。
【００７３】
図２２の「Graphics」ボタンは、拡張オイラー関数のグラフィックツールを起動する。これについての詳細を以下に説明する。
【００７４】
図２５は、拡張オイラー関数のグラフィックツールで、主に視覚上オイラー関数との差異を明らかにする。特に無限遠(n→∞)での拡張オイラー関数の漸近曲線等の研究道具として最適である。図２５の「X-mag」値及び「Y-mag」値は表示倍率の変更を可能にし、「Origin」値は原点の移動を可能にする。下段の「Reset」ボタンは、グラフ上に様々な書き込みを行ったものをクリアするときに使い、常に図２５の初期状態を回復する。
【００７５】
図２６は前記グラフィックツールで、「DispAll」ボタンを押したときの更新表示で、オイラー関数値(Green) φ(n)と拡張オイラー関数値(Cyan) Φm(n)の表示を行っている。双方の値が一致している場合には、色の濃さの違いからオイラー関数値(Green)だけが記載されているように見える。
【００７６】
図２７は、オイラー関数値と拡張オイラー関数値の比(Ratio)の表示で、前記グラフィックツールで、「Ratio」ボタンを押したときの更新表示である。表示上、比(Ratio)は黒点で示されている。拡張オイラー関数値Φm(n)とオイラー関数値φ(n)との比は理論的にも整数で、割り切れると言うことが知れていて、その確認を行うことができる。また、当該比の平均値(AveRatio)が赤線で、Ｌｏｇ平均値(LogRatio)が青線で、それぞれ示されている。
関数値の表示等を行った後に、マーカ(marker)の書き込みをすることができる。
【００７７】
図２８は、ｎ値にn=550を指定し「Express」ボタンを押したときの図面であり、当該ｎ値に該当する場所に、当該ｎ値から派生する部分群の最大位数kqにつき、拡張オイラー関数値Φm(kq)を赤線で、オイラー関数値φ(kq)を青線で示した図である。欄外には、kq=30,
φ(kq)=8, Φ(kq)=32, Ratio=4と数値が示される。このマーカは、表示窓(pictureBox1)上でのマウスの左クリックでも表示することができる。
【００７８】
図２９は、関数表示機能の例示であり、前記マーカと同様の補助表示を与える。表示窓(pictureBox1)上でのマウスの右クリックで生じるコンテキストメニューでは、関数表示の一つを選択することができる。経験から、y=x^0.7以上の傾斜を有する関数は採用されず、y=Log(1+x)のような関数が幾つか選ばれた。図中、y=x^0.5の関数が青い点線で表示され、拡張オイラー関数値の増加傾向や、拡張オイラー関数の漸近形を知る手掛かりになる。
【００７９】
２次双曲線群の理論
ここからは、２次双曲線群の理論、特に本発明に係る拡張２次双曲線群の解析ツールで紹介されている上記拡張オイラー関数(GCD totient)についての説明をする。この理論は双曲線暗号の数学的な背景を強化するものである。
【００８０】
拡張オイラー関数の着想は、既に特開2009-223035号で開示されていた。 その関数形を推定する方法は、２次双曲線群の群計算を合成数である法ｎの下で行い、全ての部分群の群位数を計算し、計数すると言うものである。位数kgを与える共役部分群Q(x)の個数がΦ(kg)個であるとしたとき、既にＧＣＤ関数への依存性が見出されていた。例えば、法ｎがn=p1p2という２個の素因数の積であ表されたとき、当該素因数から派生する部分群の位数k1,k2につき、
【数１１】
・・・・（８―１）
と言う形をしていた。
【００８１】
理論の出発点は、幾つかの合理的な仮定に基づいている。法ｐの下ではオイラー関数と拡張オイラー関数は一致していた。従って、(６―２)式が成立する。この式が意味するところは、部分群(剰余群)で位数ｄ｜ｎを有するものの個数はφ(d)個であり、その総個数は群位数であるｎになることである。従って、拡張オイラー関数につき
【数１２】
・・・・（８―２）
が成立すると考えることは自然である(仮定１)。但し、ｋは拡張２次双曲線群の群位数で、kqは最大位数である。即ち、共役部分群で群位数ｄを有するものの個数をΦ(d)個としたとき、その総個数は群位数ｋになる。
【００８２】
ここで、可能な群位数ｄを最大位数kqの約数に限定している。前記文献でも指摘していたが、拡張２次双曲線群では群位数ｋと最大位数kq(<=k)とは、通常一致しない。群位数ｋは、当該拡張２次双曲線群が異なるｋ個の要素(P(x))を有すると言うことである。従って、全ての部分群の位数kgがその最大値kqを越えず、ｋ個の要素の一部集合に止まるということは有り得そうである。ｋ個の要素は何れも何処かの部分群の要素であるが、全部が纏まって入っている部分群は存在しない、そう言う状態である。
【００８３】
群位数ｋは、法ｎを構成する素因数piから派生する部分群位数kiの積として与えられる(仮定２)。
【数１３】
・・・・（８―３）
ここで値ｍは法ｎを構成する素因数piの個数である。数学的には、m=ν(n)と表示する。
この仮定には、法ｐがその巡回群を規定する、と言う基本的な考え方に立っている。従って、法ｎが合成数でも、値ｎを構成する各素因数が生成される巡回群を規定する、と考えることは自然である。この理解には状態数の考え方が有効である。各部分群はki個の状態を有するので、全体の状態数(組み合わせ)はその積で与えられる。
【００８４】
法pihが生成する２次双曲線群では、ki=pih-1(pi+1)/2である。ここで、素因数ｐからは剰余群Z/pZしか生成されないとする考え方は狭い。現に２次双曲線群が存在し、異なる位数を有する。従って、部分群位数kiの値を固定しないで考えることが、理論の拡張につながる。
【００８５】
最大位数kq(<=k)は、kq=[k1,,,km]で与えられる(仮定３)。一応仮定として扱うが、この仮定にはメービウス関数μとの関連で幾分の根拠がある。本来(８―２)式の級数和に対しては約数ｄ｜ｋを扱うべきであるが、係る約数ｄのうちkqよりも大きなものについては、kqが最小公倍数であるのでd=x*kqと言う形になり、ｘ値に内在する素因数ｐにつき必ずｄ値にはp2という平方数、若しくはそれ以上のべき乗数が内在する。従って、μ(d)=0である。これは最大位数kqを越える部分群が存在しないか、考慮する必要がないことを意味している。(８―２)式には直接的にメービウス関数μが明示されていないが、次のメービウス変換の公式からして、この考え方は正しいと思われる。変換公式に現れる約数ｄは双方の式で同一だからである。
【数１４】
・・・・（８―４）
【数１５】
・・・・（８―５）
【００８６】
次に、（８―２）式が成立する場合に、上記メービウス変換を利用して拡張オイラー関数を明示の形で求めることを考える。この過程は遠大であるので、最初に拡張オイラー関数導出の手順の概略を書いておく。
（１）群位数ｋを最大位数kqの関数として表示する。
[1]部分群位数kiを構成要素とする積集合(GCD set)を考え、同次ＧＣＤ積に係る「簡略化定理」を導く。
[2]同次ＧＣＤ積を組み合わせて１次ＬＣＭを構成する。積集合の要素hの公式と、高次ＬＣＭも解説する。
[3]約数d|kqに係る公式を導く。
（２）上記メービウス変換を利用して拡張オイラー関数を明示の形で求める。導出の後は、その一般化も行っておく。
【００８７】
さて、上記手順に従い以下に詳細な説明を行う。
最初は部分群位数kiを基本構成要素とする積集合(GCD
set)の導入である。この集合の対象は群位数ｋであり、部分群位数kiを基本構成要素とし、その演算には部分群位数ki間のＧＣＤ演算を使う。ＧＣＤ演算で区分された各領域ｈはこの積集合の構成要素(GCD
factor)であり、ＧＣＤ演算の次元に従って同一の次元を有する。法ｎの構成素因数がｍ個であれば、最大次数はｍ次である。ＧＣＤ演算の組み合わせは2m個あり、従ってこの積集合の要素数も2m個である。ＧＣＤ演算なので各要素間には共通の素因数を有する場合がある。即ち、一般に(ha,hb)≠1(a≠b)である。但し、a,bはｍ次までの添え字列である。
【００８８】
図３０には４次(m=4)の積集合を例示した。図３０で、横線領域は２次の同次要素ha,bだけを示すもので、互いに接点のみを有しmC2個が連結する。これは鎖(Chain)結合している。縦線領域は３次の同次要素ha,b,cだけを示すもので、互いに接点のみを有しmC3個が連結する。ここでa次の同次ＧＣＤ積
を
【数１６】
・・・・（８―６）
と定義する。組み合わせ記号とは添え字の並びが違うので区別できる。a個の添え字は同一の値を有しないので全ての組み合わせmCa個の積が取られる。
【００８９】
このとき添え字ｍ値を１個増やすとどうなるのか考えてみる。
添え字ｍが1個増えると、それは部分群位数km+1が追加されたことを意味し、全ての１の要素hi1-iaから次数が１次高い要素hi1-iam+1が1個生成され、同時に要素hi1-iaの内容は要素hi1-iam+1の分だけ減じる。図３１を参照して欲しい。即ち、部分群位数が1個追加されると、次数aの同次ＧＣＤ積はmCa個からm+1Ca個になり、積の個数が増える。全体では要素の個数は2m個から2m+1個へ増える。
全体で見ると次数a固定の同次ＧＣＤ積
から新たに1次高い同次ＧＣＤ積
【数１７】
・・・・（８―７）
が生成され、新たに生成された次数aの同次ＧＣＤ積は
だけである。ここで(i1,,,ia)はａ個の添え字の全ての組み合わせにつき積演算を行うという意味である。
【００９０】
(８―７)式から次数aの同次ＧＣＤ積
は
【数１８】
・・・・（８―８）
と表せる。即ち、
【数１９】
・・・・（８―９）
である。これは組み合わせ公式
【数２０】
を反映している。
【００９１】
ここで積集合のＬＣＭ演算、
【数２１】
について考える。図３１の上記位数km+1の積集合の追加で、平原(plain=各要素の単純積)を構成する領域は、追加前のＧＣＤ演算の姿を基準にすると
【数２２】
であり、新たに生成された１次高い要素
【数２３】
で割り切ることにより得られた。これを同次ＧＣＤ積の立場から見ると、全ての同次ＧＣＤの単純積なので、前記追加後1次高い同次ＧＣＤ積で割るとその重複が解消され、再び平原（各要素の単純積）が現れる。
【００９２】
同次ＧＣＤ積（８―６）式では全ての同次数のＧＣＤが単純積として現れているので、位数ｋの積集合の1次の同次ＧＣＤ積を
【数２４】
と考えたとき、
【数２５】
とすると１次同次ＧＣＤ積内の重複が解消される。
【００９３】
しかし、まだ２次同次ＧＣＤ積
内の重複が解消されていない。そこで、
【数２６】
とすれば２次鎖まで重複が解消され、最終的には整った形式
【数２７】
により全ての次数での重複が解消され、等号が成立する。
は１個でその重複はないからである。
【００９４】
上式はm値が奇数の場合で、m値が偶数の場合は
が分母側にくる。この関係から、
【数２８】
・・・・（８―１０）
が成立する。これは位数ｋとその最大位数kqの間の関係を明示する。
【００９５】
ここで前記同次ＧＣＤ積構造Emを以下のように定義する。
【数２９】
・・・・（８―１１）
【００９６】
このときEmとEm+1の関係を調べる。新たに位数km+1の積集合が追加された場合、上記同次ＧＣＤ積
から1次高い
が生成され(８―８)式のように
と表せたのであるから、ｍ値の偶奇の反転を考慮して
【数３０】
となる。
【００９７】
ここで
は新たに生成された最高次の同次ＧＣＤ積(１個)で、上記重複解消の対象とならない。従って、
【数３１】
である。
【００９８】
いまEmの形に合わせて同次ＧＣＤ積構造
【数３２】
・・・・（８―１２）
と置けば、
【数３３】
と表せる。
【００９９】
ここで(８―７)式より最高次の同次ＧＣＤ積(１個)につき
【数３４】
であるから
【数３５】
・・・・（８―１３）
である。これは位数ｋとその最大位数kqの間の関係を同次ＧＣＤ積構造Emの漸化式で表し得たことを意味する。
【０１００】
ここで
は新たに生成された２次の同次ＧＣＤ積で、
【数３６】
・・・・（８―１４）
であり、
と共に漸化式の一部である。
【０１０１】
下準備ができたので、次の「簡略化定理」を証明しておく。
‖定理８―１‖
のとき、約数
に対し
【数３７】
が成立する。
【０１０２】
‖証明‖
いま
として１次高い同次ＧＣＤ積を考える。位数km+1の積集合の追加で、d=km+1と仮定した場合である。実際には新たな位数の追加は無いが、従前の式をそのまま利用できる。従って、（８―１０）、（８―１１）式から
【数３８】
・・・・（８―１５）
である。然るに
であるから、
【数３９】
、かつ、(８―１３)式が成立する。従って、
【数４０】
であり、
【数４１】
・・・・（８―１６）
と求めることができる。
【０１０３】
ここでFmを変数d=km+1の関数として表示するためにFm+1を考える。（８―１２）式より
【数４２】
であるので、（８―７）式より
【数４３】
と求められる。
【０１０４】
実際には新たな位数の追加は無かったのであるから、
【数４４】
・・・・（８―１７）
である。最高次数は分子から分母へ、若しくはその逆になっている。
これは(８―１７)式のような複雑な式が、
の条件下では(８―１６)式のような簡単な関係と等価であることを示す。
‖q.e.d‖
【０１０５】
さて、１個のＧＣＤを集合要素ｈの積として表現することは容易い。積集合の或る領域がki1,ki2,,,kiaの共通要素であった場合、それは１個で
と表されるが、これは要素
を意味していない。各要素ｈは全てのＧＣＤ演算により分割された後の姿なので、その他の位数kjについてのＧＣＤ演算が行われて始めてその領域が確定する。
が要素
と一致するのはその他の位数kjについてのＧＣＤ演算で影響を受けない場合だけである。
【０１０６】
最初に
であったところに、新たにkj1を追加すると、
となり、以下同様に
と急速に増加する。
【０１０７】
一般的には、kjbまで追加すると
【数４５】
となる。右辺は全体で(b+1)項ある。例えば上式の最終項の積は変数j1j2...jb(1<=b<=m-a)の重複がない全ての組み合わせ
個の積につき取る意味であり、上式全体で
個の要素の積につき取られる。従って、全ての細分が行われると(b=m-a)、
個の要素の積につき、
【数４６】
・・・・（９―１）
と言う形になり、「ＧＣＤの要素表示」を得ることができた。
【０１０８】
これは要素
から派生する次数が＋１以上の全ての要素と積をとることを意味している。即ち、積集合において当該要素より次数の高い内側の要素だけに関係し、次数の低い外側の要素とは関係がない。このように１個のＧＣＤ値を要素の積として表現することは容易であるが、逆に１個の要素ｈをＧＣＤの積として表現すること、即ち(９―１)式の逆変換を行うことは容易ではない。
【０１０９】
さて、要素ｈの単純積の内最大のものがＬＣＭであることを考えると、或るＧＣＤを要素ｈの単純積で表すことは、高次(higher order)ＬＣＭという関係を意識させる。本来の最小公倍数[kj1,,,kjb]は１次最小公倍数であり、０次最小公倍数とは部分群位数kiそのものと考える。
【０１１０】
そこで、以下に高次ＬＣＭを考えてみる。
始めに、次数aが固定状態(fix)の次数a+bの同次ＧＣＤ積
の次数bに係る部分積を
【数４７】
・・・・（９―２）
と定義したとき、b個の添え字jbは同一の値を有しないのでbに係る全ての組み合わせ
個の積が取られる。但し、添え字列[i1,,,ia]は、表記された添え字が固定状態であることを意味し、ＬＣＭとは関係ない。
【０１１１】
ここで、（８―８）式と同様に新たにkm+1を追加すると
【数４８】
・・・・（９―３）
が成立し、
【数４９】
・・・・（９―４）
である。これは組み合わせ公式
【数５０】
を反映している。
【０１１２】
ここで積集合の複数次最小公倍数ついて考える。a次ＬＣＭ、
は１個の同次ＧＣＤ積
を対象にし、kjxの追加でもその高原(tableland)の高度(=次数)を維持する積集合をいう。
【０１１３】
さて、次数a+xの同次ＧＣＤ積
には１次高い同次ＧＣＤ積
が重複しており、その高原の高度を維持するにはその１次高い同次ＧＣＤ積
で割らなければならない。言わば、「高地を削って台地を作り出す」のである。
【０１１４】
【数５１】
により、新たに追加したkj1に係る同次ＧＣＤ積
の重複を除ける。但し、
【数５２】
である。
【０１１５】
しかし、
にもその重複が存在する。従って、
【数５３】
となり、最終的には
【数５４】
for(b=m-a)・・・・（９―５）
により等号が成立し、a次ＬＣＭの明示式を得た。但し、値bと値aとの偶奇は等しいものとした。偶奇が異なれば、最高次数の同次ＧＣＤ積
は分母側に来る。
【０１１６】
同次ＧＣＤ積
を対象にした部分最小公倍数
は、その重なりがないことから通常、次数aの全ての要素の単純積
に一致する。
は少なくとも1個の要素hi1...iaを含み、
に係る重なりが無い場合は
であって、値aより大きな次数の要素を含まないからである。
【０１１７】
【数５５】
・・・・（９―６）
この（９―６）式で固定添え字をなくしb→m とすれば、本来の１次ＬＣＭ、
に一致する。ここではa個の添え字が固定状態(fix)の場合を扱っているので、
【数５６】
であるから、（９―５）式より
【数５７】
for(b=m-a) ・・・・（９―７）
である。
【０１１８】
従って、変数aと変数mの偶奇が同じものと仮定した場合は、
【数５８】
・・・・（９―７）
である。変数aと変数mの偶奇が異なるものと仮定した場合は、
【数５９】
・・・・（９―８）
である。
(９―７)、(９―８)式により、要素ｈのＧＣＤ表示を得ることができた。予想されたように、a次以上のＧＣＤだけで構成される。
【０１１９】
ここで、図３２に、n=351509の拡張オイラー関数の計算結果を表示した。下部にある要素計算は、(９―７)、(９―８)式を用いている。計算結果を図面で表示したものが図３３である。そこでは、群位数kiを構成する要素ｈの全ての積が群位数ki自身を与える。
法ｎを構成する４個(m=4)の素因数17,23,29,31が生成する部分群の位数9,12,15,16に対し、例えばk1=9では、
【数６０】
であり、積集合の理論値と一致する。
【０１２０】
拡張オイラー関数導出の最終段階は、（８―４）、(８―５)式のメービウス変換を利用して拡張オイラー関数を明示の形で求めることである。その最初のステップは、定理８―１と同様に、(８―１７)式を分解し、約数ｄに依存する項とそうでない項に分別することである。
では、
【数６１】
・・・・（１０―１）
【数６２】
・・・・（１０―２）
としたとき、変数ｄをkiの１つと考えて
を右辺で展開すると、変数ｄに依存する積と依存しない積に分けることができ、
【数６３】
・・・・（１０―３）
となる。
【０１２１】
このとき定理８―１を利用すると、
【数６４】
・・・・（１０―４）
が導かれる。また、(１０―１)、(１０―２)式の比較から、
としたとき、
【数６５】
・・・・（１０―５）
が成立する。なお、（８―１２）式の
とこの
は一致する。
【０１２２】
従って（１０―４）式から、
【数６６】
・・・・（１０―６）
であり、群位数ｋをkqの関数として導くことができた。そこで（８―４）、(８―５)式のメービウス変換を利用できる体勢が整った。
【０１２３】
(８―５)式で
としたとき、
(１０―６)式と定理８―１とから
【数６７】
・・・・（１０―７）
であるが、ここでは（６―４）式との対応に注意したい。即ち、（８―１６）式は拡張オイラー関数の級数形であって、（６―４）式で倍率関数と呼んでいたものと等しい。
【０１２４】
次数ｍを入れた表現で、
【数６８】
・・・・（１０―８）
である。但し、m=ν(n)は法ｎが有する異なる素因数の個数である。(１０―８)式はＧＣＤ積を有し、本発明に係る拡張オイラー関数を「GCD
totient」と呼ぶ理由を明示している。
【０１２５】
次に、この（１０―８）式がkg|kqに対し正しいのか、数値的に検証する。
n=1001=7*11*13の場合、k1=4,k2=6,k3=7、従ってkq=84の拡張２次双曲線群では、
kg=84,42,28,21,14,12,7,6,4,3,2,1に対しΦ(kg)=48,36,24,12,18,8,6.6,4,2,3,1であった。(１０―８)式によれば、
【数６９】
となり、群計算から得た集計結果と一致した。
【０１２６】
(１０―６)式にメービウス変換(８―４)、(８―５)式を適用すると、
【数７０】
・・・・（１０―９）
であるが、(ki,kq)=kiであり、左辺は群位数ｋに等しい。再び(８―２)式(仮定１)に戻ってきた事から、これまでの過程で矛盾は発生していない。逆に言えば、(１０―９)式を出発点にしていれば、(１０―８)式に容易に到達できたわけである。
【０１２７】
ここで、kqではなく、(１０―９)式を次のように約数kg|kqに拡張できるのか考えたい。その出発点は（１０―９）式で
【数７１】
・・・・（１１―１）
が成立すると仮定することである。（１１―１）式は、kg=kq,kg=1で成立しているが、その中間で成立しているかは定かではない。
【０１２８】
しかし、(６―２)式からオイラー関数につき
【数７２】
が成立し、拡張オイラー関数では倍率関数Ｆを用いて
【数７３】
・・・・（１１―２）
が成立すると仮定すると、この倍率関数Ｆが(８―１２)式、(８―１７)式に対応すると考えれば、（８―１６）式、定理８―１より、
【数７４】
が自然に導かれる。従って、(１１―１)式成立の証明はないが、約数kg|kqに拡張するとき(１１―１)式成立に矛盾はない。
【０１２９】
‖定理１１−１‖kg=xy,
(x,y)=1としたとき、（１１―１）式がkg=x,kg=yで成立するとすれば、（１１―１）式はkg=xyでも成立する。
【０１３０】
‖証明‖ （１１―１）式から、(x,y)=1としたとき、
、かつ、
が成立する。
仮定により、
、
であるので、
が成立する。
‖q.e.d‖
【０１３１】
ＧＣＤおよび拡張オイラー関数の何れもが乗積的だからである。しかし、このことは(１１―１)式が証明されたことを意味していない。にもかかわらず、群計算の計数結果は(１１―１)式の成立を支持している。以下は数値計算の結果である。
EHCG modulo:
n=1001; Max rank of sub-groups: kq=84;
The number of
Q(x) with kg is total Φ(kg).
φ(84)=24;Φ(84)=48;Ratio=2;Φ(84):=+84*2-42*2-28*2+14*2-12*2+6*2+4*2-2*2
φ(42)=12;Φ(42)=36;Ratio=3;Φ(42):=+42*2-21*1-14*2+7*1-6*2+3*1+2*2-1*1
φ(28)=12;Φ(28)=24;Ratio=2;Φ(28):=+28*2-14*2-4*2+2*2
φ(21)=12;Φ(21)=12;Ratio=1;Φ(21):=+21*1-7*1-3*1+1*1
φ(14)=6;Φ(14)=18;Ratio=3;Φ(14):=+14*2-7*1-2*2+1*1
φ(12)=4;Φ(12)=8;Ratio=2;Φ(12):=+12*2-6*2-4*2+2*2
φ(7)=6;Φ(7)=6;Ratio=1;Φ(7):=+7*1-1*1
φ(6)=2;Φ(6)=6;Ratio=3;Φ(6):=+6*2-3*1-2*2+1*1
φ(4)=2;Φ(4)=4;Ratio=2;Φ(4):=+4*2-2*2
φ(3)=2;Φ(3)=2;Ratio=1;Φ(3):=+3*1-1*1
φ(2)=1;Φ(2)=3;Ratio=3;Φ(2):=+2*2-1*1
φ(1)=1;Φ(1)=1;Ratio=1;Φ(1):=+1*1
Σφ(d|kq)=84;ΣΦ(d|kq)=168=2*kq;
【０１３２】
そこで、当面は(１１―１)式を拡張オイラー関数の定義式にすべき、と考える。
【数７５】
・・・・（１１―３）
である。その証明はできていない。
【０１３３】
(１１―１)式の形式を維持して、更にkgから自然数ｘに拡張することもできる。
【数７６】
・・・・（１２―１）
但し、m=ν(n)であり、あくまで法ｎの下で定義される整数論的関数である。
【０１３４】
(１２―１)式から、メービウス変換により
【数７７】
・・・・（１２―２）
である。
【０１３５】
拡張オイラー関数Φ(x)は定義域が狭く、(１１―２)式ではkg|kqなるkg値のみしか定義されていない。無理に全自然数ｘで定義しようとすればx|~kqでは、ｘ値がp|~kqであるｐ値を素因数として有し、当該ｐ値に対し(１３―２)式よりΦ(p)=0であるので、定理１２―３よりやはりΦ(x)=0である。また、ｘ値が全てkqと共通する素因数のみで構成された場合、x>kq,(x,kq)=y≠1なるｘ値に対しては、ｙ値を構成する素因数pに付き、必ずp2等のべき乗値を含み、μ(x)=0である。これは最大位数kqを越える部分群が存在しないか、考慮する必要がないことを意味している。
これを容認すると、（１２―２）式のように約数kg|kqから自然数ｘに拡張できる。
【０１３６】
以下に、(１２―２)式で定義される拡張オイラー関数の性質について調べる。この結果は、本発明に係る拡張オイラー関数(GCD totient)が、基本的で、かつ、原始的(primitive)な関数であることが判明している。
最初に拡張オイラー関数が乗積的な(multiplicative)関数であることを示す。まずは、予備定理を証明しておく。
【０１３７】
素因数の積集合におけるＧＣＤには特別な性質が成立する。
‖予備定理１２−１‖素因数の積集合Ｓで(A,B)=1ならば、
【数７８】
が成立する。ただし、
である。
【０１３８】
‖証明‖ｘの１の素因数piにつき、それぞれ
、
、
であるが、(A,B)=1ならばeA 若しくはeBが0である。eA=0であれば、
、
であり、
が成立する。
同様にeB=0であれば、
が成立する。
従って、何れの場合でも
が成立する。
ｘの１の素因数piにつき与式が成立するので、ｘの他の素因数pjでその積pipjを考える。
そこでは(pi,pj)=1であるから、ＧＣＤの可換性により、同様の議論から
が成立し、結局、
が成立する。従って、他のｘの素因数についても同様に扱える。
例えば、
につき
であり、これは
を意味する。
‖q.e.d‖
【０１３９】
次にオイラー関数φが乗積的(multiplicative)であることを示しておく。
‖予備定理１２−２‖
ならば、
【数７９】
である。
【０１４０】
‖証明‖オイラー関数φの級数展開
【数８０】
において、
【数８１】
であるが、
としたとき、
、
、
より
であるので、メービウス関数の乗積的な性質から
【数８２】
・・・・[1] が成立する。
次に、
のときは総和の積はその組み合わせの積にわたる総和に等しいので、
【数８３】
・・・・[2]
が成立する。従って、
【数８４】
である。
‖q.e.d‖
【０１４１】
次に拡張オイラー関数Φが乗積的(multiplicative)であることを示す。
‖定理１２−３‖
ならば、
【数８５】
である。
【０１４２】
‖証明‖拡張オイラー関数Φの級数展開
において、
【数８６】
であるが、
としたとき、
、
、及び
より
、かつ、
であるので、上記[1]及び[2]が成立する。
更に、ＧＣＤの乗積的な性質から、
ならば、
【数８７】
・・・・[3]
が成立する(予備定理１２―１)。従って、
【数８８】
である。
‖q.e.d‖
ここでは、拡張オイラー関数Φの乗積的性質が部分群位数kiに依存していないことが重要である。即ち、拡張オイラー関数Φの乗積的性質は素因数から生成された群の性質に依存していない。
【０１４３】
オイラー関数についての公式が拡張オイラー関数でも成立するのか検討してみる。
例えば、（６―４）式で示した
と言う公式は以下のように拡張できる。
【０１４４】
‖定理１２−４‖
【数８９】
但し、k=Пki,
である。
【０１４５】
‖証明‖
kqが奇数なら、d|kqも奇数であり、かつ、kq/dも奇数である。
従って、
【数９０】
である。
kqが偶数なら、kq=2ekg,
d=2fdg; と置くと、kg/dgが奇数であることから、
【数９１】
であり、以下のように変数分離できる。
【数９２】
このうち後の[]は奇数約数に係る和で、最初の[]は、
【数９３】
である。但し、級数和の範囲
で１の素因数のみからか構成されるので、後出する定理(１３−１)により
【数９４】
である。従って、
【数９５】
である。
‖q.e.d‖
【０１４６】
次に数値例を示す。
（１）kqが奇数の例
EHCG modulo:
n=493=17^1*29^1
GruopRank:
k=135=9*15
Max rank of
sub-groups: kq=45;
Σ(-1)^(kq/d)Φ(d|kq)=-135=-72-32-18-4-8-1
（２）kqが偶数の例
EHCG modulo:
n=11339=17^1*23^1*29^1
GruopRank:
k=1620=9*12*15
Max rank of
sub-groups: kq=180;
Σ(-1)^(kq/d)Φ(d|kq)=0=-432+216-208+216-108+104-8+54+104-52+4+54+26+4-2+26+1+1
ここでは、kq=22*45であるので、e=2,kg=45である。
-Φ(180)+Φ(90)+Φ(45)=0;
より、Φ(45){-22+2+1}=0とも書き直せる。同様に
-Φ(60)+Φ(30)+Φ(15)=0;
-Φ(36)+Φ(18)+Φ(9)=0;-Φ(20)+Φ(10)+Φ(5)=0;
-Φ(12)+Φ(6)+Φ(3)=0; -Φ(4)+Φ(2)+Φ(1)=0; が成立している。
【０１４７】
次に、拡張オイラー関数(GCD totient)Φ(x)が特定の条件下でオイラー関数φ(x)に帰着することを示しておく。
‖定理１３−１‖合成数である法ｎから派生する部分群の位数kiにつき、互いに共通する素因数を有しない場合には、拡張オイラー関数Φ(x)はオイラー関数φ(x)に一致する。
即ち、
で部分群位数ki=ki(pi)、群位数k=Πki、最大位数kq=[k1,k2,,,km]である場合に、任意の添え字i,jにつき(ki,
kj)=1ならば、Φ(x)=φ(x)である。
【０１４８】
‖証明‖(ki,
kj)=1ならば、拡張オイラー関数
において、GCDの乗積的性質(予備定理１２―１)により
【数９６】
であるが、k=khkq、(x/d)|kqであるので、約数x/dは群位数kで割り切れる。よって、
【数９７】
である。そこで、
【数９８】
である。
‖q.e.d‖
【０１４９】
次に、拡張オイラー関数Φ(n)の積表示を検討する。オイラー関数については、
【数９９】
・・・・（１３―１）
という積表示があるが、拡張オイラー関数Φ(n)でもその積表示があれば有用である。
【０１５０】
最初にΦ(pe)を検討する。最初に(１２―１)式で、x=
peと置いてみる。値xが1個の素因数で構成されるので、メービウス関数μ(d)の定義から、xの約数のうちd=1,pの場合だけを検討すれば足りる。
【数１００】
・・・・（１３―２）
である。素因数の個数m=1であるので、上式より
Φ(pe)=φ(pe)=
pe-pe-1である。
素因数の個数m>1であれば、変数xの素因数pに係る指数eに等しいかより大きなeiに係るkiの個数α(>=0)につき
である。
従って、（１３―２）式より
【数１０１】
・・・・（１３―３）
若しくは
【数１０２】
・・・・（１３―４）
と求められる。それ故、一般にkiに依存するのでΦ(pe)の値が一意に定まることはない。
【０１５１】
ここで拡張オイラー関数Φ(x)とオイラー関数φ(x)の比(Ratio)を検討する。既に本発明に係るグラフィックツールにおいて、オイラー関数値と拡張オイラー関数値の比の表示で説明していたように、以下の定理が成立する。
‖定理１３−２‖拡張オイラー関数Φ(x)はオイラー関数φ(x)で割り切れる。
【０１５２】
‖証明‖
（１３―１）、（１３―２）、(１３―３)式より、x= peの場合、
【数１０３】
・・・（１３―５）
若しくは
【数１０４】
となり、α(>=1)で、拡張オイラー関数Φ(pe)はオイラー関数φ(pe)で割り切れることが分かる。然るに、kg=peであるとすれば、kg|kq
及びkq=[k1,…,km]であるので部分群位数kiの中に素因数pに関しei>=eであるようなものが必ずあり、α>=1である。
ｘを構成する他の素因数も同様である。
従って、(１３―５)式より、拡張オイラー関数Φ(x)はオイラー関数φ(x)で割り切れる。
‖q.e.d‖
【０１５３】
この議論ををもう少し説明しておく。kq=[k1,…,km]より、k1,…,kmの中で素因数pに関し最高次数eMaxを有するものkMがあり、その他の指数はこれより小さいか等しく、素因数pに関し割り切れる。従ってkqの素因数pに関する次数はeMaxである。然らばe<=eMaxであるから、少なくともei>=eであるようなkiが存在し、e<=ei<=eMaxである。従って、x=kg|kqである変数xにおいて、その各素因数pjでαj>=1であることから、xに係る素因数の個数m1=ν(x)に対しΣαj>=ν(x)である。なお、比の中には法ｎや位数kiに含まれない新たな素因数がΣpiから派生する。
【０１５４】
ここで数値例で検証する。
法n=11339,k1=9,k2=12,k3=15,kq=180の拡張２次双曲線群で、
kg=3とした場合、φ(3)=2及び（１３―２）式より
であるので、
比
である。(１３―７)式を使った場合、p=3,e=1,α=3であるので、
であり、理論計算と一致した。この素因数q=13は新たに派生した素因数である。
【０１５５】
法n=351509,k1=9,k2=12,k3=15,k4=16,kq=720の拡張２次双曲線群で
kg=180とした場合、φ(180)=48及び
Φ(180)=+180*36-90*18-60*36+30*18-36*36+18*18+12*36-6*18=2592,
Ratio=54である。
(１３―５)式を使った場合、kg=180=22*32*5,k1=32,k2=22*3,k3=3*5,k4=24であるから、
p1=2, e1=2,α1=2;
p2=3, e2=2,α2=1; p3=5, e3=1,α3=1; であり、
Φ(22)/φ(22)=
20+1(2+1)=6; Φ(32)/φ(32)= 32+0(1)=9;
Φ(5)/φ(5)= 50+0(1)=1;
従って、Φ(180)/φ(180)=6*9*1=54
であり、理論計算と一致した。同様に、kg=24, φ(24)=8及び
Φ(24)=+24*36-12*36-8*4+4*4=416,
Ratio=52である。
(１３―５)式を使った場合、kg=24=23*3,k1=32,k2=22*3,k3=3*5,k4=24であるから、
p1=2, e1=3,α1=1;
p2=3, e2=1,α2=3;であり、
Φ(23)/φ(23)=
22+0(1)=4; Φ(3)/φ(3)= 30+0(9+3+1)=13;
従って、Φ(24)/φ(24)=4*13=52であり、理論計算と一致した。
【０１５６】
（１３―４）式において、ｘを構成する素因数qは必ずしもｎを構成する素因数pと一致しないので、本来
と表現すべきである。しかし、ｎを構成する素因数piは部分群位数kiを与えるだけで拡張オイラー関数Φ(x)の表現上直接現れない。そこで、ここでは素因数ｑを用いた表現はしないことにする。従って、素因数piは全てk若しくはkiに係る素因数のみで、法ｎとの直接の関係は無い。（１３―４）式より
【数１０５】
・・・・（１３―６）
となって、拡張オイラー関数Φ(x)の積表示を得ることができた。但し、素因数ｐjに関しベキ数ejに等しいかより大きなベキ数eiを有するkiの個数αjにつきαj>=1である。
【０１５７】
後の議論のために、拡張オイラー関数Φ(x)とオイラー関数φ(x)の比(Ratio)を明示の形で求めておく。
【数１０６】
・・・・（１３―７）
である。また、次の表示も見易い。
【数１０７】
・・・・（１３―８）
である。但し、素因数ｐjに関しベキ数ejに等しいかより大きなベキ数eiを有するkiの個数αjにつきαj>=1である。
【０１５８】
定理１３−２から、直ちに次の定理が導かれる。
‖定理１３−３‖
(a,n)=1であるようなaにつき
【数１０８】
である。
【０１５９】
‖証明‖拡張オイラー関数Φ(x)は定義域が狭く、通常x|kqなるｘ値のみしか定義されていない。無理に全自然数で定義しようとすればx|~kqでは、(１３―２)式よりΦ(x)=0である。そこで、x|kqなるｘ値に対しては、（３−１３）式により
とおけば、
【数１０９】
であり、x|~kqなるｘ値に対しては、
【数１１０】
である。
‖q.e.d‖
【０１６０】
次に2次双曲線群から導かれた拡張オイラー関数Φ(x)を他の拡張オイラー関数と比べてみることにする。整数論の教科書によれば著名なものとしてジョルダンのオイラー関数(Jordan’s
totient) Jm(x)がある。変数ｘを構成する素因数pjにつき
【数１１１】
・・・・（１３―９）
である。これをΦ(x)の積表示（１３―６）式と比べてみれば、添え字ｍを追加して
【数１１２】
・・・・（１３―１０）
であるので、似ていることがわかる。
【０１６１】
‖定理１３−４‖拡張オイラー関数Φ(x)は、ki=k0(固定)とすれば、ジョルダンのオイラー関数Jm(x)に帰着する。
【０１６２】
‖証明‖
（１３―１０）式で、ki=k0(固定)とすれば、kq=LCM(k0,k0,,,k0)=k0, x|kqであるのでkqは変数ｘで割り切れる。また、変数αjは変数ｘに係る素因数ｐjに関しベキ数ejに等しいかより大きなベキ数eiを有する「kiの個数」であり従って、ki=k0(固定)とすればαjはmの倍数でαj=m
or 0である。 2次双曲線群ではαj>=1であった。従って、
【数１１３】
・・・（１３―１１）
である。（１３―１１）式は2次双曲線群から導かれた拡張オイラー関数Φ(x)が、特定の条件下で、ｍ次のジョルダン・オイラー関数と一致することを示している。
‖q.e.d‖
【０１６３】
このことから、本発明に係る拡張オイラー関数(GCD totient)が、数ある拡張オイラー関数の中でも基本的で、かつ、原始的な関数であることがわかる。しかしながら、ki=k0(固定)とと言う条件は、異なる素因数から派生する部分群が全て同一の位数を有することを意味し、通常では有り得ない。この意味で、ジョルダン・オイラー関数は、その汎用性が失われている特殊関数である。
【産業上の利用可能性】
【０１６４】
以上のように、本発明に係る拡張オイラー関数等は未だ知られていないことが多く、研究段階の関数である。中でも拡張オイラー関数は拡張２次双曲線群の共役部分群の個数を規定する明確な意味があり、数学上も有用な関数と考えられる。そこで、本発明では拡張２次双曲線群解析ツールを設け、かつ、拡張オイラー関数のグラフィクスツールも付属させた。従って、この双曲線暗号の設計ツールが、双曲線暗号の初心者ばかりでなく、設計者、及び研究者に非常に有用である、と考えている。
【０１６５】
暗号の世界では、ＤＥＳ、ＲＳＡ暗号が依然有用と考えられているが、要求されるセキュリティのレベルも向上して、ビット数の増大で計算負担も増大し、暗号の簡単な利用ができない状況に至っている。双曲線暗号は、少ないビット数計算でも多ビット暗号と等価の計算困難性を容易に付加できるので、次世代の暗号として普及する可能性がある。
【図面の簡単な説明】
【０１６６】
【図１】２次双曲線設計ツールの全体図である。
【図２】素数テストツールでのn=1023のテスト結果である。
【図３】素数テストツールでのn=1031のテスト結果である。
【図４】素数テストツールでの篩法アルゴリズムのフロー図である。
【図５】素数テストツールでのGermann素数判定アルゴリズムのフロー図である。
【図６】素数テストツールでのn=1237のテスト結果である。
【図７】素数テストツールでの法ｐの採用方法を説明した図である。
【図３Ａ】設計ツールの上段部、曲線パラメータｃの採用を説明した図である。
【図９】設計ツールの上段部、曲線パラメータａの採用を説明した図である。
【図１０】設計ツールの中段部、曲線パラメータｄ及びｂの採用を説明した図である。
【図１１】設計ツールの下段部、データ保存を説明した図である。
【図１２】曲線パラメータのパラメータリストの全体図である。
【図１３】パラメータリストのショートカットメニューを説明した図である。
【図１４】ショートカットメニューの「ReCreateAllData」を実行したリスト図である。
【図１５】２次双曲線群解析ツールの全体図である。
【図１６】２次双曲線群解析ツールの解析集計アルゴリズムを示すフロー図である。
【図１７】２次双曲線群解析ツールの解析用曲線パラメータ等の確認を説明した図である。
【図１８】２次双曲線群解析ツールの解析結果を説明した図である。
【図１９】２次双曲線群解析ツールの集計結果を説明した図である。
【図２０】２次双曲線群解析ツールの詳細結果の表示を説明した図である。
【図２１】２次双曲線群解析ツールの詳細結果の表示、その２を説明した図である。
【図２２】拡張２次双曲線群解析ツールの指定した拡張２次双曲線群の計算結果を説明した図である。
【図２３】拡張２次双曲線群解析ツールの指定した拡張２次双曲線群の計算結果、その２を説明した図である。
【図２４】拡張２次双曲線群解析ツールの指定した拡張２次双曲線群の計算結果、その３を説明した図である。
【図２５】拡張２次双曲線群解析ツールに付属するグラフィックツールの全体図である。
【図２６】拡張オイラー関数のグラフィックツールにおけるオイラー関数値と拡張オイラー関数値の表示を説明した図である。
【図２７】拡張オイラー関数のグラフィックツールにおけるオイラー関数値と拡張オイラー関数値の比(Ratio)の表示を説明した図である。
【図２８】拡張オイラー関数のグラフィックツールにおけるマーカの書き込みを説明した図である。
【図２９】拡張オイラー関数のグラフィックツールにおける関数表示機能を説明した図である。
【図３０】４次の積集合を説明した図である。
【図３１】群位数の追加を説明した図である。
【図３２】拡張オイラー関数による群位数ｋの要素計算(n=351509) を説明した図である。
【図３３】群位数ｋの要素表示(n=351509,m=4) を説明した図である。
【符号の説明】
【０１６７】
【特許請求の範囲】
【請求項１】
与えられた法ｎが素数であることを判定するために割り数ｘを値２より順次大きくして値ｎ―１に至る過程で当該ｘが法ｎで割り切れた場合に法ｎが素数でなく、割り切れなかった場合に法ｎが素数であると判定する篩法において、法ｎが前記篩法において素数ｐと判定し、かつ、ｑ＝（ｐ＋１）／２も前記篩法において素数であると判定する方法を有し、当該法ｐを２次双曲線群の法とする指定を行う素数判定ツールを有する双曲線暗号の設計ツール。
【請求項２】
素数判定ツールにより指定された法ｐにおいて、２次曲線の判別式Ｄが平方非剰余であるように曲線パラメータの一部を選択し、若しくは、当該２次曲線値が平方非剰余であるように曲線パラメータの他の一部を選択し、当該選択された１又は複数の値を選択窓内に提示することにより、当該曲線パラメータの指定が可能な２次双曲線群の設計ツールを有する双曲線暗号の設計ツール。
【請求項３】
指定された法ｐ及び曲線パラメータの組を用いて、所定のベースポイントから出発した２次双曲線群の群計算を行い、その計算結果がゼロ元に一致した場合の前記群計算の回数から部分群位数kgを判定した後に、前記部分群位数kgが同一の前記ベースポイントの個数を計数して表示する２次双曲線群の解析ツールを有する双曲線暗号の設計ツール。
【請求項４】
請求項２の指定により定められた法ｐ及び曲線パラメータの組を一体のものとして保存し、その複数の組の１個を請求項３に係る２次双曲線群の解析ツールに提供する２次双曲線群の保存ツールを有する双曲線暗号の設計ツール。
【請求項５】
請求項２の指定により定められた法ｐ及び曲線パラメータの組を一体のものとして保存し、その複数の組の全てをリスト化して表示し、かつ、編集することができ、かつ、その複数の組の１個を請求項３に係る２次双曲線群の解析ツールに提供する２次双曲線群の編集ツールを有する双曲線暗号の設計ツール。
【請求項６】
法ｎを指定し、当該法ｎにおける拡張２次双曲線群の群計算を拡張オイラー関数式により行い、その結果を集計し、表示する機能を有する拡張オイラー関数の解析ツールを有する双曲線暗号の設計ツール。
【請求項７】
法ｎを指定し、当該法ｎにおける拡張２次双曲線群の群計算を拡張オイラー関数式により行い、その結果をグラフ表示する機能を有する拡張オイラー関数のグラフィックツールを有する双曲線暗号の設計ツール。
【請求項１】
与えられた法ｎが素数であることを判定するために割り数ｘを値２より順次大きくして値ｎ―１に至る過程で当該ｘが法ｎで割り切れた場合に法ｎが素数でなく、割り切れなかった場合に法ｎが素数であると判定する篩法において、法ｎが前記篩法において素数ｐと判定し、かつ、ｑ＝（ｐ＋１）／２も前記篩法において素数であると判定する方法を有し、当該法ｐを２次双曲線群の法とする指定を行う素数判定ツールを有する双曲線暗号の設計ツール。
【請求項２】
素数判定ツールにより指定された法ｐにおいて、２次曲線の判別式Ｄが平方非剰余であるように曲線パラメータの一部を選択し、若しくは、当該２次曲線値が平方非剰余であるように曲線パラメータの他の一部を選択し、当該選択された１又は複数の値を選択窓内に提示することにより、当該曲線パラメータの指定が可能な２次双曲線群の設計ツールを有する双曲線暗号の設計ツール。
【請求項３】
指定された法ｐ及び曲線パラメータの組を用いて、所定のベースポイントから出発した２次双曲線群の群計算を行い、その計算結果がゼロ元に一致した場合の前記群計算の回数から部分群位数kgを判定した後に、前記部分群位数kgが同一の前記ベースポイントの個数を計数して表示する２次双曲線群の解析ツールを有する双曲線暗号の設計ツール。
【請求項４】
請求項２の指定により定められた法ｐ及び曲線パラメータの組を一体のものとして保存し、その複数の組の１個を請求項３に係る２次双曲線群の解析ツールに提供する２次双曲線群の保存ツールを有する双曲線暗号の設計ツール。
【請求項５】
請求項２の指定により定められた法ｐ及び曲線パラメータの組を一体のものとして保存し、その複数の組の全てをリスト化して表示し、かつ、編集することができ、かつ、その複数の組の１個を請求項３に係る２次双曲線群の解析ツールに提供する２次双曲線群の編集ツールを有する双曲線暗号の設計ツール。
【請求項６】
法ｎを指定し、当該法ｎにおける拡張２次双曲線群の群計算を拡張オイラー関数式により行い、その結果を集計し、表示する機能を有する拡張オイラー関数の解析ツールを有する双曲線暗号の設計ツール。
【請求項７】
法ｎを指定し、当該法ｎにおける拡張２次双曲線群の群計算を拡張オイラー関数式により行い、その結果をグラフ表示する機能を有する拡張オイラー関数のグラフィックツールを有する双曲線暗号の設計ツール。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【公開番号】特開２０１１−１３７８９７（Ｐ２０１１−１３７８９７Ａ）
【公開日】平成２３年７月１４日（２０１１．７．１４）
【国際特許分類】
【出願番号】特願２００９−２９６５３６（Ｐ２００９−２９６５３６）
【出願日】平成２１年１２月２６日（２００９．１２．２６）
【出願人】（７０９００７４２３）
【Ｆターム（参考）】
【公開日】平成２３年７月１４日（２０１１．７．１４）
【国際特許分類】
【出願日】平成２１年１２月２６日（２００９．１２．２６）
【出願人】（７０９００７４２３）
【Ｆターム（参考）】
[ Back to top ]