位数nの巡回群G、その生成元gとGの元bを与えて、グ=bであるような整数xを求める問題を離散対数問題と言う。

Gが有限体の乗法群や有限体上の楕円曲線の有理点の群の場合において離散対数問題の多項式時間アルゴリズムは知られていない。これらの群上の離散対数問題の困難性は暗号系の構築によく利用されている。だからこれらの群上の離散対数問題の計算量の下限を評価するのは重要かつ難しい問題である。この論文はこの問題を調べる。

第2節で一般的な巡回群における離散対数問題に対する指数時間アルゴリズムを三っ紹介する。2.1節で中国の剰余定理を利用する自然なアルゴリズムを紹介する。群の指数のすべての素因子が小さい場合にこのアルゴリズムは有効である。2.2節でShanksのアルゴリズム([Shanks 1971])を紹介する。このアルゴリズムの時間計算量と空間計算量はともにO(√n)である。23節でPollardのアルゴリズム([Pollard 1978])を紹介する。このアルゴリズムの時間計算量はO(√n)であり、空間計算量はO(1)である。

第3節で有限体の乗法群における離散対数問題に対する準指数時間アルゴリズムを三つ紹介する。セクション3.1でIndex Calculusアルゴリズムを紹介する。Index Calculusアルゴリズムは1922年にKraitchik氏[Kraitchik 1992]によって提案されて、有限素体の乗法群上の離散対数問題を解くアルゴリズムである.素体Fpの乗法群上の離散対数問題を解く場合にこのアルゴリズムの計算量はexp(C(logp)1/2(loglogp)1/2)である(Cは正の実数定数である)。3.2節で代数体師い法を紹介する。代数体篩い法は最初1993年に因数分解アルゴリズムとして提案された。後その類似としての離散対数アルゴリズムが発見された(「Gordon 19931)。素体Fpの乗法群上の離散対数問題を解く場合にこのアルゴリズムの計算量はexp((64/9+o(1))(logp)1/2(loglogp)1/2)と予想される。3.3節で関数体篩い法を紹介する。関数体師い法は1994年にAdleman氏によって提案されて、1999年にAdleman氏とHuang氏によって改良された([Adleman and Huang1999])。有限体Fqの乗法群上の離散対数問題を解く場合にこのアルゴリズムの計算量はexp(C(logq)1/2(loglogq)1/2)と予想される。

離散対数問題の計算量下限を評価するため、直接この問題を解くアルゴリズムを探す他にこの問題と同値な問題を探す手法もある。2009年にHuang氏とRaskind氏は有限素体上の離散対数問題を実2次体と結びつけた(「Huang-Raskind 20091)。彼らは実2次体に対してramification signatureというものを定義し、ある二つの仮定の下で、有限素体上の離散対数問題と実2次体上のrami丘cation signatureの計算問題の同値性を証明した。仮定の一つは実2次体の類数に関するもので、もう一つは実2次体のある単数に関する仮定である。この仕事を第4節で紹介する。

この論文の主要部である第5節では実二次体のramification signatureを一般化する。もとのramification signatureは「pとlは両方分解する」という場合に定義されたが、このセクションでは「pが不分岐で1が分解する」という場合へ一般化する。それから有限素体と位数が素数の平方であるような有限体上の乗法群上の離散対数問題と実2次体上のramification signatureの計算問題の同値性をある仮定の下で証明する。この仮定は実2次体の類数に関する仮定である。特に、Huang氏とRaskind氏の証明から単数に関する仮定を削除してもよいということを示す。具体的には、実2次体と単数を構成するアルゴリズムを改良し(本文の5.3節のStep4)、[Huang-Raskind 2009]の中の4.1節の命題2の条件(2),(3)が自動的に満たされるようにする。

張氏は、提出論文において、有限体上の離散対数問題を研究した。有限体の乗法群Fq×は巡回群であり、その生成元gがある。Fq×の元aに対し、a=gmをみたす整数mを求める問題を離散対数問題といい、コンピュータ暗号への応用が知られている。

Hwang氏とRaskind氏は離散対数問題の解法として、実2次体の単数を用いる方法を提案した。張氏は本論文でこの方法の一般化について研究した。pとlを相異なる奇素数とし、Kを実2次体とする。Kはpで不分岐かつlで完全分解と仮定する。uをpの上にある素点、vをlのうえにある素点とする。uの剰余体の位数q=Nuがq≡1 mod lをみたすと仮定する。またKの類数はlで割れないと仮定する。Kの素点wに対し〈 , 〉w:H1(K, Fl)×K×→Flで類体論の相互写像が定める標準ペアリングを表す。Kのl次巡回拡大でu,vの外で不分岐で、u,vで分岐するものをとり、χを対応するガロワ群の指標とする。αをKの単数とすると、類体論の相互法則より〈χ,α〉u+〈χ,α〉v=0となる。

HwangとRaskindの方法は、この事実に基づき乗法群Fq×=κ(u)×における離散対数問題を、有限体の加法群Fq=κ(v)での除法という、より簡単な問題に帰着させようというものである。しかしその際、〈χ,g〉uと〈χ,1+l〉vの比を求めることが必要となり、分岐符号とよばれるこの比を求める問題と、離散対数問題が同等という結論が得られる。

HwangとRaskindは、この方法をKがpで完全分解の場合、すなわちq=pの場合に考察した。張氏は、この方法がKでpが分解しない場合、すなわちq=p2の場合にも適用できることを示した。論文の主結果は次のとおりである。

主結果 pとlを相異なる奇素数とし、p2≡1 mod lと仮定する。q=p, p2に対し, pで不分岐かつlで完全分解する実2次体Kとその単数αで、Kのpの上にある素点とlの上にある素点に関する分岐符号問題が、Fq×における離散対数問題と同値であるものを構成できる。

ただし、構成した実2次体Kの類数はlと素であると仮定する。また、構成した単数αが条件をみたす確率は50%でありこの構成をくり返すことで、条件をみたすものが確率的に得られる。

証明の方法は基本的にはHwangとRaskindの議論をなぞるものではあるが、次のような点で改良も加えている。この方法を適用するためには、〈χ,α〉vが0でない単数αを構成することが必要である。HwangとRaskindの論文ではこのような単数の存在は仮定とされていたが、単数の構成を工夫することで、この仮定を少なくとも確率論的には取り除くことができた。HwangとRaskindの論文と同じく、類数がlで割れないという仮定は除くことができない。

以上のように、本論文において論文提出者張祺智氏は有限体上の離散対数問題に関するHwang氏とRaskind氏の方法を考察し、それをさらに進めることに成功している。これは、博士(数理科学)の学位を与えるにふさわしいものである。