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

Are Proth Primes of the form

worthwhile to search for?

Fyi - I'm specifically referring to the special case when

is itself a prime number and when

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

1) I noticed that potential composite factors

have to satisfy some very strict congruence conditions when

is prime (even more strict than prime factors of Mersenne numbers).

For example,

because the order of 2 over

can be shown to be equal to

.

2) Sieving out composite Proths of this form is very easy due to the fact that all potential prime factors have the form

(unless

, but the congruence restrictions on

prevent this).

Fyi - I personally used the Pollard-rho algorithm with the iterating function

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'

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

(if not equal to

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!).