Re: Algorithm used by BigInteger prime generator?
> No my assumption was based on a conversation I had with > the original author a couple of years ago... Well, JDBC does use BigDecimal, and was presumably a motivator for including it in JDK1.1. I agree that geneating random primes suggests crypto, and may have been a motivator for the "original author" of BigInteger. What you did not explain was whether by "orginal author" you mean the person who wrote a BigInteger class that java.math.BigInteger was based on, if this pre-dates JDK1.1, or you mean the person at JavaSoft who "owned" java.math in JDK1.1, or if they are the same person. In any case, big numbers are useful for various applications, inlcuding crypto. It is important that the generated "random" values be the same on all platforms, and that is difficult with Sun's missing specifications. (Even the specifications of java.io in the JLS is incomplete; classes not specified on the JLS often are way under-specified. And the Class Libraries books, in additions to *not* being specifications, have lots of mistakes.) --Per Bothner Cygnus Solutions [EMAIL PROTECTED] http://www.cygnus.com/~bothner
RE: Algorithm used by BigInteger prime generator?
> Quoth Per Bothner [mailto:[EMAIL PROTECTED]]: > > "D'Arcy Smith" <[EMAIL PROTECTED]> writes: > > > [crypto] is what [BigInteger] is was written for in the first place > > > apparently... > > I had the (unsubstantiated) impression was that it was written for > > JDBC (i.e. a needed SQL data type). Certainly, I can't imagine > > BigDecimal being useful for crypto, but big decimal integers > > (at least 18 digits) are needed for database applications. > His assumption was probably based on this constructor: No my assumption was based on a conversation I had with the original author a couple of years ago... ..darcy -- D'Arcy Smith Sr. Software Engineer Symantec Corp., Internet Tools Division
Re: Algorithm used by BigInteger prime generator?
On Apr 22, 1999, "John Keiser" <[EMAIL PROTECTED]> wrote:
> Incidentally, as long as this method creates random BigIntegers, why does it
> matter what algorithm is used?
Given my Random generator, initialized with the same seed, I should be
able to generate the same sequence of prime BigIntegers on any Java
platform, otherwise WORA falls apart. That's why the standard Random
class is clearly specified, and that's why the algorithm for random
big prime generation should too.
--
Alexandre Oliva http://www.dcc.unicamp.br/~oliva IC-Unicamp, Brasil
{oliva,Alexandre.Oliva}@dcc.unicamp.br aoliva@{acm.org,computer.org}
oliva@{gnu.org,kaffe.org,{egcs,sourceware}.cygnus.com,samba.org}
*** E-mail about software projects will be forwarded to mailing lists
RE: Algorithm used by BigInteger prime generator?
Quoth Per Bothner [mailto:[EMAIL PROTECTED]]: > > > "D'Arcy Smith" <[EMAIL PROTECTED]> writes: > > [crypto] is what [BigInteger] is was written for in the first place > > apparently... > > I had the (unsubstantiated) impression was that it was written for > JDBC (i.e. a needed SQL data type). Certainly, I can't imagine > BigDecimal being useful for crypto, but big decimal integers > (at least 18 digits) are needed for database applications. > His assumption was probably based on this constructor: BigInteger(int bitLength, int certainty, Random rnd) Constructs a randomly generated positive BigInteger that is probably prime, with the specified bitLength. Primes usually imply crypto. They certainly don't imply database. Incidentally, as long as this method creates random BigIntegers, why does it matter what algorithm is used? As long as the distribution is roughly the same as JDK's, as long as it doesn't take longer, and as long as the bitLength and certainty parameters are honored, the algorithm shouldn't matter. Random numbers are one area where a complete algorithm is not necessary for a complete specification, IMHO. --John Keiser
Re: Algorithm used by BigInteger prime generator?
On Apr 20, 1999, Paul Fisher <[EMAIL PROTECTED]> wrote:
> Alexandre Oliva <[EMAIL PROTECTED]> writes:
>> Does anybody know what algorithm the constructor
>> java.math.BigInteger.BigInteger(int bitLength, int certainty, Random
>> rnd) is supposed to use?
> Sun's java.math implementation uses Colin Plumb's <[EMAIL PROTECTED]>
> BigNum library ftp://skip.incog.com/pub/bnlib-1.1.tar.gz>.
> You'll find the prime number generation routines there.
Thanks for the pointer. BTW, this is GPLed, did Sun get a special
license from Colin Plumb?
> Implementing the algorithm for Classpath is on my TODO list.
> Although, if you're interested in writing it, we'd love to include
> it. :)
Well, I'm currently writing it for Kaffe, but if it fits well into
Classpath, or requires a just little adaptation, I'd be glad to
contribute it to Classpath too.
--
Alexandre Oliva http://www.dcc.unicamp.br/~oliva IC-Unicamp, Brasil
{oliva,Alexandre.Oliva}@dcc.unicamp.br aoliva@{acm.org,computer.org}
oliva@{gnu.org,kaffe.org,{egcs,sourceware}.cygnus.com,samba.org}
*** E-mail about software projects will be forwarded to mailing lists
RE: Algorithm used by BigInteger prime generator?
> "D'Arcy Smith" <[EMAIL PROTECTED]> writes: > > [crypto] is what [BigInteger] is was written for in the first place > > apparently... > I had the (unsubstantiated) impression was that it was written for > JDBC (i.e. a needed SQL data type). Certainly, I can't imagine > BigDecimal being useful for crypto, but big decimal integers > (at least 18 digits) are needed for database applications. IIRC the guy who originaly wrote them did it for key calculations... ..darcy
RE: Algorithm used by BigInteger prime generator?
> I think that's the heart of this disagreement. I think that > BigInteger is a crypto library in disguise That is what is was written for in the first place apparently... ..darcy
Re: Algorithm used by BigInteger prime generator?
"D'Arcy Smith" <[EMAIL PROTECTED]> writes: > [crypto] is what [BigInteger] is was written for in the first place > apparently... I had the (unsubstantiated) impression was that it was written for JDBC (i.e. a needed SQL data type). Certainly, I can't imagine BigDecimal being useful for crypto, but big decimal integers (at least 18 digits) are needed for database applications. --Per Bothner Cygnus Solutions [EMAIL PROTECTED] http://www.cygnus.com/~bothner
Re: Algorithm used by BigInteger prime generator?
On Apr 20, 1999, Paul Fisher <[EMAIL PROTECTED]> wrote:
> Alexandre Oliva <[EMAIL PROTECTED]> writes:
>> Does anybody know what algorithm the constructor
>> java.math.BigInteger.BigInteger(int bitLength, int certainty, Random
>> rnd) is supposed to use?
> Sun's java.math implementation uses Colin Plumb's <[EMAIL PROTECTED]>
> BigNum library ftp://skip.incog.com/pub/bnlib-1.1.tar.gz>.
> You'll find the prime number generation routines there.
The problem is that there's no specification about what to do after
generating a random number, nor does it talk about ``adjusting'' a
randomly-generated number so that it passes a primality test. For
example, Plumb's primeGen doesn't provide a mechanism to specify a
`certainty'.
Furthermore, Plumb's implementation accepts a rand function as an
argument, that takes only an unsigned integer as argument, to
randomize the increments to the base random number. I don't see how
Sun might have written a wrapper function that would call back the
Random generator passed as argument, since it wouldn't be able to
figure out which Random object to invoke... But then, this is not an
issue, since we wouldn't be using Plumb's implementation anyway.
I'm going to install a very dumb implementation, and improve it when I
get input from Sun about the actual algorithm that should be used.
--
Alexandre Oliva http://www.dcc.unicamp.br/~oliva IC-Unicamp, Brasil
{oliva,Alexandre.Oliva}@dcc.unicamp.br aoliva@{acm.org,computer.org}
oliva@{gnu.org,kaffe.org,{egcs,sourceware}.cygnus.com,samba.org}
*** E-mail about software projects will be forwarded to mailing lists
Re: Algorithm used by BigInteger prime generator?
On Apr 22, 1999, Andrew Haley <[EMAIL PROTECTED]> wrote:
> As far as I can see, what is intended is something like this:
> if (candidate.isProbablePrime (certainty))
> return candidate;
> else
> candidate = candidate.add (BigInteger.valueOf (2));
Except that this may generate a prime with more than bitLength bits,
depending on the initial random number and on the number of failures
you get, so you may have to retry if it overflows. Furthermore, it
doesn't generate randomly distributed primes, and I'm not sure this
meets the requirement of O(certainty). Anyway, I've just committed a
version that does it. But it could be made much more efficient by
using a sieve, since isProbablePrime is quite expensive.
Nevertheless, the specification leaves room for a lot of different
implementations, particularly in the use of rnd, which is unacceptable
for WORA. Theoretically, given the same implementation of Random,
with the same seed, one should get the same sequence of random primes,
regardless of the JVM used.
Also note that your implementation will never generate 2 for
bitLength==2.
--
Alexandre Oliva http://www.dcc.unicamp.br/~oliva IC-Unicamp, Brasil
{oliva,Alexandre.Oliva}@dcc.unicamp.br aoliva@{acm.org,computer.org}
oliva@{gnu.org,kaffe.org,{egcs,sourceware}.cygnus.com,samba.org}
*** E-mail about software projects will be forwarded to mailing lists
Re: Algorithm used by BigInteger prime generator?
> From: Alexandre Oliva <[EMAIL PROTECTED]>
> Date: 22 Apr 1999 06:36:42 -0300
>
> Alexandre Oliva <[EMAIL PROTECTED]> writes:
>> Does anybody know what algorithm the constructor
>> java.math.BigInteger.BigInteger(int bitLength, int certainty, Random
>> rnd) is supposed to use?
>
> The problem is that there's no specification about what to do after
> generating a random number, nor does it talk about ``adjusting'' a
> randomly-generated number so that it passes a primality test.
The specification seems to me to be adequate: generate a random prime
_bitLength_ bits long which passes a Fermat test or somesuch
_certainty_ times. In cryptographic usage, the most significant bit
of an n-bit number is always assumed to be set: that's what defines it
to be an n-bit number.
As far as I can see, what is intended is something like this:
static BigInteger newPrime (int bitLength, int certainty, Random rnd)
{
BigInteger candidate = new BigInteger (bitLength, rnd);
candidate = candidate.setBit (bitLength-1).setBit (0);
for (;;)
{
boolean prime = true;
if (candidate.isProbablePrime (certainty))
return candidate;
else
candidate = candidate.add (BigInteger.valueOf (2));
}
}
I haven't tested this, and a real version should check for overflows,
but I don't think that much more is needed.
Andrew.
Re: Algorithm used by BigInteger prime generator?
On Apr 22, 1999, Andrew Haley <[EMAIL PROTECTED]> wrote:
>> Except that this may generate a prime with more than bitLength bits,
> Did you not see my comment that "a real version should check for
> overflows"?
Yup, I should have ack'ed it.
>> Furthermore, it doesn't generate randomly distributed primes
> The specification doesn't require it to.
Indeed. It doesn't really say much.
> The technique of simply adding 2 until a prime is reached is pretty
> much standard in crypto, and with crypto-sized BigIntegers the
> deviation from a uniform distribution is insignificantly small.
But we're not talking about crypto-sized BigIntegers, we're talking
about the BigInteger class. It's supposed to be general-purpose, not
exclusive for use for cryptography. If it were, it probably wouldn't
be exportable :-)
> If this is really unacceptable, a new random integer could be
> generated with each iteration, which answers such objections, but
> it's an extra run-time overhead.
But then it certainly won't meet the requirement about execution time
proportional to the value of certainty.
>> and I'm not sure this meets the requirement of O(certainty).
> I don't understand this. Are you saying that isProbablePrime
> (certainty) does not meet the requirement of O(certainty)?
Nope, I'm just unsure whether testing primes sequentially does,
assuming that isProbablePrime takes constant time for a constant
bitLength.
>> Nevertheless, the specification leaves room for a lot of different
>> implementations, particularly in the use of rnd, which is unacceptable
>> for WORA.
> I see your point. However, the requirement that all implementations
> return the same result means that implementors are prevented from
> inventing a more efficient prime generator. In real-world crypto
> applications, where random primes are frequently generated, this is
> very bad news. In financial applications, it is not uncommon to use
> hardware accelerators to generate random primes: it would be
> impossible to use such hardware if the exact algorithm used to
> generate primes was fixed.
You're free to implement whatever algorithm you want for big prime
generation in your own classes, but
java.lang.BigInteger.BigInteger(int,int,Random) must be completely
specified in order to allow for WORA. If this means using an
inefficient implementation, so be it.
--
Alexandre Oliva http://www.dcc.unicamp.br/~oliva IC-Unicamp, Brasil
{oliva,Alexandre.Oliva}@dcc.unicamp.br aoliva@{acm.org,computer.org}
oliva@{gnu.org,kaffe.org,{egcs,sourceware}.cygnus.com,samba.org}
*** E-mail about software projects will be forwarded to mailing lists
Re: Algorithm used by BigInteger prime generator?
> From: Alexandre Oliva <[EMAIL PROTECTED]> > Date: 22 Apr 1999 11:55:44 -0300 > > On Apr 22, 1999, Andrew Haley <[EMAIL PROTECTED]> wrote: > > > The technique of simply adding 2 until a prime is reached is pretty > > much standard in crypto, and with crypto-sized BigIntegers the > > deviation from a uniform distribution is insignificantly small. > > But we're not talking about crypto-sized BigIntegers, we're talking > about the BigInteger class. It's supposed to be general-purpose, not > exclusive for use for cryptography. I think that's the heart of this disagreement. I think that BigInteger is a crypto library in disguise, intended so that Java may be used for Internet commerce. I think that's why the exact method for generating random primes isn't exactly specified, so that implementors may do the most efficient thing. I accept that's not what the standard actually says. ;-) > assuming that isProbablePrime takes constant time for a constant > bitLength. Mm. It would be a very bad implementation of isProbablePrime that took constant time for a constant bitLength. Andrew.
Re: Algorithm used by BigInteger prime generator?
> From: Alexandre Oliva <[EMAIL PROTECTED]> > Date: 22 Apr 1999 11:09:10 -0300 > > On Apr 22, 1999, Andrew Haley <[EMAIL PROTECTED]> wrote: > > > As far as I can see, what is intended is something like this: > > > if (candidate.isProbablePrime (certainty)) > > return candidate; > > else > > candidate = candidate.add (BigInteger.valueOf (2)); > > Except that this may generate a prime with more than bitLength bits, Did you not see my comment that "a real version should check for overflows"? > Furthermore, it doesn't generate randomly distributed primes The specification doesn't require it to. The technique of simply adding 2 until a prime is reached is pretty much standard in crypto, and with crypto-sized BigIntegers the deviation from a uniform distribution is insignificantly small. If this is really unacceptable, a new random integer could be generated with each iteration, which answers such objections, but it's an extra run-time overhead. > and I'm not sure this meets the requirement of O(certainty). I don't understand this. Are you saying that isProbablePrime (certainty) does not meet the requirement of O(certainty)? > Nevertheless, the specification leaves room for a lot of different > implementations, particularly in the use of rnd, which is unacceptable > for WORA. I see your point. However, the requirement that all implementations return the same result means that implementors are prevented from inventing a more efficient prime generator. In real-world crypto applications, where random primes are frequently generated, this is very bad news. In financial applications, it is not uncommon to use hardware accelerators to generate random primes: it would be impossible to use such hardware if the exact algorithm used to generate primes was fixed. Andrew.
Re: Algorithm used by BigInteger prime generator?
On Apr 21, 1999, Godmar Back <[EMAIL PROTECTED]> wrote:
> I'm wondering whether you have to use BigNum.
I hope not.
> Specifically, I was wondering if some of the invariants concerning
> the representation of the magnitude and the location of the MSB are
> the same.
I plan to look into it some day, since I want to get MindTerm (a GPLed
ssh client) to work with Kaffe.
Anyway, I've filed a Java specification bug report, and they
acknowleged it as a bug. It should soon appear in the Bug Parade as
Bug Report # 4231449.
--
Alexandre Oliva http://www.dcc.unicamp.br/~oliva IC-Unicamp, Brasil
{oliva,Alexandre.Oliva}@dcc.unicamp.br aoliva@{acm.org,computer.org}
oliva@{gnu.org,kaffe.org,{egcs,sourceware}.cygnus.com,samba.org}
*** E-mail about software projects will be forwarded to mailing lists
Re: Classpath Status
"Aaron M. Renn" <[EMAIL PROTECTED]> writes: > >> -- Add the correct serialVersionUID. > > > >Is there an easy way to find out what this should be? > > Yes. There is a program called "serialver" which prints this value. It is > part of the JDK distribution, or I have a version I can send you. Should point out there is a similar program within Classpath. I don't think it is built/installed by default. Would also like to make ClassTool part of Classpath at some point if we can. classpath/gnu/tools/serialver Brian
Re: Classpath Status
"Aaron M. Renn" <[EMAIL PROTECTED]> writes: > >> -- Add the correct serialVersionUID. > > > >Is there an easy way to find out what this should be? > > Yes. There is a program called "serialver" which prints this value. It is > part of the JDK distribution, or I have a version I can send you. We also have our own version (sans script) -> gnu.tools.serialver.Main -- Geoff Berry
