In many areas of engineering and applied mathematics, spectral methods provide
very powerful tools for solving and analyzing problems. For instance, large to
extremely large sizes of numbers can efficiently be multiplied by using discrete Fourier
transform and convolution property. Such computations are needed when computing
π to millions of digits of precision, factoring and also big prime search projects.
When it comes to the utilization of spectral techniques for modular operations
in public key cryptosystems two difficulties arise; the first one is the reduction needed
after the multiplication step and the second is the cryptographic sizes which are much
shorter than the optimal asymptotic crossovers of spectral methods.
In this dissertation, a new modular reduction technique is proposed. Moreover,
modular multiplication is given based on this reduction. These methods work fully
in the frequency domain with some exceptions such as the initial, final and partial
transformations steps. Fortunately, the new technique addresses the reduction problem
however, because of the extra complexity coming from the overhead of the forward and
backward transformation computations, the second goal is not easily achieved when
single operations such as modular multiplication or reduction are considered. On the
contrary, if operations that need several modular multiplications with respect to the
same modulus are considered, this goal is more tractable.
An obvious example of such an operation is the modular exponentiation i.e., the
computation of c=m[superscript e] mod n where c, m, e, n are large integers. Therefore following
the spectral modular multiplication operation a new modular exponentiation method is
presented. Since forward and backward transformation calculations do not need to be
performed for every multiplication carried during the exponentiation, the asymptotic
crossover for modular exponentiation is decreased to cryptographic sizes. The method
yields an efficient and highly parallel architecture for hardware implementations of
public-key cryptosystems. / Graduation date: 2006
| Identifer | oai:union.ndltd.org:ORGSU/oai:ir.library.oregonstate.edu:1957/28625 |
| Date | 23 May 2005 |
| Creators | Saldamli, Gökay |
| Contributors | Koc, Cetin K., Schmidt, Thomas A. |
| Source Sets | Oregon State University |
| Language | en_US |
| Detected Language | English |
| Type | Thesis/Dissertation |
Page generated in 0.0023 seconds