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

Gröbner基计算的理论复杂度分析及其高效实现

• 批准号: 21K03377
• 负责人: 横山 和弘
• 金额: $ 2.58万
• 依托单位: Rikkyo University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2021
• 资助国家: 日本
• 起止时间: 2021-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-21K03377/
• 关键词: 計算機代数; グレブナー基底; 多項式イデアル; 計算量解析

令和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多項式選択方法を提案して、その効率性を数値実験的に確認した。

2020财年，我们延续了上一年的工作，进行了第二阶段的基础研究。在理论分析中，我们从理想的正则性和半正则性的角度对SBA算法的计算复杂度进行了文献调查，并证实了现有理论对于理想泛型情况的统一性和一致性。虽然截至2020年底尚未以论文形式发表，但计划于2020年上半年发表并在国际会议上发表。关于第二步，“更一般形式的SBA理论”，我将SBA应用于交替代数（一种非交换代数）中的格罗布纳微积分，并在国内和国际会议上做了演讲。在实现SBA算法并验证其有效性的过程中，我们提高了化简运算的效率。与Buchberger算法类似，SBA的计算通过使用中间基约简S多项式来进行，但由于S多项式的选择顺序和约简附加了条件，因此它是足以采用多项式并约简它的一个约简器。很难用“准备一个矩阵，向量化，转化为矩阵，然后化简”的方法。因此，我们设计了一种方法，根据SBA中S多项式的选择顺序，每次约简一个S多项式，但约简本身是通过将S多项式和约简器转换为向量并对向量进行约简来执行的。我们在计算机代数系统 Risa/Asir 上进行了计算实验，发现采用全度词典排序的 Gröbner 基计算速度最高可达 10 倍。在应用研究中，我们研究了如何使用 Gröbner 基础微积分有效地解决 MQ 问题，该问题是寻找联立二次多元代数方程的解的问题，它是多元公钥密码学安全性的基础。在这里，我们应用F4型算法，提出了一种S多项式选择方法来有效地解决MQ问题，并通过数值实验证实了其有效性。

项目成果

Polynomial selection of F4 for solving the MQ problem

用于解决 MQ 问题的 <i>F</i>₄ 多项式选择

• DOI: 10.14495/jsiaml.14.135
• 发表时间: 2022
• 影响因子: 0.4
• 作者: Ito Takuma;Hoshi Yuta;Shinohara Naoyuki;Uchiyama Shigenori
• 通讯作者: Uchiyama Shigenori

Non-compatible な加群項順序の下でのsignature-based algorithm について

不兼容模块术语排序下基于签名的算法研究

• 发表时间: 2022
• 作者: 野呂正行

Solving the constructive Deuring correspondence via the Kohel-Lauter-Petit-Tignol algorithm

通过 Kohel-Lauter-Petit-Tignol 算法求解建设性 Deuring 对应关系

• 发表时间: 2021
• 作者: Kambe Yuta; Yasuda Masaya; Noro Masayuki; Yokoyama Kazuhiro; Aikawa Yusuke; Takashima Katsuyuki; Kudo Momonari
• 通讯作者: Kudo Momonari

Risa/Asir における種々の change of ordering algorithm の実装について

关于Risa/Asir中排序算法的各种变化的实现

• 发表时间: 2022
• 作者: 野呂正行

多変数多項式のパラメトリック因数分解

多元多项式的参数因式分解

• 发表时间: 2022
• 作者: 横山和弘