Binary Polynomial Explorer

Enter a polynomial using standard terms (x^2) and/or falling factorial terms (x^(2)). Standard terms are converted; falling factorial terms are kept as-is. Coefficients can be decimal or hex (0x1F). Ring exponent n with 1 ≤ n ≤ 64.

Polynomial

2ⁿ

Basis

Input syntax

x^3 → standard monomial x³
x^(3) → falling factorial x(x−1)(x−2)
0x1Fx^2 → hex coefficient (31x²)

Falling factorial notation

x⁽⁰⁾ = 1
x⁽¹⁾ = x
x⁽²⁾ = x(x − 1)
x⁽³⁾ = x(x − 1)(x − 2)

This tool implements ideas from [1] for reducing polynomials in the falling factorial basis.

Previous methods[2] for finding inverse permutation polynomials used Newton-Raphson method. This approach has significant limitations first of all it does not necessarily converge when the constant term is non-zero. Furthermore it requires complex manipulations of the polynomials.

This tool has no such limitations. The inversion algorithm works by using Hensel lifting to find solutions for the first min(2^n, n+2) points. e.g. for ℤ/2³ℤ: 5 points, (f⁻¹(0), 0), (f⁻¹(1), 1), ... , (f⁻¹(4), 4).

Then interpolating the flipped points (x, y) ↦ (y, x) result using Newton's forward difference formula. This results in the inverse polynomial in the falling factorial basis which can be cheaply reduced by masking coefficients using values dependent on ν₂(i!) where i is the degree of the monomial under consideration.

The reason this amount of points suffices is that the max degree of a binary polynomial (modulo null polynomials) is n + 1. So interpolating based on n + 2 points is always enough for binary polynomials. Or in the case of ℤ/2ℤ the whole image is sampled.

[1] Arnau Gàmez-Montolio, Enric Florit, Martin Brain, Jacob M. Howe. Efficient Normalized Reduction and Generation of Equivalent Multivariate Binary Polynomials Workshop on Binary Analysis Research (BAR 2024)

[2] Lucas Barthelemy, Ninon Eyrolles, Guénaël Renault, Raphaël Roblin. Binary Permutation Polyno- mial Inversion and Application to Obfuscation Techniques. 2nd International Workshop on Software Protection, Oct 2016, Vienna, Austria.