Modular arithmetic is commonly used in cryptographic schemes such as elliptic curve cryptography. A modular number system can represent whole numbers in the range 0 up to some value p-1, where p is the modulus. Modular number systems wrap around. For example, if the modulus is 7, then (4 + 6) mod 7 = 10 mod 7 = 3. In cryptographic systems the modulus may be large, such as a 256, 512, or 1024-bit number.
Modular multiplication is a particularly expensive operation. We multiply two numbers, each in the range 0 to p-1, giving us a product between 0 and (p-1)^2. We need to reduce this product mod p. There are several strategies for reducing the product. In the “interleaved” strategy, we interleave adding partial products and reducing mod p.
The goal of this project is to design interleaved modular multiplication circuits. There is a design space of possible designs and variants each with their own strengths and weaknesses, which I have written down in a document. The project should design several interleaved multipliers and compare them.
This project would suit a student with an interest in the design of algorithms for computer arithmetic. Ideally you will already be familiar with the basics of hardware multiplication, such as Booth recoding and Wallace/Dadda multipliers. The most likely tool for implementing these circuits is Vivado from Xilinx/AMD. The student needs to have existing experience of designing circuits, and be confident to work independently with the hardware design tools.