City Research Online

Abstract

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 - https://www.ndss-symposium.org/ndss-paper/auto-draft-436/
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:	Symplectic Administrator

Export

Downloads