Date of Award
2012
Publication Type
Master Thesis
Degree Name
M.A.Sc.
Department
Electrical and Computer Engineering
Keywords
Crytpography, High-Speed, Mersenne Prime, Modular, Multiplication, Reduction
Supervisor
Huapeng Wu
Supervisor
Majid Ahmadi
Rights
info:eu-repo/semantics/openAccess
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Abstract
The work contained in this thesis is a representation of the successful attempt to speed-up the modular reduction as an independent step of modular multiplication, which is the central operation in public-key cryptosystems. Based on the properties of Mersenne and Quasi-Mersenne primes, four distinct sets of moduli have been described, which are responsible for converting the single-precision multiplication prevalent in many of today's techniques into an addition operation and a few simple shift operations. A novel algorithm has been proposed for modular folding. With the backing of the special moduli sets, the proposed algorithm is shown to outperform (speed-wise) the Modified Barrett algorithm by 80% for operands of length 700 bits, the least speed-up being around 70% for smaller operands, in the range of around 100 bits.
Recommended Citation
Sreehari, Suhas, "Fast Modular Reduction for Large-Integer Multiplication" (2012). Electronic Theses and Dissertations. 5360.
https://scholar.uwindsor.ca/etd/5360