有限体上の代数曲面に関する求セクション問題から生じる連立方程武の半正則性について

摘要

代数曲面に関する求セクション問題（AS-SFP）は量子計算機においても多項式時間のアルゴリズムが知られていない。このため、耐量子暗号の1つである代数曲面暗号の安全性の根拠ともなっており、その計算量評価は同暗号のパラメータを設計する上で重要な課題となっている。AS-SFPはある種の多次多変数連立方程式（セクション方程式）の求解問題に帰着でき、これはグレブナー基底計算によって解くことができる。グレブナー基底計算の計算量は定量化困難であるが、連立方程式が半正則である場合は容易となることが知られている。本研究ではセクション方程式の半正則性について評価することにより計算量の定量評価を試みた。計算機実験により、小さいパラメータに対してはほとhど半正則にならないが、特定のパラメータを大きく取ると、半正則に近づく傾向があることが分かった。