Re: Problem with Montgomery product

From: Tom St Denis (tomstdenis_at_iahu.ca)
Date: 05/28/04 

Date: Fri, 28 May 2004 11:27:45 GMT

Giovanni Parodi wrote:
> Hello everybody, I am an italian student and I have a problem with the
> MonPro algorithm.
> I read the paper "Analyzing and Comparing Montgomery Multiplication
> Algorithms" because it's considered the better paper about this
> argument freely available on the web (also in this NG it's often
> referenced).
> In this paper I found that it's possible to use the least significant
> word of n' (indicated as n'0), instead of n'. I don't understand why
> it's possibile to do that. I tried to read the paper "A cryptographic
> library for the Motorola DSP56000" (in which this trick has been
> proposed), but I didn't understand the short explication given about
> this argument.
> I will appreciate your help. I think that the explanation is not very
> difficult (because I didn't find a paper with an explicit explanation
> of this topic), but I wasn't able to find it.
> If possible can you give also a little example? Thanks a lot

I have an implementation and explanation of how Montgomery reduction
works in my LTM package [tommath.pdf in the archive]. It should help
explain how the basic algorithm works from which you can figure out
MontPro rather easily.

Tom

Relevant Pages

  • Re: What I learned from Class Viewer
    ... displaced by such a trivially easy algorithm? ... as the distance information dropped away. ... by simply assuming that the weight is a distance between nodes ... There isn't anything more I can do besides the general explanation, ...
    (comp.lang.java.programmer)
  • RE: Cosine of 90 degrees
    ... Computers work in binary is part of the explanation. ... The algorithm used doesn't address 0 specifically, ... Excel 07, XPPro SP3. ...
    (microsoft.public.excel.worksheet.functions)
  • Re: Distinct issues
    ... explanation of why code would have so many SELECT DISTINCT at all ... levels of nesting? ... do you know if there is a tool or algorithm that will ... find if a query returns duplicate rows or not for the general case? ...
    (microsoft.public.sqlserver.programming)
  • Re: Lexicons
    ... > Is there an algorithm for computing the shortest representation of a ... > given sequence of digits? ... > have no short explanation, and yet x is not normal? ... Normality is not necessarily connected with randomness, ...
    (sci.math)