Spectral Modular Exponentiation

We describe a new method to perform the modular exponentiation operation, i.e., the computation of c = m^e mod n, where c, m, e and n are large integers. The new method uses the discrete Fourier transform over a finite ring, and relies on new techniques to perform multiplication and reduction operations. The method yields efficient and highly parallel architectures for hardware realizations of public-key cryptosystems requiring the modular exponentiation as the core computation, such as the RSA and Diffie-Hellman algorithms.