This paper presents efficient algorithms for solving overdefined systems of multivariate polynomial equations, focusing on the relinearization and XL (eXtended Linearization) techniques. The security of many cryptographic systems relies on the difficulty of solving such systems, which is NP-hard. For systems with equal numbers of equations and variables, known algorithms include exhaustive search for small fields and Gröbner bases for larger fields, but these are inefficient for large systems. The relinearization technique, introduced by Kipnis and Shamir, aims to solve overdefined systems with more equations than variables. It generates additional nonlinear equations to handle dependencies, but its exact complexity is not well understood. The authors analyze the theoretical and practical aspects of relinearization, finding that many generated equations are linearly dependent, reducing its efficiency. They then introduce the XL algorithm, which is both simpler and more powerful than relinearization. XL generates higher-degree variants of each polynomial equation and linearizes the expanded system, leading to polynomial time complexity for sufficiently overdefined systems. The paper also discusses experimental results showing that XL can solve systems with a number of equations exceeding the number of variables by a small amount in subexponential time. The XL algorithm is shown to be more efficient than relinearization, as it can solve systems with fewer variables and equations. The authors also compare XL with Gröbner bases algorithms, demonstrating that XL is more practical for solving overdefined systems. The paper concludes that the complexity of solving systems of multivariate equations decreases rapidly when the number of equations exceeds the number of variables. For systems with m ≥ εn², the complexity is polynomial with an exponent of O(1/√ε). The FXL algorithm is introduced as an extension of XL, which fixes a small number of variables to reduce the problem to a slightly overdefined system, potentially leading to subexponential time complexity. The paper also discusses the application of these techniques to cryptanalysis of the HFE cryptosystem, showing that XL and relinearization attacks can be effective against certain instances.This paper presents efficient algorithms for solving overdefined systems of multivariate polynomial equations, focusing on the relinearization and XL (eXtended Linearization) techniques. The security of many cryptographic systems relies on the difficulty of solving such systems, which is NP-hard. For systems with equal numbers of equations and variables, known algorithms include exhaustive search for small fields and Gröbner bases for larger fields, but these are inefficient for large systems. The relinearization technique, introduced by Kipnis and Shamir, aims to solve overdefined systems with more equations than variables. It generates additional nonlinear equations to handle dependencies, but its exact complexity is not well understood. The authors analyze the theoretical and practical aspects of relinearization, finding that many generated equations are linearly dependent, reducing its efficiency. They then introduce the XL algorithm, which is both simpler and more powerful than relinearization. XL generates higher-degree variants of each polynomial equation and linearizes the expanded system, leading to polynomial time complexity for sufficiently overdefined systems. The paper also discusses experimental results showing that XL can solve systems with a number of equations exceeding the number of variables by a small amount in subexponential time. The XL algorithm is shown to be more efficient than relinearization, as it can solve systems with fewer variables and equations. The authors also compare XL with Gröbner bases algorithms, demonstrating that XL is more practical for solving overdefined systems. The paper concludes that the complexity of solving systems of multivariate equations decreases rapidly when the number of equations exceeds the number of variables. For systems with m ≥ εn², the complexity is polynomial with an exponent of O(1/√ε). The FXL algorithm is introduced as an extension of XL, which fixes a small number of variables to reduce the problem to a slightly overdefined system, potentially leading to subexponential time complexity. The paper also discusses the application of these techniques to cryptanalysis of the HFE cryptosystem, showing that XL and relinearization attacks can be effective against certain instances.