各講演20分(質疑応答時間を含む)
○印は登壇者
位数n^2の数独解とは, サイズn^2×n^2の方陣に, 1, 2, ..., n^2の数字(シンボル)を入れ, どの縦の列、横の行にもすべてのシンボルがちょうど1 回ずつ出現し, サイズn×n のn^2 個の小方陣(ブロック)に全てのシンボルがちょうど1回ずつ出現するように配置したものである. n=3の場合は, 通常の数独パズルの解(完成形)である. 数独については様々は研究がなされており,素数pについて, 位数p^2の数独解の構成法はKeedwell(2010)によって与えられた. 通常, 数独は2次元で考えるが, Lambertand Whitlaock(2010)は3次元に一般化している. そこで, 本研究では, 拡大体を用いて, 高次元の数独解の構成法を与える.
p=1 mod 3となる素数、及び{1,w,w^2}を1の3乗根とする。 EをFp上楕円曲線E:y^2+axy+by=x^3とする。 写像 E(Fp) -> {1,w,w^2} を P=(x,y)->y^(p-1)/3 と定義する。 この写像が準同型であることを示す。 E:y^2=x^3+ax+bの場合も考察する。
Ring-LWE問題は代数構造を持つ格子暗号方式の安全性を支える 求解困難な数学問題の1つである. Kannanの埋め込み法により探索Ring-LWE問題はある 格子上の最短ベクトル問題に帰着でき, 格子基底簡約アルゴリズムにより探索Ring-LWE問題を求解できる. 本稿では,Ring-LWE格子上のrotation 操作による Kannanの埋め込み法の拡張を提案すると共に, その拡張による利点と欠点について述べる.
Radical isogeniesとは、小さな正整数Nに対してN次同種写像を繰り返し計算す る公式である。Radical isogeniesでは核の生成を省略でき、一部の同種写像暗 号の計算を高速化できることが知られている。しかし、radical isogeniesで は、小さな次数の同種写像計算とその他の計算のための楕円曲線で異なる形を用 いる必要があり、それらの間の変換がオーバーヘッドとなる。本研究では、同種 写像暗号で広く用いられている楕円曲線の形であるMontgomery形において次数3 と4のradical isogeniesの公式を導出した。これらの公式では曲線の変換が必要 ないため、一部の同種写像暗号の計算を高速化できる。さらに、有限素体上の次 数4のradical isogeniesの公式に関する未解決であった予想を肯定的に解決した。
与えられた種数に対し,代数曲線をその定義方程式付きで効率よくパラメトライズすることは基本的な問題であるが,非超楕円曲線については一般には困難が伴う.種数5の非超楕円曲線は,トリゴナルか否かで分類され,前者の場合の定義方程式は既に考察済みである(JANT2018秋の発表).本講演では,後者の場合を平面射影6次曲線の特異点解消として実現する.特異点が悪くない場合(genericと呼ぶ)は,特異点の配置に着目し,可能な限り少ない未知係数をもつ定義方程式を明示的に構成し,非常に効率のよい表示を与えることが出来た.応用として,標数3の素体上種数5のgeneric曲線で,二次拡大体上で有理点の個数が最大となるものを計算機によって全て数え上げた.
楕円曲線には通常曲線と超特異曲線の二タイプの曲線が存在する。ある楕円曲線が与えられたときにその曲線が超特異曲線であるかを判定する効率的かつalmost deterministic なアルゴリズムがSutherland により提案されている。このアルゴリズムの支配的な計算コストは有限体上の平方根計算となっている。本研究ではその支配的な計算コストをLegendre型の楕円曲線とその間の同種写像の性質を用いることにより、約半分に削減出来ることを示した。また、768bitから1024bitの標数pにおいて計算実験を行うことにより、44.3% から 56.4%計算時間が削減されたことを示した。
関東学院大学 理工学部数物系
長尾孝一
nagao@kanto-gakuin.ac.jp