Re: libtommath - Greg Rose - Help on libtommath

On Tue, 30 Sep 2008 11:32:56 -0700 (PDT), amzoti <amzoti@xxxxxxxxx>
wrote:

The fully calculated product of the two numbers that you gave would be
(most significant digit to least significant):

e0 cbfe76c e855d80 c0608c4 eccbd17 efd198a 230cad6 72745d1 e989f02
5a83fde 2b2c2bf ca5bc1c 2e88d5e 1560723 8fadf39 d6cbfe7 ||| 6ce8 ||
55d 80c0608 c4eccbd 17efd19 8a230ca d672745 d1e989f 025a83f de2b2c2
bfca5bc 1c2e88d 5e15607 238fadf 38f6000 0000000

But in the calculations given by s_mp_mul_high_digs, we get a correct
result down to the digit "d6cbfe7". All digits less significant than
this one are off, even though some are given above the lower zeros.

Is there any way to determine which number of digits the high digit
multiplication will be guaranteed to be accurate every time?

I do not think so, because AFAIK the only thing that can be said, is
that q3 = floor(q2/b^(k+1) is at most off by 2. But this can (in the
worst cast) lead to the situation that due to carry propagation
all/most digits are wrong, although the difference is less than about
2*b^(k+1).


It is also worth noting that to get the a matching result for the
operands that you gave, I had to set the parameter "digs" for
s_mp_mul_high_digs to 14, not 15, as you explained in your
calculations. Did I miss understand something?

No, at least not something that is obvious. But some time ago I
changed the code in my Pascal implementation after realizing that
digs==um leads to more back subtracts than necessary:

{q1 = x / b^(k-1)}
mp_rshd(q, um-1);

{done if q1=0, *V0.7.07}
if q.used>0 then begin
if [snip] then begin
mp_mul(q, mu, q)
end
else begin
{*V1.1.09: use digs=um-1 to avoid large number if back subtracts
below}
s_mp_mul_high_digs(q, mu, q, um-1);
end;
...
end;

Please note that if you do this change, it is (as already said) vital
to check and handle negative offsets in Tom's s_mp_mul_high_digs code

/* alias for where to read the right hand side from */
tmpy = b->dp + (digs - ix);

The "underflow" is obvious for digs==0, which theoretically should be
allowed.


Wolfgang
--
In order to e-mail me a reply to this message, you will have
to remove PLEASE.REMOVE from the address shown in the header
or get it from http://home.netsurf.de/wolfgang.ehrhardt
(Free open source Crypto, AES, CRC, Hash for Pascal/Delphi)
.