~~CMPE 691a Advanced Arithmetic Algorithms
CMPE 691 A Advanced Arithmetic Algorithms
Instructor : Dhananjay S. Phatak
Office : ITE 327
email : firstname.lastname@example.org
Class Room and Time : Tu Th 1 pm via blackboard course room
Office Hours : TBD and by apt
course web-site :
Textbook : None.
Appropriate material (articles from the
literature, web pages....)
will be provided.
Most of the topics will be selected from the following list
(We might deviate and study some other topics (such as
AKS and other most recent primality testing algorithms, etc.)
upon the interests of the students and the instructor).
- Introduction: RSA encryption/decryption, Fermat's Little Theorem,
Euler Totient Theorem
- Conventional Residue Number Systems (RNS)
Sets of viewgraphs
- Advanced topics in Residue Number Systems.
Our recent work on (RNS)
Older version of the document (RNS)
- Fast arithmetic for large (cryptographic) wordlengths
- multi-digit multiplication : Karatsubba, Toom-Cook
FFT multiply methods, 3-primes FFT multiplication method
FFT Multiply Viewgraphs JJ 1
FFT Multiply Viewgraphs JJ 2
FFT Multiply Viewgraphs Umass
FFT Multiply Viewgraphs set 4
FFT Multiply Viewgraphs set 5
3 primes FFT Multiply Viewgraphs
- Modular Reducction : Barrett method, Montgomery algorithms
linear, cyclic and negacyclic convolutions,
Further optimization based on Montgomery Methods.
- other topics (time permitting) Fully and Partially
Homomorphic Encryption (and Decryption)
- Get familiar with software package Maple
It will be
used fairly heavily.
Participation in class discussions about
open problems and/or a Term Project and/or a final exam.
Goals of the Course :
Exposure to research in new computing needs and paradigms...
Prerequisites : 419/645 or permission of the instructor.