 |
|
| Science Forum Index » Cryptography Forum » question about montgomery reductions... |
|
Page 1 of 1 |
|
| Author |
Message |
| yawnmoth... |
 Posted: Fri Oct 30, 2009 6:41 pm |
|
|
|
Guest
|
From <http://math.libtomcrypt.com/files/tommath.pdf>:
"The final result 900 is then divided by B**k to produce the final
result 9.
The first observation is that 9 != x (mod n) which implies the result
is not the
modular residue of x modulo n. However, recall that the residue is
actually
multiplied by B**-k in the algorithm. To get the true residue the
value must
be multiplied by B**k. In this case B**k = 15 (mod n) and the correct
residue is
9 * 15 = 16 (mod n)."
So, basically, to undo a montgomery reduction, all you need do is get
the remainder when dividing by n? Dividing by B**k seems pointless if
you're just going to multiply by it later. Sure, as a result of
shiting one way and back the other, some digits will be zero'd out,
but if those digits need to be zero'd out, why not just do it
directly?
Also, just to confirm that I'm understanding the montgomery reduction
correctly...
If B == 2**26, x = 2**26, n = 2**26 + 1, and k = 2 (ie. the number of
digits in n), then the loop would be as follows:
x[0] = 0
x[1] = 1 (msb)
-1/n[0] (mod B) == 2**26 - 1
t = 0
u = x[t] * (2**26 - 1) (mod 2**26) == 0
x = 2**26 + 0 * (2**26 + 1) * (2**26)**0 == 2**26
t = 1
u = x[t] * (2**26 - 1) (mod 2**26) == 2**26 - 1
x = 2**26 + (2**26 - 1) * (2**26 + 1) * (2**26)**1 == (2**26)**3
return ((2**26)**3)/((2**26)**2) == 2**26
At this point, we, presumably, have no way of knowing if this is the
answer we want or not (even though 2**26 == (2**26 % 2**26 = 1)), so
we need to "undo" it, which, per the above, would involve zero'ing out
the least k significant digits or by dividing or multiplying it by B
and then getting the remainder from a regular division algorithm.
Problem is, none of those yield the correct answer. |
|
|
| Back to top |
|
|
|
| Tom St Denis... |
| Posted: Sat Oct 31, 2009 12:32 am |
|
|
|
Guest
|
On Oct 31, 12:41 am, yawnmoth <terra1... at (no spam) yahoo.com> wrote:
[quote]From <http://math.libtomcrypt.com/files/tommath.pdf>:
"The final result 900 is then divided by B**k to produce the final
result 9.
The first observation is that 9 != x (mod n) which implies the result
is not the
modular residue of x modulo n. However, recall that the residue is
actually
multiplied by B**-k in the algorithm. To get the true residue the
value must
be multiplied by B**k. In this case B**k = 15 (mod n) and the correct
residue is
9 * 15 = 16 (mod n)."
So, basically, to undo a montgomery reduction, all you need do is get
the remainder when dividing by n? Dividing by B**k seems pointless if
you're just going to multiply by it later. Sure, as a result of
shiting one way and back the other, some digits will be zero'd out,
but if those digits need to be zero'd out, why not just do it
directly?
[/quote]
You have to read the entire section. The idea is that you premultiply
your values by R=B**k, e.g.
A = aR
B = bR
then
AB = abR^2
Now when you reduce that you end up with abR. In the sense of an
exptmod for instance, that's useful since now your accumulated product
is in terms of R, you can square/multiply against it and when you
reduce it's back in terms of R.
When you are finished your exptmod, one last reduction divides by R
and voila the result.
Leaving aside all the numbers the point of Montgomery is to take two
values XX and YY to produce a product like ZZZZ then somehow zero the
lower two digits to WW00 which you can then shift [without losing
data] to WW. The text explains it in terms of single bits first, then
moves on to digits, I suggest you re-read the entire section.
Tom |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Sat Dec 05, 2009 4:30 pm
|
|