Exact relation between nonlinearity and algebraic immunity

Boolean functions have found a widespread use in cryptography. In connection with the advent of the ‘algebraic’ attack on stream ciphers, the Boolean functions, which are used in these ciphers as nonlinear filters, have to possess, among other properties, high algebraic immunity. One more cryptographically significant property of Boolean functions, especially of those utilised in stream ciphers, is nonlinearity. In this connection, the question arises about relations between the nonlinearity of a Boolean function and its algebraic immunity.
In this research we obtain a lower bound for nonlinearity in terms of algebraic immunity and present functions at which this bound is attained for any admissible values of the parameters.