第4回「代数学と計算」研究集会(AC2001)アブストラクト

講演者または提案者による原文のままの「内容の簡単な解説」です.
その後に加筆・修正された場合は, その文章に置換えられています.

----------------------------------------------------------------
１１月５日（月）

・渡辺治（東京工業大学）
計算の複雑さの理論

・倉田俊彦（東京都立大学）
Combinatory Representations of λ-Calculus:
	λ計算におけるβ-equalityを関数抽象に関連するξ-規則を用いず
	に記述する。combinatory logicの体系を基に2種類の記述が与えら
	れ、一つはMeyer-Scott公理の制限、もう一つはweak-equalityの構
	造の自然な拡張となっている。表示的意味論の観点から、これらの
	記述はλ代数のクラスを特徴付けていることになる。

・赤間陽二（東北大学）
極限操作を用いた計算と構成的論理:
        極限操作を用いた計算は学習理論などでみられるが、その能力は普通の
	計算の能力より飛躍的に高い。極限操作の入れ子の回数により計算力の階層
	ができ、Kleeneのjump階層に対応する。この階層が、
	二重否定の除去の公理の階層に対応することを説明する。また、
	不連続な数学的関数への関わりを述べる。

・坂本伸幸・田中一之（東北大学）
ヒルベルトの零点定理と２階算術:
	次のようなヒルベルトの零点定理が，２階算術の体系RCAoで
	証明できることを示す：任意の$n,m$について，
	$p_1$, ... ,$p_m \in \mathbf{C}$[$x_1$, ... ,$x_n$]が共通根を
	持たないとき，$q_1, ... , q_m \in \mathbf{C}[x_1, ... , x_n]$が存在して，
	$p_1q_1 + \cdots + p_mq_m = 1.$

	体系RCAoは，$\Delta^0_1$内包公理と$\Sigma^0_1$帰納法に基づく
	２階算術の体系であり，計算可能数学の形式的枠組みと見なせる．
	実数や複素数は有理数の基本列を用いて定義し，それらが
	実閉体や代数的閉体を形成することはRCAoで証明できる．
	しかし，実数の種々の計算（例．連立一次方程式の解法）では，
	ある実数$X$が$0$か否かという有限的に判定できない条件分岐を
	無制限に用いるので，その計算の手続きを形式化することで，
	RCAoにおいて解などの存在をいうことは難しい．

	上の定理は，量化記号消去法に基いて，$\mathbf{R}$の充足関係を
	定義し，その性質を調べることによって得られる．

・藤崎 竜也 (九州大学)
有限射影空間 PG(3,q) から出来る Strongly regular graph:
	 qを２の巾(４以上)とします。有限射影空間 PG(3,q)の hyperbolic
	 quadric を取り、この quadric に関する external (projective)
	 line つまり quadric の点を持たない line の集合をとります。

	 この集合から intersection による４つの関係と diagonal relation
	 により class 4 の association scheme が得られました。

	 また、この association scheme から factor scheme が得られ、class
	 2 であるため strongly regular graph が構成できました。
	 この graph の parameter 達はある partial geometry (存在に関しては
	 不明)から得られる strongly regular graph と同じ parameter をもちます。

	 q=4 のときはこの partial geometry の非存在が知られています。
	 q=8 のときはこの partial geometry が存在するとしても、これから
	 得られる graph と factor scheme から得られる graph が異なるもの
	 であることが証明されました。

----------------------------------------------------------------------
１１月６日（火）

・小山陽一（金沢工業大学）・吉野健一（金沢医科大学）
実円分体の類数の素因子の計算:
導手が素数冪の円分体の最大実部分体の類数について、その
         素因子を求める計算手法ならびにアルゴリズムについて、最近
         までに得られた我々の結果を紹介する。方法としては多項式を
         用いている。最大実部分体とその部分体に対して、それぞれ一つづ
         つ特性多項式を対応させる。この講演では、ある奇素数 $\ell$ に
         対して、ある円単数の $\ell$ 乗根がその体の単数群に入るか否か
         の判定をある多項式の既約因子を調べることで実行できることを
         示し、最終的には実円分体の類数の素因子を見つけることがその
         体に対応している特性多項式のうち、非自明なものを探すことと
         同値なことを示す。

・近藤通朗（島根大学）
weak interlaced bilattice の構造について:
        Logic Programming の意味論において有用である weak
	interlaced bilattice の構造について述べる．具体的には，任意の有界な束 L から
	作られる典型的な weak interlaced bilattice K(L) に対して， interlaced
	bilattice B が存在し，K(L) と B のある元全体が同型となることなど
	を示す．

・Hatem M. Bahig（東京都立大学）
Generating Minimal Addition chains:
	 An addition chain for a positive integer $n$ is a sequence
	 $1=a_0<a_1< \ldots < a_r=n$ of integers such that for each
	 $0<i\leq r,$ $a_i=a_j+a_k$  for some $0\leq k\leq j<i$.
	 We shall present how to generate all minimal addition chains
	 and how to improve it.

・田村明久（京都大学）
離散最適化

・石関隆幸（東京大学）
有向グラフの standard pair 分解と最小費用流問題:
	 近年，toric ideal の initial ideal の standard pair分解が
	 研究されています．特に，toric ideal が homogeneous なときには，
	 standard pair の特徴づけがされています．本発表では，toric
	 ideal が homogeneous とは限らない有向グラフ の toric ideal
         について，最小費用流問題の性質からの特徴づけを行うとともに，
	 最小費用流問題や多面体の三角形分割との関係について考えます．

・荻野大助・澤田秀樹（山形大学）
暗号系に現れる群構造:
	 ブロック暗号の鍵の集合の持つ群論的な特徴に注目し，その
	 性質を利用した落し戸の理論的な構成法の一つを提案する。

----------------------------------------------------------------------
１１月７日（水）

・脇克志（弘前大学）
Construction of the finite groups by a given centralizer of an involution:
	  位数２の元とその元を中心に含む有限群 H が与えられたとき、こ
	  の H の elementary abelian 2-group を使って新しい有限群 G を
	  構成する方法を紹介するこの方法で散在有限群のうち最小のM11と
	  最大の B を除く全ての有限単純群が得られることが可能であるこ
	  とが示されている。

・足立智子・上原啓明・神保雅一（慶応大学）
線形符号から生成されるBIBデザインによるquorum systemのfailure polynomial:
	   quorum systemとは，任意の２つの集合が空でない共通部分を
	   必ず持つという集合系であり，排他制御など分散システムの
	   分野に広く応用されている.
	   このquorum systemsがどの程度有用なものかを判断する基準の
	   一つとして，failure polynomialがある．
	   一方，Colbourn, Dinitz, Stinsonは，$\lambda=1$の
	   $(v,k,\lambda)$-BIBデザインからquorum systemを構成する
	   方法を見出し，計算機を用いて$k=3$かつ$v \leq 15$のBIB
	   デザインについてfailure polynomialを計算したが，
	   この計算は非常に煩雑なものであり一般のBIBデザインについて
	   有用であるとはいえない．
	   そこで，本報告では，
	   線形符号から生成されるBIBデザインによるquorum systemについて，
	   繁雑さを軽減してfailure polynomialを計算した．

・佐藤秀・大原幸多・神保雅一（慶応大学）
BIBデザイン生成のための推論システム：
	本研究ではBIBデザインの既知の構成定理を組み込むことにより，
	ユーザーから与えられた入力パラメータに対応するブロックデザインを
	推論アルゴリズムにより構成し，さらに得られた結果をデータベースとし
	て蓄積する推論システムDesNaviを構成した．

・宗政昭弘（九州大学）
有限幾何とデザイン

・島倉裕樹（東京大学）
$4A$元に関するMcKay-Thompson級数の計算:
	 Moonshine moduleはLeech latticeの$2k$-frameに対応する部分VOAを持ち、
	 その部分VOAの加群としての分解は$Z/2kZ$上の符号を用いて記述される。
	 $k$が奇数の場合には、この分解を用いてモンスター単純群の共役類
	 $4A$のある元の作用が簡単に記述でき、$4A$元に関する
	 McKay-Thompson
	 級数を符号を用いて記述される。
	 特に、ある$Z/6Z$上の符号を用いてMcKay-Thompson級数を計算機を
	 用いて具体的に与えた。

・小関道夫（山形大学）
Covering radius problem for non self-dual binary codes:

----------------------------------------------------------------------
１１月８日（木）

・岸康弘（東京都立大学）
基本単数を根に持つ３次巡回多項式の族について:
	ワンパラメーターの入った、ある３次巡回多項式の族を考える。
        その多項式の３つの根のうちの２つが、それらが生成する整環の
        基本単数系となること、また、ある条件の下ではその根のペアが
        分解体での基本単数系になっていることを示す。
          また、基本単数系が分かると類数の上限が得られる。このこと
        を用いて、我々の扱う多項式の分解体の族の中で類数が小さいも
        のが有限であることを示す。
          時間があれば、我々の考察した多項式の出所や、良く知られた
        シャンクスの多項式との関係についても解説したい。

・中原徹（佐賀大学）
On the 2th power-class ranks of quadratic fields(二次体の類群の 2巾階数について):
	 We would show several characterizations of families of
	 quadratic fields whose class groups have 2th power ranks
	 by way of the works of H. Cohn
	 or Ihara's zeta attached to a certain graph.

・小松啓一（早稲田大学）・福田隆（日本大学）
虚２次体の非円分 $Z_p$ 拡大の岩澤不変量について:
	虚２次体の ray class fields から作られる非円分 $Z_p$ 拡大の
	岩澤不変量を考察する。まずこの $Z_p$ 拡大の中間体を具体的に
	構成し(この段階で計算機実験による中間体の特定作業を行なう)、
	中間体の数論的性質を調べる。次に PARI を用いて類群を計算する。
	類群がある条件をみたせばμ不変量とλ不変量が０になることが判り、
	我々の計算例ではかなりの場合について μ=λ=0 を示すことができた。
	この問題は総実代数体の円分 $Z_p$ 拡大のλ不変量が０であろうという
	Greenberg Conj. の類似であり、Greenberg Conj. の攻略法を探る意味
	でも、この非円分 $Z_p$ 拡大は重要な研究対象であると我々は考えている。

・西野哲朗（電気通信大学）
量子計算

・知念宏司（大阪工業大学）・村田玲音（明治学院大学）
a (mod p) の剰余位数の分布について:
	  2 以上の自然数 a を取り，a の Z/pZ* (乗法群) における位数を
	  $D_a(p)$ とする．このとき，集合

	  $ Q_a(x;k,l):={ p \leq x ; D_a(p) \equiv l (mod k)}$

	  の自然密度を求める問題を考える．k=2 の場合が Sierpinski によって
	  問題提起され(1958)，その場合を Hasse が解決(1965-66，剰余項なし)，
	  k が square free な合成数で l=0 の場合に Odoni が剰余項付きで
	  自然密度を求めている(1981)．
	    われわれは昨年，k=4 のときにある条件のもとで l=0,1,2,3 に対する
	  密度を求めた(l=1,3 のときは一般 Riemann 予想(GRH)を仮定)．これは
	  (GRH の下ではあるが) k $\geq$ 3 で l$\ne$ 0 の場合に得られた最初の
	  結果と思われる(cf. 数理研講究録 No.1219)．
	    今回の講演では，主に k が奇素数べき $q^i$ の場合に，われわれが
	  得た結果を報告する．

・横山和弘（九州大学）・野呂正行（神戸大学）
小さい標数の有限体上の多項式イデアルの準素分解について:
	  有理数体上の多項式イデアルの準素分解法であった、下山-横山による
	  方法を有限体上の場合に適応させた方法を提案する。ここで、有理数体と
	  大きく異る部分は、根基計算とその素分解であり、この部分を重点
	  として説明する。

----------------------------------------------------------------------
１１月９日（金）

・宮本泉（山梨大学）
Zimmermann のGMP-ECMによる円分数の素因子分解の報告:
	   Zimmermann のelliptic curve methodによる素因子分解プログラム
	   GMP-ECMを使用して112桁＝55桁×57桁の素因子分解を得た
	   ことを報告したいと思います。プログラムは学科の教育用計算機75台
	   をいっせいに動かして計算しました。
	   55桁の素因子はelliptic curve methodによる素因子分解では新記録らしいです。
	   ただし、parallel computingをする以外にはさしたるくふうはしていません。

・小林大輔・阿部瑞穂・中村憲（東京都立大学）
Some computation on the odd covering problem:
	    整数のcoveringについてのopen ploblemとして,odd coveringの存在の
	    有無というものがあります.それを調べるために,coveringをグラフを
	    使って表現するという方法が考案されています.
	    今回は,この方法をもとにした,限定された状況でのcoveringの存在を
	    調べるプログラムを作成し,計算機実験を行った結果に付いて報告します.

・橋本竜太（名古屋大学）
媒介変数を含む代数的無理数の連分数展開のアルゴリズムの実装:
	    c は正整数値をとる媒介変数とする.
	    $(c^3-1)^(1/3)$ や,$X^3 - c X^2 - 1$ の実根などといった
	    代数的無理数の連分数展開を, c を含む形で求めたい.
	    そのためのプログラムをコンピュータ上に実装したことについて報告する.

・金山直樹(早稲田大学)・長尾孝一(関東学院大学)・内山成憲(NTT)
Generating Hyperelliptic Curves Suitable for Cryptography:
	   暗号論的に安全な種数２の超楕円曲線の生成法について述べる．
	   　Elkiesが提案したアイデアにpracticalな工夫を加えてみて，
	   ヤコビアンが十分大きな素数(または大きな素因子をもつ)位数を
	   持つような超楕円曲線をreasonableな時間で探すことが出来るか
	   試みた．
	   　Elkiesのアイデアでは準備計算としてBabyStepGiantStep法を
	   行うのであるが，この計算において
	   ・Baby-Stepで計算したデータの格納の仕方を工夫する
	   ・Baby-Stepの幅の長さを調整する
	   というような工夫を加えてみた．
	   　このような工夫を加えることにより，例えば20ビットくらいの
	   標数に対し，ヤコビアンの位数が160ビット以上の素因子を持つ
	   ような超楕円曲線は，一般に普及しているようなPCを使って数分
	   間計算させれば一つ探すことが出来た．
	   　上の工夫の内容とその実験結果について発表する予定である．

・竹内良平（東京都立大学）
楕円曲線のmod pでの周期性と計算機実験:
	   $E$を$\mathbf{Q}$上定義された楕円曲線とし, $F_p$を$p$元体とすると,
	   $E$の$\mathbf{F}_p$-有理点の成す群$E(\mathbf{F}_p)$は高々2つの巡回群の
	   直積になることが知られている.  $E$を一つ固定し, 素数$p$を動かすとき
	   $E(\mathbf{F}_p)$がどのくらいの頻度で巡回群になるか?という質問を考える.
	   $E$がMordell-curveと呼ばれる曲線のとき, この頻度をexplicitに計算したので
	   それを報告する.  また, その他の曲線に対しても計算機実験した結果を述べたい.

・桶屋勝幸（日立製作所）
モンゴメリ型楕円曲線 $By^2=x^3+Ax^2+x$ におけるスカラー倍計算の高速化について:
	   我々は、モンゴメリ型楕円曲線におけるスカラー倍計算において、計算量が増大しな
	   いランダム化射影座標を提案する。ランダム化射影座標は楕円曲線暗号に対するサイ
	   ドチャネル攻撃を防ぐための一手法である。これは、座標表現をランダム化すること
	   により、特定の数値の出現を攻撃者に対して予測不能とする防御方法である。しかし
	   ながら、座標表現のランダム化によりZ座標の値を1とすることができず、そのためZ
	   座標との乗算が発生し、計算量が増大していた。提案法のスカラー倍計算方法によ
	   り、サイドチャネル攻撃の脅威にさらされるスマートカード等への実装に関する、モ
	   ンゴメリ型楕円曲線の優位性を明らかにする。

・佐藤孝和（埼玉大学）
楕円曲線の有理点に関する計算

リンク:

第4回「代数学と計算」研究集会

「代数学と計算」ホームページ