A peaceful night for you,

The last program was too slow. I am thinking of using the chinese remainder theorem in order to search for a factor of Mp.

I would suggest a linear substitution for f(n)=2n²-1 with n=Mp*k+1, using some precalculated primes and

sort them in different modulo classes (mod Mp).

As the function value is always f(k)=1 mod Mp and the factor g of Mp is also g=1 mod Mp

I am looking for precalculated primes p=1 mod Mp, so that f(k)=p*g and

in the second run for two precalculated primes p*q=1 mod Mp, so that f(k)=p*q*g

Is this method practical and an improvement, or do I replace a slow version by a worse implementation ?

I am not the fastest guy in programming and if someone could give me a hint, would be nice.