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

Thu Jan 11 02:55:00 GMT 2001

On Sun, 7 Jan 2001, Mark J. Roberts wrote:
> Another test case, for another (perhaps less trivial) bug:
>> import java.math.BigInteger;
>> public class EvilBug {
> public static void main(String[] args) {
> BigInteger X = new BigInteger("222556259477882361118129720038750144464896096345697329917462180806109470940281821580712930114298080816996240075704780895407778416354633927929850543336844729388676722554712356733107888579404671103423966348754128720372408391573576775380281687780687492527566938517625657849775850241884119610654472761291507970934");
> BigInteger Y = new BigInteger("110319153937683287453746757581772092163629769182044007837690319614087550020383807943886070460712008994638849038231331120616035703719955147238394349941968802357224177878230564379014395900786093465543114548034361805469457605783731382574787980771957640613447628351175959168798011343064123908688343944150028709336");
> BigInteger Z = new BigInteger("211455809992703561445401788842734346323873054957006050135582190157359001703882707072169880651159563587522668850959539052488297197610540840476872693108381476249027986010074543599432542677282684917897250864056294311624311681558854158430574409491081490219256907243905496547813878640883064959346343865887971384185");
> BigInteger A = Z.modPow(X,Y);
> System.out.println(A.toString());
> }
> }
>> which results in:
>> [root@rm03-24-131-185-22 /freenet]# gcj --main=EvilBug -o evilbug EvilBug.java
> [root@rm03-24-131-185-22 /freenet]# ./evilbug
> 76475944278426898748735231384095480813900840993607065582220349895865809085142942614931274934596621051633402900925590578189740023258059721343444253476042572315014638104175928891530878756403552402446824939295559830592949251323649349933451461856156175697510863031755311205211843476729890389330266393681960156153
> [root@rm03-24-131-185-22 /freenet]# javac EvilBug.java
> [root@rm03-24-131-185-22 /freenet]# java EvilBug
> 89040229313686098274750802637193802904787850353791629688385431482589769348345172944539658366893587456857347312314974124445695423885005533414559099801699612294235861570065774222911180890417009385455826560773741520297884850460324781620974467560905975577765401911117379967692495136423710471201230243826129276993
>> Which are quite different. This did not emerge when I tried smaller values
> (even quite big smaller values) but only with these big
> Diffie-Hellman-sized ones. With some similarly-sized ones, I could not
> reproduce the error, so perhaps it's related to improper rounding?
>> Note that I have no idea how this thing works; I only know that it
> doesn't. "Additive chaining" means nothing to me.

That's ok, the Additive chaining algorithm seems to be fine; I implemented
it in a test program that I tried in both gcj and the JDK. I get the
exact same results in both gcj and the JDK as you did using modPow 
directly. This tells me the problem is in one of the underlying methods.
I'll try checking the intermediate output of the algorithm in my test
program to see at what point gcj and the JDK diverge. That should help me
home in on the problem.
(BTW, I've changed the Subject for this thread to something more
appropriate; I've also included most of the original text to make
following this in the archive easier).
--warrenl