Quote:
Originally Posted by paulunderwood

That is just painful. I mean the ecpp proof for the hard number when you have a much cheaper way, searching a better form.
Say
2^a divides p1
3^b divides p+5
ofcourse you want 2^a~3^b (~sqrt(N)) because then you know large p1,(p+6)1 factors in the oder of sqrt(N), so
a=floor(log(N)/log(2)/2)
b=floor(log(N)/log(3)/2)
you can search p in the form (because 2^a and 3^b are coprime):
p=u*2^a+v*3^b,
from divisibilities you can get:
Code:
v*3^b==1 mod 2^a
u*2^a==5 mod 3^b
Don't need to run two variables, fix u, then run v in arithmetic progression. Use sieving.