Prev: Rendering prediction of congruential random number generators hard
Next: Hey guys, what is this all about? MQQ digital signature scheme?
From: Paul Rubin on 25 Oct 2009 16:16
yawnmoth <terra1024(a)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.
From: Mok-Kong Shen on 25 Oct 2009 18:30
yawnmoth schrieb:
> 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.

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
From: Scott Contini on 25 Oct 2009 18:50
On Oct 26, 3:31 am, yawnmoth <terra1...(a)yahoo.com> 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.

A comparison is done in this article:
http://www.cosic.esat.kuleuven.be/publications/article-144.pdf

Scott
From: yawnmoth on 25 Oct 2009 19:11
On Oct 25, 3:16 pm, Paul Rubin <http://phr...(a)NOSPAM.invalid> wrote:
> yawnmoth <terra1...(a)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.
From: Paul Rubin on 25 Oct 2009 19:26
yawnmoth <terra1024(a)yahoo.com> writes:
> "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 part that you do 800 times just involves truncating to the lower
N bits, which is practically free.
First  |  Prev  |  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?