TY - JOUR
T1 - Inverting square systems algebraically is exponential
AU - Ding, Jintai
AU - Clough, Crystal
AU - Araujo, Roberto
PY - 2014
Y1 - 2014
N2 - 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 q=Ω(n), where n is the number of variables of the system.
AB - 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 q=Ω(n), where n is the number of variables of the system.
KW - Degree of regularity
KW - HFE
KW - Square
UR - http://www.scopus.com/inward/record.url?scp=84888194273&partnerID=8YFLogxK
U2 - 10.1016/j.ffa.2013.10.004
DO - 10.1016/j.ffa.2013.10.004
M3 - Article
AN - SCOPUS:84888194273
SN - 1071-5797
VL - 26
SP - 32
EP - 48
JO - Finite Fields and their Applications
JF - Finite Fields and their Applications
ER -