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

jshort · 2020-06-11, 23:46

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

carpetpool · 2020-06-12, 05:34

I think you are referring to Gaussian Mersenne norms.

JeppeSN · 2020-06-15, 17:42

Quote:

Originally Posted by carpetpool

I think you are referring to Gaussian Mersenne norms.

That sounds correct. In fact it seems the Gaussian Mersenne norms includes a bit more candidates, namely 2^{2k+1} ± 2^{k+1} + 1 where the sign of the middle term is picked such that the candidate is not divisible by 5. You can fix the sign, then you will get "half" of the Gaussian Mersenne norms. /JeppeSN

Batalov · 2020-06-15, 19:07

https://primes.utm.edu/top20/page.php?id=41

https://mersenneforum.org/showthread.php?t=19235

https://oeis.org/A057429 = https://oeis.org/A007670 + https://oeis.org/A007671

Batalov · 2020-06-15, 21:00

Quote:

Originally Posted by jshort

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

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

In additional to what UTM's (and Mathworld's iirc has one) comprehensive pages says, quick note: Gaussian Mersenne norms share many similarities to Mersenne numbers. In particular,
* n needs to be prime - why? because otherwise there is an algebraic factorization. (And in the algebraic factorization you will find both + and - forms)
* Any factor (except 5 which is intrinsic) is of form 2 * k * p + 1, so trial factoring is simplified but is very similar to Mersenne project: you don't sieve database-wide - you pre-factor each candidate. Furthermore, just like factors of Mersenne composites, these will not share the same factors (except the trivial case when one divides the other).

...that's just a few quick thoughts is a spare time during lunch break.

P.S. All primes of this form at this time are known -- loosely speaking to the limit of p < 10,000,000. So searching below this limit will not bring too much joy to the searcher.

JeppeSN · 2020-06-20, 07:55

If you consider the numbers 2^(4k+2) + 1, there are two kinds of algebraic factorizations for them. One is because 4k+2 = 2(2k+1), so the exponent has an odd divisor, therefore:

2^(4k+2) + 1 = (2^2)^(2k+1) + 1 = (2^2 + 1)[(2^2)^(2k) - (2^2)^(2k-1) + ... - (2^2)^3 + (2^2)^2 - 2^2 + 1]

But this simply says that 2^2 + 1 = 5 divides 2^(4k+2) + 1 which is also quite obvious without the factorization above.

Set n=2k+1. When n is a prime, there are no other nontrivial odd factors of the exponent 4k+2 than n, and then we do not get more factorizations of the above type.

However, Aurifeuille noted another algebraic factorization of 2^(4k+2) + 1, namely

2^(4k+2) + 1 = (2^(2k+1) - 2^(k+1) + 1)(2^(2k+1) + 2^(k+1) + 1)

For each k, one of the two factors here is necessarily divisible by 5. Then the other may be prime.

We can also write Aurifeuille's factorization with j = k+1 instead:

2^(4j-2) + 1 = (2^(2j-1) - 2^j + 1)(2^(2j-1) + 2^j + 1)

or with n (which is odd):

2^(2n) + 1 = (2^n - 2^((n+1)/2) + 1)(2^n + 2^((n+1)/2) + 1)

Let n be this odd number. The relation to Mersenne primes, as explained on Caldwell's page linked by carpetpool and Batalov above, is that the complex number (1+i)^n - 1 where i is a square root of minus one, is a prime in the ring of Gaussian integers exactly if the one of Aurifeuille's factors which is not a multiple of 5, is an ordinary prime.

The classical (https://en.wikipedia.org/wiki/Aurife...zation#History) example is n = 29 (so k=14 and j=15) where Aurifeuille says:

2^58 + 1 = (2^29 - 2^15 + 1)(2^29 + 2^15 + 1)

where the latter factor is prime (so a Gaussian Mersenne norm prime corresponding to the Gaussian prime (1+i)^29 - 1 where i is either of the two square roots of minus one).

/JeppeSN

2020-06-11, 23:46	#1
jshort "James Short" Mar 2019 Canada 17 Posts	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!).

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Smallest prime of the form a^2^m + b^2^m, m>=14	JeppeSN	Math	114	2018-12-16 01:57
Probability that N is prime given each divisor of N has the form 2kp+1	carpetpool	Miscellaneous Math	6	2017-09-01 13:59
Most Abundant form of Prime Numbers	a1call	Information & Answers	17	2017-02-26 22:01
Is there a prime of the form......	PawnProver44	Miscellaneous Math	9	2016-03-19 22:11
Code for testing a prime other than form 2^n-1	MercPrime	Information & Answers	5	2013-05-12 22:03

2020-06-12, 05:34	#2
carpetpool "Sam" Nov 2016 2²×3⁴ Posts	I think you are referring to Gaussian Mersenne norms.

2020-06-15, 19:07	#4
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2²×23×103 Posts	https://primes.utm.edu/top20/page.php?id=41 https://mersenneforum.org/showthread.php?t=19235 https://oeis.org/A057429 = https://oeis.org/A007670 + https://oeis.org/A007671

2020-06-20, 07:55	#6
JeppeSN "Jeppe" Jan 2016 Denmark 2³×3×7 Posts	If you consider the numbers 2^(4k+2) + 1, there are two kinds of algebraic factorizations for them. One is because 4k+2 = 2(2k+1), so the exponent has an odd divisor, therefore: 2^(4k+2) + 1 = (2^2)^(2k+1) + 1 = (2^2 + 1)[(2^2)^(2k) - (2^2)^(2k-1) + ... - (2^2)^3 + (2^2)^2 - 2^2 + 1] But this simply says that 2^2 + 1 = 5 divides 2^(4k+2) + 1 which is also quite obvious without the factorization above. Set n=2k+1. When n is a prime, there are no other nontrivial odd factors of the exponent 4k+2 than n, and then we do not get more factorizations of the above type. However, Aurifeuille noted another algebraic factorization of 2^(4k+2) + 1, namely 2^(4k+2) + 1 = (2^(2k+1) - 2^(k+1) + 1)(2^(2k+1) + 2^(k+1) + 1) For each k, one of the two factors here is necessarily divisible by 5. Then the other may be prime. We can also write Aurifeuille's factorization with j = k+1 instead: 2^(4j-2) + 1 = (2^(2j-1) - 2^j + 1)(2^(2j-1) + 2^j + 1) or with n (which is odd): 2^(2n) + 1 = (2^n - 2^((n+1)/2) + 1)(2^n + 2^((n+1)/2) + 1) Let n be this odd number. The relation to Mersenne primes, as explained on Caldwell's page linked by carpetpool and Batalov above, is that the complex number (1+i)^n - 1 where i is a square root of minus one, is a prime in the ring of Gaussian integers exactly if the one of Aurifeuille's factors which is not a multiple of 5, is an ordinary prime. The classical (https://en.wikipedia.org/wiki/Aurife...zation#History) example is n = 29 (so k=14 and j=15) where Aurifeuille says: 2^58 + 1 = (2^29 - 2^15 + 1)(2^29 + 2^15 + 1) where the latter factor is prime (so a Gaussian Mersenne norm prime corresponding to the Gaussian prime (1+i)^29 - 1 where i is either of the two square roots of minus one). /JeppeSN