RE: New algorithm for finding prime factor of large numbers

From: Eugen Leitl (eugen@leitl.org)
Date: Sun Sep 01 2002 - 03:51:25 MDT


On Sat, 31 Aug 2002, Brent Allsop wrote:

> Huu? What good is any algorithm, no matter how fast, if it doesn't produce
> certain results?

http://mathworld.wolfram.com/news/2002-08-07_primetest/

The most efficient prime factorization and primality testing algorithms
known today are probabilistic, in the sense that they use sophisticated
techniques that will almost always return a result but do not do so with
absolute mathematical certainty. For example, a particularly efficient
probabilistic algorithm known as the Rabin-Miller strong pseudoprime test
is used by Mathematica's PrimeQ command for testing primality.

http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html



This archive was generated by hypermail 2.1.5 : Sat Nov 02 2002 - 09:16:36 MST