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 ~ N²logN, 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 N². 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 than standard techniques which scale as N³. The two new approaches are validated on several examples, including solid silicon and liquid water and demonstrated to be improvements on other reduced order nonlocal techniques. Indeed, the new methods have low overhead and become more efficient than the standard technique for ≥ 20 atoms. Both NLEES methods are shown to work stably and efficiently within the Car-Parrinello ab initio molecular dynamics framework due to the existence of p-2 continuous derivatives of a p^th order spline.