An Euler exponential spline (EES) based formalism is employed to derive new expressions for the electron-atom nonlocal pseudopotential interaction (NL) in electronic structure calculations performed using a plane wave basis set that can be computed more rapidly than standard techniques. Two methods, one that is evaluated by switching between real and reciprocal space via fast Fourier transforms, and another that is evaluated completely in real space, are described. The reciprocal-space or g-space-based technique, NLEES-G, scales as NMlogM approximately N2logN, where N is the number of electronic orbitals and M is the number of plane waves. The real-space based technique, NLEES-R, scales as N2. The latter can potentially be used within a maximally spatially localized orbital method to yield linear scaling, while the former could be employed within a maximally delocalized orbital method to yield NlogN scaling. This behavior is to be contrasted with standard techniques, which scale as N3. The two new approaches are validated using several examples, including solid silicon and liquid water, and demonstrated to be improvements on other, reduced-order nonlocal techniques. Indeed, the new methods have a low overhead and become more efficient than the standard technique for systems with roughly 20 or more atoms. Both NLEES methods are shown to work stably and efficiently within the Car-Parrinello ab initio molecular dynamics framework, owing to the existence of p-2 continuous derivatives of a pth-order spline.