Spectral Modular Exponentiation
Gökay Saldamlı, Çetin Kaya Koç · Proceedings/Proceedings - Symposium on Computer Arithmetic · 2007
We describe a new method to perform the modular exponentiation operation, i.e., the computation of c = memod 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.