权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

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

In the fourth year, the second stage of the research was carried out. Theoretical analysis is related to the calculation of SBA classification, regularity and semi-regularity, literature investigation, generic classification, and confirmation of the unity of existing theories. At the end of the fourth year, the discussion on culture and international conferences will be held in the first half of the fifth year. The second stage of the study is "general shape of SBA theory" related to non-commutative algebra, accounting algebra, calculation of SBA, application of domestic conferences and international conferences. The SBA has a simple operation and a simple efficiency. SBA, SBA, SBA algorithm, SBA algorithm, SBA algorithm,(Simple polynomial) The order of selection of S polynomials in SBA and SBA is discussed. The S polynomials in SBA and SBA are reduced. The reduction of S polynomials in SBA and SBA is discussed. Computational algebra is based on Risa/Asir, and the calculation is performed in the order of full degree dictionary formula. The calculation speed is increased by 10 times at most. A study on the basis of security of open keys with multiple variables is presented in this paper. This is the first time that we've seen a good solution to the MQ problem.

项目成果

期刊论文数量（17）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

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

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

DOI：
发表时间：
2021
期刊：
影响因子：
0
作者：
Kambe Yuta;Yasuda Masaya;Noro Masayuki;Yokoyama Kazuhiro;Aikawa Yusuke;Takashima Katsuyuki;Kudo Momonari
通讯作者：
Kudo Momonari

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

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