Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

Semi-Regular Sequences and Other Random Systems of Equations

Abstract : 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 Gröbner bases, since computing the solutions of a polynomial system can be reduced to finding a lexicographic Gröbner 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 ≤q k, n ≤q 100 and online we provide the values of the bounds for 2 ≤q k, n ≤q 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. \textcopyright 2021, The Author(s), under exclusive license to Springer Nature Switzerland AG.
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal-u-picardie.archives-ouvertes.fr/hal-03682202
Contributeur : Louise DESSAIVRE Connectez-vous pour contacter le contributeur
Soumis le : lundi 30 mai 2022 - 19:02:53
Dernière modification le : mardi 31 mai 2022 - 03:00:17

Lien texte intégral

Identifiants

Collections

Citation

M. Bigdeli, E. de Negri, M.M. Dizdarevic, E. Gorla, R. Minko, et al.. Semi-Regular Sequences and Other Random Systems of Equations. Association for Women in Mathematics Series, 2021, 24, pp.75--114. ⟨10.1007/978-3-030-77700-5_3⟩. ⟨hal-03682202⟩

Partager

Métriques

Consultations de la notice

0