Disordered media with their numerous scattering channels can be used as optical operators. Measurements of the scattering tensor of a second-harmonic medium extend this computing application to the nonlinear regime. A complex scattering medium offers spatial mixing of the incoming waves via numerous randomly wired channels, making it act as a unique linear optical operator. However, its use as a nonlinear operator has been unexplored due to the difficulty in formulating the nonlinear wave-medium interaction. Here we present a theoretical framework and experimental proof that a third-order scattering tensor completely describes the input-output response of a nonlinear scattering medium made of second-harmonic-generation nanoparticles. The rank of the nonlinear scattering tensor is higher than that of a second-order scattering tensor describing a linear scattering medium, scaling with the number of the spatially orthogonal illumination channels. We implement the inverse of the nonlinear scattering tensor by tensor reshaping and minimization operation, which enables us to retrieve the original incident wave from the speckled nonlinear wave. Using the increased rank of the scattering tensor along with its inverse operation, we demonstrate that the disordered nonlinear medium can be used as a highly scalable nonlinear optical operator for optical encryptions, all-optical multichannel logic AND gates, and optical kernel methods in machine learning.