View Single Post
Old 2020-06-11, 23:46   #1
jshort
 
"James Short"
Mar 2019
Canada

B16 Posts
Default Proths of the form 2^{k+1}(2^{k} - 1) + 1, 2k+1 is prime

(I guess am sort of answering my own question here......but here goes)

Are Proth Primes of the form 2^{k+1} \cdot (2^{k} - 1) + 1 worthwhile to search for?

Fyi - I'm specifically referring to the special case when 2k + 1 is itself a prime number and when k \equiv 0,3 mod(4)

So here are my reasons for choosing these numbers and restrictions.

1) I noticed that potential composite factors q have to satisfy some very strict congruence conditions when p = 2k+1 is prime (even more strict than prime factors of Mersenne numbers).

For example, q \equiv 1 mod (4(2k+1)) because the order of 2 over q can be shown to be equal to 4p.

2) Sieving out composite Proths of this form is very easy due to the fact that all potential prime factors have the form 1 + 4(2k+1) (unless q = 5, but the congruence restrictions on k prevent this).

Fyi - I personally used the Pollard-rho algorithm with the iterating function x_{n+1} = x_{n}^{24 \cdot (2k+1)} + 1 to weed out many composites

(here is a basic program:

rho1(n)=
{
local(x,y);

x=2; y=2^(24p) + 1;
while(gcd(y-x,n)==1,
x=(x^(24p)+1)%n;
y=(y^(24p)+1)%n; y=(y^(24p)+1)%n
);
gcd(n,y-x)
}

)

Note: You don't necessarily need to use the 'extra' 24 multiplier in the exponent of the iterating function, however the exponent of the iterating function definitely needs to be a "highly composite number" multiple of 4(2k+1) (if not equal to 4(2k+1) itself) to be the most efficient at weeding out composite Proths of this form .

Alternatively, the p-1 test could be used instead to weed out composites. I'm not sure which of the two would be more efficient tbh (if anyone knows the answer to this, that'd be awesome!).
jshort is offline   Reply With Quote