# Blockwise Montgomery multiplication

I have to implement a 256*256 bit Montgomery multiplier for pairing computations. The straightforward approach is to use a bit-serial version, but I would like to utilize the built-in 64*64 bits multipliers on soft cores of modern FPGA devices, therefore I need a blockwise implementation (64 bits each). Two choices for implementation are:

1. Get a 512-bit product and then apply Montgomery reduction.
2. Reduce the intermediate products (128 bits) in each step using Montgomery reduction.

Which strategy is faster? If intermediate results are reduced in each step, then what should be the value of $R$: is it $2^{256}$ or $2^{64}$?

-
This question is about implementation of Montgomery multiplier, which is commonly a component used for implementation of asymmetric cryptography. However, such components do not usually belong to this site. I propose migrating question to appropriate generic programming discussion, such as stackoverflow.com. –  user4982 Oct 14 '13 at 15:15
@user4982 This is an algorithm question rather than a coding question. While not about cryptography specifically, it is about a subject (bignums) for which cryptography is one of the main use cases. Therefore I think the question is fine here. –  Gilles Oct 14 '13 at 17:53

As I said above, I feel the question is bit off-topic here. However, there does not seem to be too good a place in SE for questions that combine mathematics and programming on VHDL, where target is obviously something cryptography related. Most questions regarding FPGA are seen in electronics.stackexchange.com.

Montgomery reduction in Wikipedia is useful description of Montgomery reduction. The value of R you usually use is the same than word size used in processing. In your case, it could be $2^{256}$ or $2^{64}$ depending on how you implement the montgomery multiplier. If you have multiple $64*64$ bit multiplier units, you may want to use them in parallel, to perform large multiplications and/or montgomery reductions at once.

Assuming you had two multipliers available, one way around this would be using one multiplier for 64*64 multiply and another for montgomery reduction of previous 64*64 multiply, and thus R would be $2^{64}$. Then you would need to build 256*256 from e.g. 16 executions of 64*64 multiply. But, the algorithm, approach and processing pattern somewhat depends on how many multiplier you have available. Notice that you do not need to use rectangular size: you may build 128*64 montgomery step (from e.g. 4 multipliers) and you can use it to build 256*256.

The speed of different implementation decisions in the end depend on your target platform. Likely you need to design and implement appropriate benchmarks yourself.

Coming back to the original question. Overall, it is often most efficient to work locally i.e. inside one 64 bit / 128 bit word, i.e. to try to constrain each handling path to process word at time. (I.e. choice 2.) Note: you cannot restrict all operations to work in 128-bits, but occasionally need to handle carries etc. concerns.