 |
|
| Science Forum Index » Cryptography Forum » calculating only the most significant half of a... |
|
Page 1 of 1 |
|
| Author |
Message |
| yawnmoth... |
 Posted: Tue Nov 03, 2009 11:33 am |
|
|
|
Guest
|
From Multi-Precision Math's discussion of Barrett reduction:
"Recall that the multiplication for the quotient on step 3 must only
produce
digits at or above the m-1'th position. An algorithm called
s_mp_mul_high_digs
which has not been presented is used to accomplish this task. The
algorithm
is based on s_mp_mul_digs except that instead of stopping at a given
level of
precision it starts at a given level of precision."
s_mp_mul_digs is easy enough to understand. If ever the current index
of the product is greater than the number of digits you need, don't
write to it and break out of the loop. In that way, you calculate the
least significant half of a multiplication. But s_mp_mul_high_digs
confuses me. Sure, you can start your way at the middle and work your
way to the most significant digit, but what if the least significant
half had a carry? Without calculating the least significant half how
can you accurately get the most significant half of a multiplication? |
|
|
| Back to top |
|
|
|
| Tom St Denis... |
| Posted: Tue Nov 03, 2009 4:33 pm |
|
|
|
Guest
|
On Nov 3, 4:33 pm, yawnmoth <terra1... at (no spam) yahoo.com> wrote:
[quote]From Multi-Precision Math's discussion of Barrett reduction:
"Recall that the multiplication for the quotient on step 3 must only
produce
digits at or above the m-1'th position. An algorithm called
s_mp_mul_high_digs
which has not been presented is used to accomplish this task. The
algorithm
is based on s_mp_mul_digs except that instead of stopping at a given
level of
precision it starts at a given level of precision."
s_mp_mul_digs is easy enough to understand. If ever the current index
of the product is greater than the number of digits you need, don't
write to it and break out of the loop. In that way, you calculate the
least significant half of a multiplication. But s_mp_mul_high_digs
confuses me. Sure, you can start your way at the middle and work your
way to the most significant digit, but what if the least significant
half had a carry? Without calculating the least significant half how
can you accurately get the most significant half of a multiplication?
[/quote]
The text [and the code] explains it. You need m digits, but produce m
+1 digits. You remove the least significant digit, so at most you've
computed the carry wrong.
The barrett reduction includes a simple subtraction loop to deal with
off by one errors. Essentially you're computing the quotient so you
can compute the remainder via x (mod p) == x - \lfloor x/p \rfloor * p
(trim off the decimal and keep only the integer). But instead of
dividing by p you multiply by 1/p mod \beta^m. The entire chapter
explains fixed point math and builds up the concept of multiplying by
the inverse and how to optimize it.
So in short, the estimate for floor(x/p) could be off by as much as
one. Since subtracting p from the remainder is invariant to the
congruence you can loop at the end without destroying the result.
Tom |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Sat Dec 05, 2009 3:19 am
|
|