Hi,
> I�m thinking about something the would probably be called a stage 2 for
> my P-1 factorer, i.e. the 3^(E*(p+x)) = 3^(E*p) * 3^(E+x) with x
> difference between subsequent primes.
> But I need to check for a factor after every of these steps, and a
> full-blown GCD would be far too slow.
> Is there another trick to find out whether two numbers have a
> common factor (without neccessarily finding the factor itself) ?
Not as far as I know but you can effectively eliminate the cost of the GCD.
The usual trick is to accumulate the product of your results (mod 'N') and
then perform the GCD on the product after a certain number of iterations.
Start with the accumulator set to one and then multiply it mod N, by your
result at each iteration. If a factor emerges in one iteration, it will be
remain in the accumulator through successive iterations.
After a number of iterations, say 10000, calculate the GCD(N,accumulator).
There is the risk that more than one factor (or all factors!) might be
extracted in between GCD's. This is easy to work around: After each
unsuccessful GCD, save the current iteration number. If the next
GCD(N,accumulator) is equal to 'N', back track to the iteration you saved
and start again, executing the GCD more frequently.
Don Leclair
[EMAIL PROTECTED]
