Re: A benchmark comparing ECM and triangle number factoring.

On Oct 20, 1:03 pm, dan73 <fasttrac...@xxxxxxx> wrote:
dan73 <fasttrac...@xxxxxxx> writes:
As a test I chose 2 equal length primes of 309
digits each with their ratio close to but less than (2).
Close? That's an understatement.

You are right--- a (1) followed by 150 9's after
the decimal point.

Note that this algorithm generalizes. If N = p/q and p/q is
sufficiently close to the ratio of two small integers a/b, then N
is easily factored by an extension of Fermat's difference of squares.
The trick, of course, is to know a/b..... It will also work if
(p/q)^1/s is sufficiently close to the ratio of two small integers
for
some value of (integer) s.

However, "sufficiently close", means "almost impossibly close" in
practice.

Look up "Lehman's Algorithm".
.