View Single Post
Old 2021-09-23, 00:35   #3
bhelmes's Avatar
Mar 2016

17116 Posts

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.

bhelmes is offline   Reply With Quote