Sunday, 11 August 2013

Improving Montgomery product

Improving Montgomery product

I am reading the paper "A Cryptographic Library for the Motorola DSP56000"
(http://link.springer.com/content/pdf/10.1007%2F3-540-46877-3_21.pdf)
which describes a trick to speed-up calculation of the Montgomery product.
What I don't get is the improvement step (between the two algorithms at
the end). All parameters are separated into words and the improvement step
says that instead of $N'$ it is enough to only use $n'_0$ (the first word
of $N'$). So the rest of $N'$ is not needed! What??!!
Can someone please give me some hints, why is this the case?

No comments:

Post a Comment