An improvement of algorithms to solve under-defined systems of multivariate quadratic equations

DOI10.14495/JSIAML.15.53MaRDI QIDQ6139474zbMATH OpenOpenAlexFDO

Authors Yasufumi Hashimoto

Publication date 19 December 2023

Published in JSIAM Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.14495/jsiaml.15.53

zbMATH Keywords

MQ problemmultivariate quadratic equationsunder-defined systems

Mathematics Subject Classification ID

Numerical computation of solutions to systems of equations (65H10)

Recommendations

• Extended algorithm for solving underdefined multivariate quadratic equations
• A polynomial-time algorithm for solving a class of underdetermined multivariate quadratic equations over fields of odd characteristics
• Solving underdetermined systems of multivariate quadratic equations revisited
• scientific article; zbMATH DE number 2085432
• Efficient algorithms for solving overdefined systems of multivariate polynomial equations

Cites work

• A new efficient algorithm for computing Gröbner bases (F₄)
• A polynomial-time algorithm for solving a class of underdetermined multivariate quadratic equations over fields of odd characteristics
• Comparison Between XL and Gröbner Basis Algorithms
• Complexity of problems in games, graphs and algebraic equations
• Extended algorithm for solving underdefined multivariate quadratic equations
• scientific article; zbMATH DE number 2085432 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Improving Thomae-Wolf algorithm for solving underdetermined multivariate quadratic polynomial problem
• Solving polynomial systems over finite fields: improved analysis of the hybrid approach
• Solving quadratic equations with XL on parallel architectures
• Solving underdetermined systems of multivariate quadratic equations revisited
• Unbalanced Oil and Vinegar Signature Schemes

Cited in

(7)

• An improved algorithm for quadratic equation classification and Petrov classification
• Improved cryptanalysis of SNOVA
• A correct justification for the CHMT algorithm for solving underdetermined multivariate systems
• A simple noncommutative UOV scheme
• Wedges, oil, and vinegar. An analysis of UOV in the exterior algebra
• Post-quantum multivariate signature scheme QR-UOV: security, parameters, and implementations
• Explicit bounds on the existence probability of random multivariate quadratic systems over finite fields

This page was built for publication: An improvement of algorithms to solve under-defined systems of multivariate quadratic equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6139474)