RE: BigInteger.modPow bug? (was: Freenet compilation errors.)

["Boehm, Hans" <hans_boehm at hp dot com>]

The problem I was tracking down turned out to be in the private
setShiftRight method in BigInteger.java.  If x is negative, and count is a
multiple of 32, the line

	words[ival -1] |= -1 << (32 - count);

does the wrong thing, since a left shift by 32 is equivalent to a left shift
by 0 in Java.  Thus this code should bemoved into the preceding else clause.

A test case is attached.

Hans


> -----Original Message-----
> From: Warren Levy [mailto:warrenl@redhat.com]
> Sent: Thursday, January 11, 2001 1:50 PM
> To: Boehm, Hans
> Cc: Mark J. Roberts; java-discuss@sources.redhat.com
> Subject: RE: BigInteger.modPow bug? (was: Freenet compilation errors.)
> 
> 
> On Thu, 11 Jan 2001, Boehm, Hans wrote:
> 
> > I'm also tracking down what appears to be a BigInteger bug, 
> that might be
> > related.  I'll keep you informed.  Please do the same.
> 
> No problem.  Last night I got it narrowed down to a problem 
> in the private
> divide method.  It seems that BigInteger.mod() is resulting 
> in a (bogus)
> negative value (the result should never be negative).  Using 
> the debugger,
> I found that the result of the divide done in the mod method 
> was negative.
> 
> FWIW, This can be reproduced with the following:
> 
> public class EvilBug2 {
>     public static void main(String[] args) {
>         BigInteger Y = new
> BigInteger("11031915393768328745374675758177209216362976918204
> 400783769031961408
> 75500203838079438860704607120089946388490382313311206160357037
> 199551472383943499
> 41968802357224177878230564379014395900786093465543114548034361
> 805469457605783731
> 38257478798077195764061344762835117595916879801134306412390868
> 834394415002870933
> 6");
>         BigInteger Z = new
> BigInteger("21145580999270356144540178884273434632387305495700
> 605013558219015735
> 90017038827070721698806511595635875226688509595390524882971976
> 105408404768726931
> 08381476249027986010074543599432542677282684917897250864056294
> 311624311681558854
> 15843057440949108149021925690724390549654781387864088306495934
> 634386588797138418
> 5");
> 
>         BigInteger res = Z.multiply(Z);
>         System.out.println(res.mod(Y));
>     }
> }
> 
> 
> Let me know what you find or if you think this is related to 
> what you're
> looking at.  I know that slight changes to either Z or Y make 
> the negative
> problem go away so that should help in homing in on the cause.
> 
> Right now, my debugger is being a bit finicky, so I haven't made much
> progress today.
> --warrenl
> 
> 
>

test2.java