  An algorithm for computing the nonlinearity of a Boolean function from its
algebraic normal form (ANF) is proposed. By generalizing the expression of the
weight of a Boolean function in terms of its ANF coefficients, a formulation of
the distances to linear functions is obtained. The special structure of these
distances can be exploited to reduce the task of nonlinearity computation to
solving an associated binary integer programming problem. The proposed
algorithm can be used in cases where applying the Fast Walsh transform is
infeasible, typically when the number of input variables exceeds 40.
