# Degree of a big S-box

Assume we have a big S-box (i.e. $15*15$). We have truth table of it. (so $2^{15}$ output). How can we find its degree without using Algebraic Normal Form of its Boolean functions. Or with ANF, can you help me to write the algorithm of implementing.

Take the field with $2^{15}$ elements, identify its elements with 15-bit 0/1-strings (in any linear way -- the polynomials will be dependent on the choice, but not the resulting maximal Hamming weight) and find the polynomial $p(X)$ of degree $2^{15}-1$ with $p(x) = S[x]$ for all $2^{15}$ values $x$ via Lagrange or Newton interpolation. If $p(X) = \sum_{i=0}^{2^{15}-1} p_i X^i$ then the degree you are looking for is the maximum of all Hamming weights (= number of zeros in binary representation) of exponents $i$ where $p_i\ne 0$.
So if for example $p(X) = p_7 X^7 + p_{257} X^{257}$ with $p_7\ne 0$, $p_{257}\ne 0$ then the degree is $3$, as maximum of Hamming weight(7) = Hamming weight($2^2+2^1+2^0$) = 3 and Hamming weight(257) = Hamming weight($2^8+2^0$) = 2.