[Tcl-bugs] [ tcl-Bugs-2413689 ] Bug in function s_mp_sqr()

[SourceForge.net <no...@so...>]

Bugs item #2413689, was opened at 2008-12-10 06:58
Message generated for change (Settings changed) made by kennykb
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=110894&aid=2413689&group_id=10894

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: 56. LibTomMath
Group: None
>Status: Closed
>Resolution: Invalid
Priority: 5
Private: No
Submitted By: Gregor Cramer (gcramer)
Assigned to: Kevin B KENNY (kennykb)
Summary: Bug in function s_mp_sqr()

Initial Comment:
Function s_mp_sqr() has a bug. I have no example, but I developed a multiple precision library by myself, and I had the same bug in my code. In line bn_s_mp_sqr.c:59 "r       = ((mp_word) *tmpt) + r + r + ((mp_word) u);" an integer overflow may occur! This leads to wrong results in general. Inside the function "HAC pp.596-597, Algorithm 14.16" is referenced, but "Note 14.17 (i)" is not regarded appropriately.

----------------------------------------------------------------------

>Comment By: Kevin B KENNY (kennykb)
Date: 2008-12-10 16:21

Message:
In this case, overflow appears impossible. It is important to remember that
not all the bits of an mp_digit are actually used; the maximum value for an
mp_digit is (1<<28)-1.

So here I see that r (a 64-bit integer) is set to the product of two
mp_digits (which is less than 2**56). It's subsequently doubled, and then
two more mp_digits are added to it, so it winds up still less than 2**58 +
2**29.  This is comfortably less than 2**63-1, the maximum size of an
mp_word.

Even if MP_31BIT is defined - which Tcl does not do - the result of this
addition is at most 2**62 + 2**32, still less than 2**63-1.  (Tcl does not
define MP_31BIT because observed performance is better with the Comba
multipliers, which are incompatible with that option.)
Overflow would be possible if tommath used all 32 bits of an mp_digit. 
But it doesn't.




----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=110894&aid=2413689&group_id=10894