Question

Which of the following algorithms has better computational complexity than standard division algorithms?

(a) Montgomery algorithm

(b) Classical modular exponentiation algorithm

(c) ASM algorithm

(d) FSM algorithm

I got this question in an international level competition.

I need to ask this question from Number Theory in division Number Theory and Cryptography of Discrete Mathematics

Answer 1

The correct answer is (b) Classical modular exponentiation algorithm

The best I can explain: To multiply m and n, they are converted to Montgomery form: mR mod X and nR mod X. When multiplied, these produce mnR^2 mod X, and the Montgomery reduction produces abR mod N which is the Montgomery form of the desired product. After that, the low bits are discarded which gives a result less than 2X. One final subtraction reduces this to less than X. Hence, this procedure can have a better computational complexity than standard division algorithms.