~~CMPE 691a Advanced Arithmetic Algorithms   CMPE 691 A Advanced Arithmetic Algorithms
Spring 2021

Instructor : Dhananjay S. Phatak
Office : ITE 327
Phone : 410--455--3624
email : phatak@umbc.edu

Class Room and Time : Tu Th 1 pm via blackboard course room
Office Hours : TBD and by apt    course web-site : http://www.csee.umbc.edu/~phatak/691a

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.) depending 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.

Evaluation :
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.