City Research Online

Efficient Normalized Reduction and Generation of Equivalent Multivariate Binary Polynomials

Gàmez Montolio, A., Florit, E., Brain, M. ORCID: 0000-0003-4216-7151 & Howe, J. ORCID: 0000-0001-8013-6941 (2024). Efficient Normalized Reduction and Generation of Equivalent Multivariate Binary Polynomials. Paper presented at the Workshop on Binary Analysis Research, 1 Mar 2024, San Diego, USA. doi: 10.14722/bar.2024.23014


Polynomials over fixed-width binary numbers (bytes, ℤ/2ωℤ, bit-vectors, etc.) appear widely in computer science including obfuscation and reverse engineering, program analysis, automated theorem proving, verification, errorcorrecting codes and cryptography. As some fixed-width binary numbers do not have reciprocals, these polynomials behave differently to those normally studied in mathematics. In particular, polynomial equality is harder to determine; polynomials having different coefficients is not sufficient to show they always compute different values. Determining polynomial equality is a fundamental building block for most symbolic algorithms. For larger widths or multivariate polynomials, checking all inputs is computationally infeasible. This paper presents a study of the mathematical structure of null polynomials (those that evaluate to 0 for all inputs) and uses this to develop efficient algorithms to reduce polynomials to a normalized form. Polynomials in such normalized form are equal if and only if their coefficients are equal. This is a key building block for more mathematically sophisticated approaches to a wide range of fundamental problems.

Publication Type: Conference or Workshop Item (Paper)
Additional Information: Originally published by the Internet Society -
Subjects: Q Science > QA Mathematics
Departments: School of Science & Technology
School of Science & Technology > Computer Science
School of Science & Technology > Computer Science > Software Reliability
SWORD Depositor:
[thumbnail of bar2024-7.pdf]
Text - Published Version
Download (379kB) | Preview


Add to AnyAdd to TwitterAdd to FacebookAdd to LinkedinAdd to PinterestAdd to Email


Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login