Computational Equivalence Between Mutant Strategies and Normal Selection in Algebraic Cryptanalysis

• SheshuKumar Vangala

  Author

This document explores the relationship between mutant-based selection in the Mutant eXtended Linear Algebra (MXL) procedure and degree-stratified critical-pair selection in the F 4 procedure for Gröbner basis computation. It develops a conditional procedural equivalence, relying on several assumptions: input ideal, coefficient field, monomial ordering, critical-pair generation and reduction procedures, and termination criteria. It then shows that if mutant prioritization only changes the order of processing of some fixed set of selected rows, and both procedures perform complete S-pair termination tests, then either procedure produces the same reduced Gröbner basis. It also looks at when the set of nonzero S-polynomials that show up together will be smaller than the set of mutants that show up together, if you swap one set in for the other. It postulates that full reduction and mutant termination testing may be insufficient for Gröbner basis completion, as nonzero S-polynomials can remain without a complete mutant set. It also describes a concept of partial enlargement as a restricted selection heuristic, without claiming equivalence with the known delayed criterion. This paper helps clarify the differences between selection heuristics and Gröbner basis completeness criteria, and is not intended to prove equivalence unconditionally for all MXL algorithms, asymptotic complexity equivalence, or performance correlation.

• PDF

Copyright (c) 2026 International Journal of Intelligent Systems and Data Science

This work is licensed under a Creative Commons Attribution 4.0 International License.