Thread: Other Primes
View Single Post
Old 2019-04-19, 23:05   #188
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

24·83 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Congrats to GEN-ERIC for the primes [p,p+6] = (18041#/14*2^39003-4)±3.

http://primepairs.com/
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 p-1
3^b divides p+5

ofcourse you want 2^a~3^b (~sqrt(N)) because then you know large p-1,(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.
R. Gerbicz is offline   Reply With Quote