グレブナー基底計算の理論計算量解析とその効率的な実装

点击翻译按钮获取中文摘要

令和4年度では前年度の継続と第2段階に向けての基礎研究を行った。理論解析では、SBAアルゴリズムの計算量に関して、イデアルの正則性、半正則性の観点から文献調査を行い、イデアルがgenericなケースに関して、既存の理論の統一と整合性の確認を行った。令和４年度末時点では論文化されていないが、令和５年度の前半に論文化し、国際会議等での発表を予定している。第２段階と考えている「より一般的な形でのSBA理論」に関しては、非可換代数である交代代数におけるグレブナー計算にSBAを適用し、国内会議・国際会議での発表を行った。SBAアルゴリズムの実装とその有効性検証では、簡約操作の効率化をおこなった。SBAは、ブッフバーガー算法と同様にS多項式を中間基底で簡約することで計算が進行するが、S多項式の選択順序および簡約に条件がつくため、F4アルゴリズムのように、「一度に多くのS多項式を取り出して、それを簡約するのに十分なreducer(簡約につかう多項式) を用意してベクトル化を行い、最終的に行列の形に直した上で簡約を行う」という方法が取りにくい。そこで、SBAにおけるS多項式の選択順序に従って、毎回1つのS多項式を簡約するが、簡約自体はS多項式やreducerをベクトル化して、ベクトルに対する簡約で行う方法を考案した。計算機代数システムRisa/Asir上で計算実験を行い、全次数辞書式順序でのグレブナー基底計算において、最大10倍程度高速化する場合があることがわかった。応用研究では、多変数公開鍵暗号の安全性の基礎となるMQ問題と呼ばれる「連立２次多変数代数方程式の解を求める問題」をグレブナー基底計算を使って効率的に解くことを検討した。ここではF4型のアルゴリズムを適用し、MQ問題を効率良く解くためのS多項式選択方法を提案して、その効率性を数値実験的に確認した。