"Sharon Lourduraj" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED] > 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 :-) > http://wiki.apache.org/jakarta-commons/PrimeNumbers > > I will updated a full-fledged plan as time allows. > > Thanks, > -Sharon > > P.S: > Source 1: http://en.wikipedia.org/wiki/Primality_test > Source 2: http://primes.utm.edu/prove/index.html --------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
