Prev: Rendering prediction of congruential random number generators hard
Next: Hey guys, what is this all about? MQQ digital signature scheme?
From: yawnmoth on 25 Oct 2009 12:31
According to <http://en.wikipedia.org/wiki/
Computational_complexity_of_mathematical_operations>, division, if
implemented with Newton's method, has a complexity equal to that of
whatever multiplication algorithm is in use. The article on Newton's
method elaborates: "Newton–Raphson division ... can be used to quickly
find the reciprocal of a number using only multiplication and
subtraction."

My question is... what's the point of using Montgomery reduction in
modular exponentiation if Newton–Raphson division can implement
division efficiently, as well? Montgomery reduction, similarly, uses
just multiplication and addition / subtraction. It does some bit
shifting (or string shifting if you're using base-10 strings, I
guess), as well, but that's pretty inconsequential.
From: Paul Rubin on 25 Oct 2009 13:15
yawnmoth <terra1024(a)yahoo.com> writes:
> My question is... what's the point of using Montgomery reduction in
> modular exponentiation if Newton-Raphson division can implement
> division efficiently, as well?

Montgomery reduction is for efficiently multiplying modulo N where N
is not a power of 2. Basically you do a pre-transformation, then do
the entire exponentiation (a whole lot of multiplications) modulo
2**b, then undo the transformation. Reducing mod 2**b is of course
trivial since you just chop all the bits above the b'th bit.
From: Mok-Kong Shen on 25 Oct 2009 13:28
yawnmoth wrote:
> According to <http://en.wikipedia.org/wiki/
> Computational_complexity_of_mathematical_operations>, division, if
> implemented with Newton's method, has a complexity equal to that of
> whatever multiplication algorithm is in use. The article on Newton's
> method elaborates: "Newton�Raphson division ... can be used to quickly
> find the reciprocal of a number using only multiplication and
> subtraction."
>
> My question is... what's the point of using Montgomery reduction in
> modular exponentiation if Newton�Raphson division can implement
> division efficiently, as well? Montgomery reduction, similarly, uses
> just multiplication and addition / subtraction. It does some bit
> shifting (or string shifting if you're using base-10 strings, I
> guess), as well, but that's pretty inconsequential.

I could gravely err, but isn't it that the "normal" Newton method
can't work on integer numbers in a residue system (i.e. mod N)?

M. K. Shen
From: yawnmoth on 25 Oct 2009 15:26
On Oct 25, 12:15 pm, Paul Rubin <http://phr...(a)NOSPAM.invalid> wrote:
> yawnmoth <terra1...(a)yahoo.com> writes:
> > My question is...  what's the point of using Montgomery reduction in
> > modular exponentiation if Newton-Raphson division can implement
> > division efficiently, as well?
>
> Montgomery reduction is for efficiently multiplying modulo N where N
> is not a power of 2.  Basically you do a pre-transformation, then do
> the entire exponentiation (a whole lot of multiplications) modulo
> 2**b, then undo the transformation.  Reducing mod 2**b is of course
> trivial since you just chop all the bits above the b'th bit.

I'm familiar with how montgomery reduction is used... the thing is,
it seems to me that montgomery reduction and newton-raphson division
have about the same time complexity.

You use montgomery reduction because it's faster than division, in
theory. Doing 1x pre-transformation, 1x montgomery reduction, and 1x
post-transformation is more expensive than doing 1x division, but
doing 1x pre-transformation, 2x montgomery reductions, and 1x post-
transformations is cheaper than doing 2x divisions, and so on.

But, as I said, if newton-raphson division and the montgomery
reduction have the same time complexity, I don't see the advantage.
From: yawnmoth on 25 Oct 2009 15:46
On Oct 25, 12:28 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote:
> yawnmoth wrote:
> > According to <http://en.wikipedia.org/wiki/
> > Computational_complexity_of_mathematical_operations>, division, if
> > implemented with Newton's method, has a complexity equal to that of
> > whatever multiplication algorithm is in use.  The article on Newton's
> > method elaborates: "Newton–Raphson division ... can be used to quickly
> > find the reciprocal of a number using only multiplication and
> > subtraction."
>
> > My question is...  what's the point of using Montgomery reduction in
> > modular exponentiation if Newton–Raphson division can implement
> > division efficiently, as well?  Montgomery reduction, similarly, uses
> > just multiplication and addition / subtraction.  It does some bit
> > shifting (or string shifting if you're using base-10 strings, I
> > guess), as well, but that's pretty inconsequential.
>
> I could gravely err, but isn't it that the "normal" Newton method
> can't work on integer numbers in a residue system (i.e. mod N)?

If it returned 2.5 for 5/2, you could get the remainder by doing 5 -
floor(5/2) = 1.
 |  Next  |  Last
Pages: 1 2 3
Prev: Rendering prediction of congruential random number generators hard
Next: Hey guys, what is this all about? MQQ digital signature scheme?