commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Phil Steitz" <phil.ste...@gmail.com>
Subject Re: [math] Prime Numbers Library.
Date Sat, 11 Mar 2006 18:32:35 GMT
On 3/11/06, Sharon Lourduraj <sharon.lourduraj@gmail.com> wrote:
> Hello Phil,
>
> Prime Number Theory is a huge subject. To start of with we can focus on
> implementing prime finding methods, such as divide by odd numbers up to
> the square root of a number, divide by primes up to the square root of a
> number and Sieve of Eratosthenes. As we move along, we can implement
> prime finding of specific types, Mersenne Prime, Twin Primes,
> Palindromic Primes etc. And as we move along with those implementations,

> we can introduce Primality Proving algorithms.
>
> Some sites:
> Basic Prime Number finding -
> http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm
> Prime Numbers - http://mathworld.wolfram.com/PrimeNumber.html (good site
> to learn the ins/outs of prime numbers)
> Primality Proving - http://primes.utm.edu/
>
> Also, we can work on implementing optimized algorithms...I think that
> would be fun. The practical purpose of Prime Numbers can be extended
> into encryption/decryption algorithms, but implementing those algorithms
> might be beyond the scope of this project.

Actually, this (optimized algorithms for primality testing /
generating large primes) is what would fit into the scope and mandate
of [math] and could also be eventually useful to [OpenPGP]
(contributing to direct pgp impl or key generation either there or in
[math]). We have tried up to now to stick with applied math topics in
[math], so what we should be focussed on in number-theoretic topics is
things with applications to areas like crypto, using standard
algorithms with good performance and accuracy.   Starting by doing
some research on primality testing algorithms that perform well for
large numbers would be good.  The references here provide a good
starting point:
http://en.wikipedia.org/wiki/Primality_test
http://en.wikipedia.org/wiki/Miller-Rabin_primality_test

I think an API for primality testing (designed consistently with the
rest of [math] - look at the distributions, analysis, stat packages
for examples) with implementations of some standard algorithms would
make a great addition to [math]. The probablilistic algorithms could
leverage the stuff in the random package and also give us some
motivation to extend the capabilities there to include faster random
integer generation methods.

Thanks again for your interest in [math].

Phil

Phil



Phil

>
> Thanks,
> -Sharon
>
> Phil Steitz wrote:
> > Hi Sharon,
> >
> > This sounds interesting. Can you describe a little more what
> > algorithms you are thinking about implementing?  Online references to
> > point us to a common set of definitions for discussion purposes would
> > be great.
> >
> > Also, if you have not aldeady read this, have a look at
> > http://jakarta.apache.org/commons/math/developers.html for info on how
> > to get set up, etc.
> >
> > Thanks!
> >
> > Phil
> >
> > On 3/10/06, Sharon Lourduraj <sharon.lourduraj@gmail.com> wrote:
> >
> >> Hello,
> >>
> >> As you know every math library needs to have a relation to prime number
> >> algorithms, so just wondering if drafting something for prime number
> >> library would be a good idea. I am thinking of providing a patch with
> >> very (very) basic prime number functions. What do you think?
> >>
> >> Let me know :-)
> >> -Sharon
> >>
> >> ---------------------------------------------------------------------
> >> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> >> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
> >>
> >>
> >>
> >
> > ---------------------------------------------------------------------
> > To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> > For additional commands, e-mail: commons-dev-help@jakarta.apache.org
> >
> >
> >
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>
>

---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org


Mime
View raw message