mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2022-04-17, 20:15   #1
jshort
 
"James Short"
Mar 2019
Canada

100102 Posts
Default factoring composite mersennes

Suppose M_{p} = 2^{p} - 1 is composite for prime p and define the iteration function f(x_{n+1}) = (x_{n}^{12p \cdot 5} - 1) \cdot (x_{n}^{12p \cdot 7} - 1) + 1mod(M_{p}) with x_{0} = 3. Does there exist some integer N_{p} such that for all i > N_{p}, we have gcd(x_{i} - 1,M_{p}) \neq 1 ?
jshort is offline   Reply With Quote
Old 2022-04-22, 11:41   #2
Dobri
 
"Καλός"
May 2018

5·73 Posts
Default

Quote:
Originally Posted by jshort View Post
Suppose M_{p} = 2^{p} - 1 is composite for prime p and define the iteration function f(x_{n+1}) = (x_{n}^{12p \cdot 5} - 1) \cdot (x_{n}^{12p \cdot 7} - 1) + 1mod(M_{p}) with x_{0} = 3. Does there exist some integer N_{p} such that for all i > N_{p}, we have gcd(x_{i} - 1,M_{p}) \neq 1 ?
Here is a Wolfram code to test the quoted heuristic recursion.
Code:
p = 1277; Mn = 2^p - 1; xn = 3;
While[(GCD[xn - 1, Mn] == 1) && (xn != 0), xn = Mod[(xn^(12*p*5) - 1)*(xn^(12*p*7) - 1) + 1, Mn];];
Print[xn];
Dobri is offline   Reply With Quote
Old 2022-04-22, 15:11   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

13·461 Posts
Default

I think you mean

x_{n+1}\;=\;\(x_{n}^{60p}\;-\;1\)\(x_{n}^{84p}\;-\;1\)\;+\;1

where x0 is Mod(3,2^p - 1).

I am not certain, but I suspect the answer is "yes."

A prime factor q of 2^p - 1 divides the gcd of (the lift of) xn+1 - 1 and 2^p - 1 when xn+1 is 1 (mod q). When that happens, all further x's will also be 1 (mod q), so q will divide the gcd forever after.

So if the gcd becomes greater than 1 at some point, it stays greater than 1 after that point.

We know that q = 2*k*p + 1. If 2*k divides either 60 or 84, x60p or x84p will automatically be 1 (mod q) [assuming x is not 0 (mod q).]

In fact, we know that for p > 2, q == 1 or 7 (mod 8), which means k would have to divide 15 or 21; k = 1, 3, 5, 7, 15, or 21. If q = 2*k*p + 1 happens to be a factor of Mp for one of these k, it will divide the first gcd. However, trial factoring would almost certainly be faster.

In addition, if xn happens to hit one of the values 2, 4, ..., 2^p-1 (mod 2^p - 1), then xn+1 will be 1 (mod 2^p - 1) whether this is prime or composite.

For example with p = 7, x1 = Mod(4,127) so x2 and all further x's will be 1 (mod 127).

The recursion is unmotivated at this point, and the iterations are expensive to compute.


EDIT: My suspicion was wrong. The answer to your question is "no."

The first prime Mersenne number for which the gcd remains 1 forever is for p = 17. After a while, the iteration cycles through 13 values.
Code:
? p=17;a=2^p-1;m=Mod(3,a);v=vector(100);for(i=1,100,m=(m^(60*p)-1)*(m^(84*p)-1)+1;v[i]=lift(m);g=gcd(lift(m)-1,a);if(g>1,print(c" "g)))
? for(i=1,#v-1,for(j=i+1,#v,if(v[i]==v[j],print(i" "j);break(2))))
20 33
? for(i=20,33,print(i" "v[i]))
20 87019
21 21750
22 15865
23 46346
24 89767
25 85845
26 68218
27 113345
28 47439
29 35712
30 26871
31 12601
32 121150
33 87019
?
The first counterexample I found for a composite Mersenne number was for p = 41. What happens is that after some time, the iteration begins repeating the same ten values. No gcd greater than 1 ever shows up.
Code:
? p=41;a=2^p-1;m=Mod(3,a);v=vector(1000);for(i=1,1000,m=(m^(60*p)-1)*(m^(84*p)-1)+1;v[i]=lift(m);g=gcd(lift(m)-1,a);if(g>1,print(c" "g)))
? for(i=1,#v-1,for(j=i+1,#v,if(v[i]==v[j],print(i" "j);break(2))))
655 665
? for(i=655,666,print(i" "v[i]))
655 1070040474851
656 2109318288198
657 1990816244601
658 70809791609
659 509766907190
660 1942949745660
661 673267198969
662 396358531829
663 1458749118825
664 434250274170
665 1070040474851
666 2109318288198

? print(factor(2^41-1))
[13367, 1; 164511353, 1]
?

Last fiddled with by Dr Sardonicus on 2022-04-23 at 13:40
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Doing P-1 on known composite Mersennes bur Factoring 14 2021-04-26 18:06
Composite integers n satisfying prime exponents of Mersennes carpetpool carpetpool 7 2017-01-05 04:36
Factoring non-form composite roger Factoring 15 2006-11-29 08:58
Factoring with Highly Composite Modulus mgb Math 3 2006-09-09 10:35
Factoring Double mersennes Citrix Miscellaneous Math 2 2005-10-04 08:08

All times are UTC. The time now is 17:00.


Mon Oct 3 17:00:56 UTC 2022 up 46 days, 14:29, 1 user, load averages: 1.33, 1.29, 1.22

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔