mersenneforum.org > Math factoring composite mersennes
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2022-04-17, 20:15 #1 jshort   "James Short" Mar 2019 Canada 100102 Posts 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$ ?
2022-04-22, 11:41   #2
Dobri

"Καλός"
May 2018

5·73 Posts

Quote:
 Originally Posted by jshort 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];

 2022-04-22, 15:11 #3 Dr Sardonicus     Feb 2017 Nowhere 13·461 Posts 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

 Similar Threads Thread Thread Starter Forum Replies Last Post bur Factoring 14 2021-04-26 18:06 carpetpool carpetpool 7 2017-01-05 04:36 roger Factoring 15 2006-11-29 08:58 mgb Math 3 2006-09-09 10:35 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

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.

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