LLT, double-checking and factoring at the same time

[T.Rex]

Originally Posted by maxal

First off, I've got slightly different result for F(43) running your program here:

? F(43)
q: 43 A4188889-28 A4188889-56

I wrote a program A that displays each factor only once. Then I wrote a simplified version F in order to provide it on the forum. And they seem to differ in some cases, like for 43. So, I've provided result of A(43) instead of F(43). Sorry.

Regarding the algorithm: I think there is no much sense in computing gcd like A=gcd(S1-S1_,S2-S2_) and then checking if A is a dividor of M. It is no better than computing gcd(S1-S1_,M) and gcd(S2-S2_,M) and checking if either is greater than 1. But the latter approach allows to process different starting values independently.

My idea was that mixing values computed from different initial values would lead to more chances to find a factor. Your program shows that the basic Rho Pollard does provide nearly the same factors, but not exactly.

And I am not convinced that using several starting values helps much.

Your example with 43 shows that 2/3 sometimes provides different factors.

So, do you agree that the conclusion is that this method could find some interesting factors, but with a higher cost than ways already used by prime95 ?
(up to now, I've found NO interesting big factor with this method and Pari ...)
Tony

[maxal]

Originally Posted by T.Rex

My idea was that mixing values computed from different initial values would lead to more chances to find a factor.

Mixing values does not help at all. Because of the following trivial observation:
If gcd(S1-S1_,S2-S2_) gives you a factor of M, then the same factor is contained (maybe with others) in both gcd(S1-S1_,M) and gcd(S2-S2_,M).

Originally Posted by T.Rex

Your example with 43 shows that 2/3 sometimes provides different factors.

Yes, but the amount of work is doubled/tripled/etc. with the number of different starting values.

Originally Posted by T.Rex

So, do you agree that the conclusion is that this method could find some interesting factors, but with a higher cost than ways already used by prime95 ?

Maybe.