Inverting square systems algebraically is exponential

详细信息    查看全文

• 作者：Jintai Ding ; Crystal Clough ; Roberto Araujo
• 关键词：94A60 ; 14G50 ; 13P15 ; 03D15
• 刊名：Finite Fields and Their Applications
• 出版年：March, 2014
• 年：2014
• 卷：26
• 期：Complete
• 页码：32-48
• 全文大小：252 K

文摘

In this paper, we prove that the degree of regularity of square systems, a subfamily of the HFE systems, over a prime finite field of odd characteristic q is exactly q and, therefore, prove that inverting square systems algebraically using Gr枚bner basis algorithm is exponential, when , where n is the number of variables of the system.