commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Phil Steitz" <>
Subject Re: [math] Prime Numbers Library.
Date Mon, 13 Mar 2006 18:46:25 GMT
On 3/12/06, Bill Barker <> wrote:
> "Sharon Lourduraj" <> wrote in message
> > Hello,
> >
> > Thank you for the positive input on implementing Prime Number functions. I
> > have created a 'wish' on the Math Wish List page. I would like to lay out
> > an initial plan before everyone starts to jump into coding the algorithms.
> >
> > Here is the base "off-my-head" plan, in the order that might prove the
> > implementation to be of positive value, also the order of difficulty:
> >
> > 1. Implement naive primality (quick tests, but are slow for large numbers)
> > testing algorithms. These algorithms are not very fast and are mainly
> > intended for small numbers. Some involve trial and error methods. Some
> > involve generating a sieve, as aligned, to test the given number and
> > derive result from the contents of the sieve.
> >
> +1 IMHO, this really should be a part of [math].

+1 for API,  +0 for naive implementation.  I am OK with starting with
naive implementations to get the API right, which is a strategy that
we have used before, but need to make sure the design will support
robust impls.

> > 2. Implement probabilistic testing (classical tests) algorithms. These
> > algorithms include tests that identify a number as a probable-prime, of
> > course using logical deduction (Fermat, Miller-Rabin, etc.) theorized by
> > mathematicians. These algorithms are relatively fast for large numbers,
> > but are sophisticated. They do contain a calculated error margin.
> >
> Currently, [math] doesn't support integer calculations bigger than 'int'.
> It could do 'long', but it's really not much of an improvement in this area.
> It's really is going to need a BigInteger class simply to handle the 2048+
> bit integers that are of interest to crypto providers.  Of course, the
> number theorests will want much larger :).
> And, yes, I'm volunteering.

What about the jdk-supplied class?  I don't know anything about the
implementation, but this class also supports a probablePrime method
that takes a Random and bit length as arguments.  We could provide one
of our own (Random's) there and leverage the primitives in this class.
 Assm you mean using or extending this, or accomodating BigIntegers in
the API.  Or is the jdk impl not usable?

> > 3. Implement General purpose testing algorithms. These algorithms are
> > extremely advanced. They are significantly faster than any other
> > algorithms. Some of these algorithms have been widely accepted to work,
> > but are based  on conjectures that have still not been proved true (but
> > are widely assumed to be). These algorithms will significantly test our
> > brains and the scope of [math].
> >
> Bring it on ;-).

+1 and of course the Riemann hypothesis is true ;-P
> >
> > Alright, all that thoughts are off my head now. Feel free to make any
> > corrections, I do not have much knowledge of advanced algorithms just a
> > keen interest. Also, feel free to make suggestions.
> >
> > I have created a wiki entry :-)
> >



To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message