commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Bill Barker" <>
Subject Re: [math] Prime Numbers Library.
Date Mon, 13 Mar 2006 00:58:04 GMT

"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].

> 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.

> 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 ;-).

> 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 :-) 
> I will updated a full-fledged plan as time allows.
> Thanks,
> -Sharon
> P.S:
> Source 1:
> Source 2: 

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

View raw message