Subject: [Classpathx-crypto] Primes and BigInteger

From: Marcel Winandy <[email-masked]>
Date: Wed, 17 Apr 2002 15:00:45 +0200

Hello!

I've just read that you were wondering about some large primes for which
java.math.BigInteger.isProbablePrime() returns 'false'. Well, BigInteger
has indeed a bug in its primality test. BigInteger runs Miller-Rabin
first. If Miller-Rabin returns 'probable prime' for some number, a
second test will be made, using Lucas this time. And there is a bug in
that Lucas algorithm of BigInteger. I don't know exactly what is is,
because a friend of mine examined several primality test algorithms. He
found that bug in BigInteger and told me. However, it was a very silly
mistake as far as I remeber - something like +1 instead of -1. But the
consequences are enormous - as you have seen.

I hope it will help you.

Bye,
 Marcel
-- 
Marcel Winandy
EMail: [email-masked]
http://www-student.informatik.uni-bonn.de/~winandy/

---

From: "Raif S. Naffah" <[email-masked]>
Date: Fri, 19 Apr 2002 04:16:04 +1000

well, i guessed it may be the case and that's why i asked for somebody who
can inspect the sources (of the JDK) to tell me/us more.  thanx for that.

the GNU crypto lib solves this problem by implementing a more reliable and i
think faster primality test based on Colin Plumb's tests (as the info page
states).

by the way, is there a bug number in the bug parade of Sun that points to
this problem?

cheers;
rsn
----- Original Message -----
From: "Marcel Winandy" <[email-masked]>
To: <[email-masked]>
Sent: Wednesday, April 17, 2002 11:00 PM
Subject: [Classpathx-crypto] Primes and BigInteger

> _______________________________________________
> Classpathx-crypto mailing list
> [email-masked]
> http://mail.gnu.org/mailman/listinfo/classpathx-crypto
>