Pollard' rho algorithm is not deterministic,

It is probabilistic and could fail even with small numbers.

It should not be part of discussions about

"proven lower bounds"

Milton L. Brown

miltbrown at earthlink.net

-----Original Message-----

From: Décio Luiz Gazzoni Filho <

decio@...>

Sent: May 2, 2004 9:17 PM

To:

primenumbers@yahoogroups.com
Subject: [PrimeNumbers] Does such a factoring algorithm exist?

-----BEGIN PGP SIGNED MESSAGE-----

Hash: SHA1

Is there a factoring algorithm which depends on the size of the factors (and

not the integer being factored itself), and is faster than trial division,

yet upon failure it provides a proven lower bound on the factors?

With Pollard rho, for instance, if I perform O(t) iterations of the method

unsuccessfully, this is a clue that the integer in question is not likely to

have prime factors < t^2, but for my application I need a proof of that

assertion. If I trial divide with primes up to t without finding anything,

then this is proof that the integer being trial divided has no factors up to

t -- thus trial division is an algorithm that I could use, except that it's

slow.

So, anyone knows of an algorithm that fits the bill?

Décio

-----BEGIN PGP SIGNATURE-----

Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFAlcf3FXvAfvngkOIRAmBiAJ49BGSUYXTtHpeWbXV3U+9dB1Z7BgCZAcEw

4yYr3lR2y3tjTeYxMNa9tu8=

=1CpK

-----END PGP SIGNATURE-----

Unsubscribe by an email to:

primenumbers-unsubscribe@yahoogroups.com
The Prime Pages :

http://www.primepages.org/
Yahoo! Groups Links