تقرير
Semi-regular sequences and other random systems of equations
| العنوان: | Semi-regular sequences and other random systems of equations |
|---|---|
| المؤلفون: | Bigdeli, M., De Negri, E., Dizdarevic, M. M., Gorla, E., Minko, R., Tsakou, S. |
| سنة النشر: | 2020 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Cryptography and Security, Mathematics - Commutative Algebra, Primary: 94A60, 13P10, 13P15, 13P25, Secondary: 13D40 |
| الوصف: | The security of multivariate cryptosystems and digital signature schemes relies on the hardness of solving a system of polynomial equations over a finite field. Polynomial system solving is also currently a bottleneck of index-calculus algorithms to solve the elliptic and hyperelliptic curve discrete logarithm problem. The complexity of solving a system of polynomial equations is closely related to the cost of computing Groebner bases, since computing the solutions of a polynomial system can be reduced to finding a lexicographic Groebner basis for the ideal generated by the equations. Several algorithms for computing such bases exist: We consider those based on repeated Gaussian elimination of Macaulay matrices. In this paper, we analyze the case of random systems, where random systems means either semi-regular systems, or quadratic systems in n variables which contain a regular sequence of n polynomials. We provide explicit formulae for bounds on the solving degree of semi-regular systems with m > n equations in n variables, for equations of arbitrary degrees for m = n+1, and for any m for systems of quadratic or cubic polynomials. In the appendix, we provide a table of bounds for the solving degree of semi-regular systems of m = n + k quadratic equations in n variables for 2 <= k; n <= 100 and online we provide the values of the bounds for 2 <= k; n <= 500. For quadratic systems which contain a regular sequence of n polynomials, we argue that the Eisenbud-Green-Harris Conjecture, if true, provides a sharp bound for their solving degree, which we compute explicitly. Comment: 27 pages, 4 tables |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2011.01032 |
| رقم الأكسشن: | edsarx.2011.01032 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |