Inverting square systems algebraically is exponential

Jintai Ding CPS Lab, Chongqing University, China; Department of Mathematical Sciences, University of Cincinnati, USA Crystal Clough Department of Mathematical Sciences, University of Cincinnati, USA Roberto Araujo Faculdade de Computação, Universidade Federal do Pará, Brazil

Information Theory Algebraic Geometry mathscidoc:2207.19001

Finite Fields and Their Applications, 26, 32-48, 2014.3
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 = \Omega(n), where n is the number of variables of the system.
No keywords uploaded!
[ Download ] [ 2022-07-14 14:37:09 uploaded by dingjt ] [ 62 downloads ] [ 0 comments ]
@inproceedings{jintai2014inverting,
  title={Inverting square systems algebraically is exponential},
  author={Jintai Ding, Crystal Clough, and Roberto Araujo},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220714143709665790646},
  booktitle={Finite Fields and Their Applications},
  volume={26},
  pages={32-48},
  year={2014},
}
Jintai Ding, Crystal Clough, and Roberto Araujo. Inverting square systems algebraically is exponential. 2014. Vol. 26. In Finite Fields and Their Applications. pp.32-48. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220714143709665790646.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved