 |
|
| Science Forum Index » Cryptography Forum » Newton-Raphson division vs. Montgomery reduction... |
|
Page 1 of 1 |
|
| Author |
Message |
| yawnmoth... |
 Posted: Sun Oct 25, 2009 6:31 am |
|
|
|
Guest
|
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. |
|
|
| Back to top |
|
|
|
| yawnmoth... |
| Posted: Sun Oct 25, 2009 9:26 am |
|
|
|
Guest
|
On Oct 25, 12:15 pm, Paul Rubin <http://phr... at (no spam) NOSPAM.invalid> wrote:
[quote]yawnmoth <terra1... at (no spam) 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.
[/quote]
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. |
|
|
| Back to top |
|
|
|
| yawnmoth... |
| Posted: Sun Oct 25, 2009 9:46 am |
|
|
|
Guest
|
On Oct 25, 12:28 pm, Mok-Kong Shen <mok-kong.s... at (no spam) t-online.de> wrote:
[quote]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)?
[/quote]
If it returned 2.5 for 5/2, you could get the remainder by doing 5 -
floor(5/2) = 1. |
|
|
| Back to top |
|
|
|
| Paul Rubin... |
| Posted: Sun Oct 25, 2009 11:15 am |
|
|
|
Guest
|
yawnmoth <terra1024 at (no spam) yahoo.com> writes:
[quote]My question is... what's the point of using Montgomery reduction in
modular exponentiation if Newton-Raphson division can implement
division efficiently, as well?
[/quote]
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. |
|
|
| Back to top |
|
|
|
| Mok-Kong Shen... |
| Posted: Sun Oct 25, 2009 11:28 am |
|
|
|
Guest
|
yawnmoth wrote:
[quote]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.
[/quote]
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 |
|
|
| Back to top |
|
|
|
| Scott Contini... |
| Posted: Sun Oct 25, 2009 12:50 pm |
|
|
|
Guest
|
On Oct 26, 3:31 am, yawnmoth <terra1... at (no spam) yahoo.com> wrote:
[quote]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.
[/quote]
A comparison is done in this article:
http://www.cosic.esat.kuleuven.be/publications/article-144.pdf
Scott |
|
|
| Back to top |
|
|
|
| yawnmoth... |
| Posted: Sun Oct 25, 2009 1:11 pm |
|
|
|
Guest
|
On Oct 25, 3:16 pm, Paul Rubin <http://phr... at (no spam) NOSPAM.invalid> wrote:
[quote]yawnmoth <terra1... at (no spam) yahoo.com> writes:
But, as I said, if newton-raphson division and the montgomery
reduction have the same time complexity, I don't see the advantage.
You would have to do the newton-raphson process at every step of the
exponentiation. You only have to do the montgomery process once.
[/quote]
No... you have to do the montgomery process every time you do a trial
division. To quote from <http://en.wikipedia.org/wiki/
Montgomery_reduction#Modular_exponentiation>:
"To fix our ideas, suppose that a particular modular exponentiation
requires 800 multiplications. In that case 802 Montgomery steps will
be needed: one to Montgomeryize the number being exponentiated, 800 to
do the exponentiation, and one to de-Montgomeryize the result."
802 != 1. |
|
|
| Back to top |
|
|
|
| Scott Contini... |
| Posted: Sun Oct 25, 2009 1:33 pm |
|
|
|
Guest
|
On Oct 26, 10:11 am, yawnmoth <terra1... at (no spam) yahoo.com> wrote:
[quote]On Oct 25, 3:16 pm, Paul Rubin <http://phr... at (no spam) NOSPAM.invalid> wrote:
yawnmoth <terra1... at (no spam) yahoo.com> writes:
But, as I said, if newton-raphson division and the montgomery
reduction have the same time complexity, I don't see the advantage.
You would have to do the newton-raphson process at every step of the
exponentiation. You only have to do the montgomery process once.
No... you have to do the montgomery process every time you do a trial
division. To quote from <http://en.wikipedia.org/wiki/
Montgomery_reduction#Modular_exponentiation>:
"To fix our ideas, suppose that a particular modular exponentiation
requires 800 multiplications. In that case 802 Montgomery steps will
be needed: one to Montgomeryize the number being exponentiated, 800 to
do the exponentiation, and one to de-Montgomeryize the result."
802 != 1.
[/quote]
The pre-transformation (to get it into Montgomery form) and post-
transformation
are done only once, the other operations are done each iteration.
I might be wrong on this, but as far as my decrepit memory tells me,
the
Montgomery reduction is not a bit speedup. It is a small speedup
(something
like 10%) when implemented efficiently. If I am wrong on this, then
I'm
sure people will let you know. Have a look at the paper I posted a
link
to in the other reply, however.
Scott |
|
|
| Back to top |
|
|
|
| Scott Contini... |
| Posted: Sun Oct 25, 2009 1:36 pm |
|
|
|
Guest
|
On Oct 26, 10:11 am, yawnmoth <terra1... at (no spam) yahoo.com> wrote:
[quote]On Oct 25, 3:16 pm, Paul Rubin <http://phr... at (no spam) NOSPAM.invalid> wrote:
yawnmoth <terra1... at (no spam) yahoo.com> writes:
But, as I said, if newton-raphson division and the montgomery
reduction have the same time complexity, I don't see the advantage.
You would have to do the newton-raphson process at every step of the
exponentiation. You only have to do the montgomery process once.
No... you have to do the montgomery process every time you do a trial
division. To quote from <http://en.wikipedia.org/wiki/
Montgomery_reduction#Modular_exponentiation>:
"To fix our ideas, suppose that a particular modular exponentiation
requires 800 multiplications. In that case 802 Montgomery steps will
be needed: one to Montgomeryize the number being exponentiated, 800 to
do the exponentiation, and one to de-Montgomeryize the result."
802 != 1.
[/quote]
The pre-transformation (to get it into Montgomery form) and post-
transformation are done only once, the other operations are done
each iteration.
I might be wrong on this, but as far as my decrepit memory tells me,
the Montgomery reduction is not a big speedup. It is a small speedup
(something like 10%) when implemented efficiently. If I am wrong on
this, then I'm sure people will let you know. Have a look at the
paper I posted a link to in the other reply, however.
Scott |
|
|
| Back to top |
|
|
|
| yawnmoth... |
| Posted: Sun Oct 25, 2009 1:39 pm |
|
|
|
Guest
|
On Oct 25, 5:30 pm, Mok-Kong Shen <mok-kong.s... at (no spam) t-online.de> wrote:
[quote]yawnmoth schrieb:
On Oct 25, 12:28 pm, Mok-Kong Shen <mok-kong.s... at (no spam) 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.
But you couldn't compute approximate quotient like that in a residue
system, for it doesn't make sense in general, if I don't err. For
instance, let's compute 36/7 mod 31. You would compute floor(36/7)=5.
But 36/7 mod 31 is neither 5 nor 6, nor a number near these, but 14.
[/quote]
Modular exponentiation doesn't really do division save for to
calculate the residue. As such, for that particular application, 36/7
mod 31 seems like maybe a false scenario? |
|
|
| Back to top |
|
|
|
| Paul Rubin... |
| Posted: Sun Oct 25, 2009 2:16 pm |
|
|
|
Guest
|
yawnmoth <terra1024 at (no spam) yahoo.com> writes:
[quote]But, as I said, if newton-raphson division and the montgomery
reduction have the same time complexity, I don't see the advantage.
[/quote]
You would have to do the newton-raphson process at every step of the
exponentiation. You only have to do the montgomery process once. |
|
|
| Back to top |
|
|
|
| Mok-Kong Shen... |
| Posted: Sun Oct 25, 2009 4:30 pm |
|
|
|
Guest
|
yawnmoth schrieb:
[quote]On Oct 25, 12:28 pm, Mok-Kong Shen <mok-kong.s... at (no spam) 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.
[/quote]
But you couldn't compute approximate quotient like that in a residue
system, for it doesn't make sense in general, if I don't err. For
instance, let's compute 36/7 mod 31. You would compute floor(36/7)=5.
But 36/7 mod 31 is neither 5 nor 6, nor a number near these, but 14.
M. K. Shen |
|
|
| Back to top |
|
|
|
| Paul Rubin... |
| Posted: Sun Oct 25, 2009 5:26 pm |
|
|
|
Guest
|
yawnmoth <terra1024 at (no spam) yahoo.com> writes:
[quote]"To fix our ideas, suppose that a particular modular exponentiation
requires 800 multiplications. In that case 802 Montgomery steps will
be needed: one to Montgomeryize the number being exponentiated, 800 to
do the exponentiation, and one to de-Montgomeryize the result."
802 != 1.
[/quote]
The part that you do 800 times just involves truncating to the lower
N bits, which is practically free. |
|
|
| Back to top |
|
|
|
| Francois Grieu... |
| Posted: Mon Oct 26, 2009 12:52 am |
|
|
|
Guest
|
Scott Contini wrote :
[quote]On Oct 26, 10:11 am, yawnmoth <terra1... at (no spam) yahoo.com> wrote:
On Oct 25, 3:16 pm, Paul Rubin <http://phr... at (no spam) NOSPAM.invalid> wrote:
yawnmoth <terra1... at (no spam) yahoo.com> writes:
But, as I said, if newton-raphson division and the montgomery
reduction have the same time complexity, I don't see the advantage.
You would have to do the newton-raphson process at every step of the
exponentiation. You only have to do the montgomery process once.
No... you have to do the montgomery process every time you do a trial
division. To quote from <http://en.wikipedia.org/wiki/
Montgomery_reduction#Modular_exponentiation>:
"To fix our ideas, suppose that a particular modular exponentiation
requires 800 multiplications. In that case 802 Montgomery steps will
be needed: one to Montgomeryize the number being exponentiated, 800 to
do the exponentiation, and one to de-Montgomeryize the result."
802 != 1.
The pre-transformation (to get it into Montgomery form) and post-
transformation are done only once, the other operations are done
each iteration.
I might be wrong on this, but as far as my decrepit memory tells me,
the Montgomery reduction is not a big speedup. It is a small speedup
(something like 10%) when implemented efficiently. If I am wrong on
this, then I'm sure people will let you know. Have a look at the
paper I posted a link to in the other reply, however.
[/quote]
An undeniable benefit of Montgomery reduction is that it replaces the
difficult "quotient estimation" step in traditional division by a simple
step. And it never needs a messy "correction step". True, the odds of
mis-estimation of the quotient can be made so low that it has hardly
measurable impact on average speed, yet the need for this step
complicates hardware and software, and sometime timing attacks
conceivably can be mounted that deduce information from the occurrence
of a correction step.
Most importantly from a speed and hardware perspective, Montgomery
reduction makes it easy to implement each step of multiplication by a
"digit" (which increase the intermediary result by one digit), together
with the reduction step (which decrease the intermediary result by one
digit), with the intermediary result scanned once per digit and per
modular multiplication, and remaining of the same size as N.
By contract, when using "traditional" modular multiplication to compute
W = U*V mod N in the context of modular exponentiation, the textbook
method is to compute U*V, then reduce mod N; the intermediary result
grows twice the size of N, and the number of read/write operations to
the individual digits of the intermediary results is bigger than with
Montgomery reduction using the same base. Also, loop overhead is
typically bigger than with Montgomery reduction.
It is possible to massage "traditional" modular multiplication to the
point that the intermediary result remains the same size as N, and the
number and dominant pattern of access to individual digits is the same
as in Montgomery reduction. The rare case of mis-estimation of the
quotient can even be turned into a rare speedup. Any speed benefit of
Montgomery modular multiplication (using the same base) then becomes
marginal, to the point that the initial and final adjustment outweighs
this benefit when doing modular exponentiation with small exponent (say
64 bits or less). However, I know no good public description of how to
achieve this. Most importantly, when manipulating secret data, guarding
against timing attacks on the individual modular multiplication requires
extra caution, when it comes nearly for free with Montgomery reduction.
Francois Grieu |
|
|
| Back to top |
|
|
|
| Mok-Kong Shen... |
| Posted: Mon Oct 26, 2009 2:08 am |
|
|
|
Guest
|
yawnmoth wrote:
[quote]Mok-Kong Shen wrote:
yawnmoth wrote:
Mok-Kong Shen wrote:
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.
But you couldn't compute approximate quotient like that in a residue
system, for it doesn't make sense in general, if I don't err. For
instance, let's compute 36/7 mod 31. You would compute floor(36/7)=5.
But 36/7 mod 31 is neither 5 nor 6, nor a number near these, but 14.
Modular exponentiation doesn't really do division save for to
calculate the residue. As such, for that particular application, 36/7
mod 31 seems like maybe a false scenario?
[/quote]
I don't know how you'll exactly implement the Newton method for your
purpose to compare with Montgomery's procedure (which I haven't
closely studied). But I want to say that you have to examine and
ensure that nothing involving an analogue of the normal division in
the sense above (directly or indirectly) ever occurs in your scheme.
M. K. Shen |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Fri Nov 27, 2009 6:51 am
|
|