A surface plasmon that is excited on the interface separating a metal and a nonlinear semiconductor has a propagation constant that depends on the power carried by the plasmon. We present an analytic expression for the change in the propagation constant of the plasmon,K&Dgr;&bgr;, as a function of the dielectric constants of the two media, the nonlinear refractive index of the semiconductor,n2,E, and the power carried by the plasmon. We define a figure of merit,P0, which is the power required for shifting the phase of the plasmon by &pgr;/2 along a distanceS, (S= 1/2&agr;, where &agr; is the plasmon decay constant), and find the wavelength dependence ofK&Dgr;&bgr; andP0.