Montgomery Modular Multiplier

#Montgomery Modular Multiplier

##Design

We initially decided to use std_logic_vectors for out inputs and outputs, however we were having issues with the shift modules and the these types. We decided to move towards using std_numeric types and they are the ieee standards and reportedly have less issues with shifting. This required some more work on getting the correct type conversions working to use the shift_left and shift_right functions. We initially started using loops to get the operation to work, however this was unsuccessful due to loops in VHDL being parallel operators not sequential. We addressed this problem by using case statements and a "state" variable to ensure that the correct number of shift operations occur

###Issues

We had a few issues:

• Initially we wanted the operation to be asynchronous however this has been an issue due to recursion in sensitivity list. Currently we have it clocked (runs on the rising edge), if we have time we want to make the entire operation asynchronous to make it more optimal.
• Parallel loops -- this was resolved early on and was a mistake we should have been able to avoid from the start of the project.
• Reducing the shift-add operations from two dependent clock cycles to a single clock cycle i.e. doing prelim checking of add operation results with a simple if-statement xor.

###Current Design

• Execution time is (WIDTH_IN + 1)*C_CYCLE
  • The extra cycle is for latching the data when state = '0'. It may be possible to cut down on the number of cycles if A < N && B < N for the operation A*B MOD N -- however more research may need to see if this is actually faster of it is simple a "fake" effect of VHDL simulation vs synthesis.
• Behavioral description that uses a single process block to "loop" over the bits in the B operand.
• Uses add-shift for the multiple and modulo operation in a single step, i.e. removes the need for both shift-add and shift-subtract for multiplication and division respectively.

###Testing

• Currently initial tests have been run for "proof of concept" and such that it works for a single remainder case.
• We will be running two initial testing methods for proof of correctness. First we will write a testbench to execute and confirm the correct results from the VHDL file for simple results.
  • For more complex results we will compare the answer to a simple C or Python program that will perform the operation since we know that both the * and MOD operator have been verified in these languages. Although we will no be able to test every case, finding a strong set of tests for various DATA_IN lengths will be important