各種日程、参加費については上記ウェブページをご覧ください。
各講演20分（質疑応答時間を含む）
○印は登壇者
MQ問題（2次の多変数連立方程式求解問題）の一般的な求解方法としてグレブナー基底を計算する方法がある。その計算の効率はreductorやS多項式と呼ばれる多項式の選択方法などに依存することが知られており、これらの多項式の選択方法に関する研究が進められている。グレブナー基底を計算するM4GBアルゴリズムは、多変数公開鍵暗号の安全性の根拠として利用されるMQ問題を解くコンテストであるFukuoka MQ Challengeにおいて設定されている6種の問題のうち、2種の問題において最も変数の多い連立代数方程式を解くことに利用されている。本講演ではMQ問題に対するM4GBアルゴリズムの最適な多項式の選択方法を調べるために実施した数値実験の結果とその考察について述べる。
有限体上の多変数連立2次方程式の解法については、グレブナ基底アルゴリズムと総当たり法を組み合わせた hybrid approach がよく使われる。ただ、これは over-defined な（方程式が変数よりも多い）場合にとくに効率的であり、under-defined な（変数が方程式よりも多い）場合にはそれほど有効でない。このような under-defined な場合については、Kipnis-Patarin-Goubin (1999)らによる多項式時間アルゴリズムをはじめとして、鄭-橋本-三浦-高木（2014)による多項式時間アルゴリズムや、Tomae-Wolf (2012), 古江-中村-高木(2021)によるHybrid approach を利用した指数時間アルゴリズムなどがこれまでにも考案されてきた。本講演では、さらに少ない変数で有効な、Hybrid approach を利用した方法を紹介する。
本講演では、$n$次元整数格子上の1つの格子点と他の2つの格子点により定まる角（格子角）を調べ、3次元格子のみ性質が異なることを明らかにする。成分がすべて整数であるベクトル（整数ベクトル）を用いると、格子角は2つの整数ベクトルのなす角と言い換えられる。整数格子上のすべての格子角の集合は次元$n$ごとにBeesonにより求められている。本研究では、1つの整数ベクトルを固定したとき、このベクトルと他のすべての整数ベクトルによってつくられる角の集合を調べる。3次元以外の格子では、固定するベクトルをどのように選んでも、他の整数ベクトルを適切に選べば、すべての格子角を実現できる。一方で、3次元格子では、任意の固定するベクトルに対して、実現できない3次元格子角が必ず存在する。このように、格子角の性質は3次元格子のみで異なるのである。講演ではこの結果の証明の概要を述べるとともに、時間があれば3次元の格子角のより詳細な性質にも触れる。
ユークリッド空間内の一次独立なベクトルの集合に対して，それらの整数係数の一次結合全体の集合を格子と呼ぶ．格子の中でノルムの短い非ゼロベクトルを求める計算問題（最近ベクトル問題）は多くの応用を持ち，多様なアルゴリズムの開発が続けられている．特に，[Dieter 1975, Math. Comp.][Kannan 1983, STOC]により提案された格子点探索アルゴリズムは木構造を用いた表現の単純さ，実装の容易さから近似率の高い最短ベクトル問題を解く際の基本的なツールとして用いられる．[Gama-Nguyen-Regev 2010, Eurocrypt]による枝刈り(Extreme Pruning)戦略は短いベクトルが発見される確率，長さ，計算コストの正確な見積もりが事前に可能であり，格子問題の困難性を根拠とした暗号の解読計算量解析において重要な役割を果たす．本発表では，ターゲットとなるベクトルの長さがある程度長く，確率を低く設定した際の枝刈り戦略による計算コストの見積もりが現実のコストと大きくずれる現象を報告し，その解決方法の提案と計算機実験の結果を報告する．
位数nのモジュラー多項式とは, 二変数整数係数多項式であって、2つのj-不変量がその根になることと対応する楕円曲線の間にn次巡回同種写像が存在することが同値である、という性質を持つものである。本発表では、これを高レベルのモジュライ空間の元と対応する楕円曲線の係数への拡張することについて述べる。1つの係数で記述される楕円曲線のモデルがその座標に関するスカラー倍公式、同種写像公式、等分多項式を持つとき、そのモデルの係数に関するモジュラー多項式が存在することを示す。この理論が適用可能な例としてMontgomery曲線、Hesse曲線がある。また、これらの曲線に関するモジュラー多項式の構成アルゴリズムを具体的に与える。
有限体上の通常楕円曲線の自己準同型環は二次体の整環と同型である。本研究では、通常楕円曲線の自己準同型環を計算するアルゴリズムを提案する。具体的には、Bisson-Sutherlandによるモジュラー多項式を利用したisogeny climbingとイデアル類群を利用したfinding relationsなどの既存手法は自己準同型環の判別式を求めるが、本研究の提案アルゴリズムは同種写像列によるサイクル探索により自己準同型環の生成元を明示的に求める。また、本提案アルゴリズムの応用として、同種な通常楕円曲線間の同種写像全体のなす群の生成元と群構造を決定する手法を紹介する。
超楕円曲線のヤコビアン上の加法を具体的に扱う際は，MumfordがTata Lectures on theta II, 1984で導入したヤコビアンの元の記述法（Mumford表現と呼ばれている）を用いたCantorの手法(Computing the Jacobian of a hyperelliptic curve, 1987) がよく知られている．一方，ヤコビアンの元の記述の仕方としては，Leitenbergerが導入したもの(About the group law for the Jacobi variety of a hyperelliptic curve, 2005)もある．これらの二つの表現については，Takahashi and Tokunaga, Representations of divisors on hyperelliptic curves and plane curves with quasi-toric relations, 2022 において，Gröbner基底の視点からその関係が整理されている．なお，Gröbner基底を用いる手法としては，Aritaによる$C_{ab}$-curveのヤコビアン上の計算に関する研究が知られている．こうした状況のもと本講演では以下の内容について報告する：
Cantorによるヤコビアン上の加法には，Composition stepとReduction stepの二つのステップがあるが，ここでは，
(i) Composition stepを，超楕円曲線の座標環のイデアルの積から誘導される多項式イデアルのGröbner基底の計算として実装した．
(ii) Reduction stepでは，（イ）Cantorによるものと，（ロ）Takahashi and Tokunaga で考察されたものを改良しGröbner基底の取り替えを用いたもの，の二通りの手法について実装した．
(iii) その結果をLeprevostが与えた$\Q(t)$上の種数$2$の超楕円曲線及び位数有限の有理点$P$の例に対して適用し，$nP$の計算時間を比較した．上記の例については，$n$が大きくなると，Reduction stepでの手数が少ない（ロ）の手法が計算時間が少なくなるのでは無いかと予想していたが，(iii)で考察した例については，予想通りであることが観察された．
正標数p>0の体上の代数曲線に対するCartier-Manin行列とは、正則微分形式のなす空間へのあるp^(-1)線形作用（Cartier作用と呼ぶ）を記述する行列のことであり、有理点の勘定や超特異性の判定などに用いられる。2020年にSutherlandは、hyperelliptic曲線の一般化であるsuperelliptic曲線y^m=f(x)に対し、x座標の平行移動を利用することでCartier-Manin行列を高速に計算するアルゴリズムを提案した。
本講演では、Sutherlandアルゴリズムにおいてx座標の平行移動だけでなくメビウス変換を利用することで、非自明な自己同型をもつsuperelliptic曲線に対し更に高速にCartier-Manin行列を計算するアルゴリズムを提案する。提案アルゴリズムをPythonで実装し数値実験を行った結果、Sutherlandアルゴリズムに対し最大2倍程度高速となる結果を得たのでこれを報告する。
位数n^2の数独解とは, サイズn^2×n^2の方陣に, 1, 2, ..., n^2の数字(シンボル)を入れ, どの縦の列、横の行にもすべてのシンボルがちょうど1 回ずつ出現し, サイズn×n のn^2 個の小方陣(ブロック)に全てのシンボルがちょうど1 回ずつ出現するように配置したものである. n=3の場合は通常の数独パズルの解(完成形)である. 数独解を同値な数独解に移す作用素の集合は群を成し数独群と呼ばれる. 通常, 数独は2次元で考えるが, Lambert and Whitlaock(2010)は3次元に拡張した.申込者は2022年９月応用数理学会JANTセッションにて3次元数独解の同値な条件と作用素の特徴を与えた. Modular Magic Sudoku とは, 小方陣における行和・列和・対角線和がn^2を法として0と合同になるという条件を追加した数独解であり, nは3以上の奇数となる. 最小位数n^2=9の場合の構造はLoach and Weldによって解明された. 本講演では, 最小位数のModular Magic Sudoku を３次元空間へ拡張し,同値なModular Magic Sudokuに移す作用素の特徴を述べる.
東京都立大学 大学院理学研究科 数理科学専攻
内田 幸寛
yuchida@tmu.ac.jp