mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > Dobri

Reply
 
Thread Tools
Old 2022-08-12, 09:07   #45
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

236068 Posts
Default

Sorry, busy here around, I just looked for this thread, which you should read carefully, especially from post #32 onward, till the end.
LaurV is offline   Reply With Quote
Old 2022-08-12, 22:37   #46
User140242
 
Jul 2022

22×13 Posts
Default

Quote:
Originally Posted by LaurV View Post
Sorry, busy here around, I just looked for this thread, which you should read carefully, especially from post #32 onward, till the end.

In addition you can calculate the possible remainders and automatically you can find the possible factors:

Code:
tf_c(p,fromk=0,tok=10000)=
{
    PrimesBase=[2,3,5,7,11];
    n_PB=5;
    PrimesBaseProd=2;
    for(i=1,n_PB,PrimesBaseProd*=PrimesBase[i];);
    bW=2*p*PrimesBaseProd;
    RW=List();
    listput(RW,1);
    for(i=1,PrimesBaseProd-1,for(j=1,n_PB,;if(Mod(1+2*p*i,PrimesBase[j])^1==0,break;);if ((j==n_PB)&&(Mod(1+2*p*i,PrimesBase[j])^1!=0)&&(Mod(1+2*p*i,8)^1==1||Mod(1+2*p*i,8)^1==7),listput(RW,1+2*p*i););););
    nR=length(RW);
    for(k=fromk, tok, for(i=1,nR,q=RW[i]+bW*k; if(Mod(2,q)^p==1, if(q>1,print("M"p" has a factor: "q); break;));));
}

Last fiddled with by User140242 on 2022-08-12 at 22:38
User140242 is offline   Reply With Quote
Old 2022-08-13, 03:56   #47
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

236068 Posts
Default

Why would you do that? It will take a lot of time to build that list, and it will find a lot of unneeded composite factors which you need to factor later to find the real prime factors.
LaurV is offline   Reply With Quote
Old 2022-08-13, 06:24   #48
User140242
 
Jul 2022

22×13 Posts
Default

Quote:
Originally Posted by LaurV View Post
Why would you do that? It will take a lot of time to build that list, and it will find a lot of unneeded composite factors which you need to factor later to find the real prime factors.

You can use n_PB as a parameter and if you check the number of remainders that nR uses they are 2 if n_PB = 1, 4 if n_PB = 2, 16 if n_PB = 3, 96 if n_PB = 4 and 960 if n_PB = 5.


That is, it is the same job as creating the table but you can perform an automatic operation as needed.


Of course with this method it checks (tok-fromk)*nR elements instead with forstep it checks (tok-fromk)/nR elements but the factors are the same only the size of the interval changes.


Finally, multiples of small factors can be easily eliminated for each row.



Here you find an example with 2 classes and to speed up we use two vectors for the two classes:
https://gist.github.com/user140242/0...d2738788bb1cae

Last fiddled with by User140242 on 2022-08-13 at 06:45
User140242 is offline   Reply With Quote
Old 2022-08-13, 09:57   #49
User140242
 
Jul 2022

22×13 Posts
Default

Quote:
Originally Posted by User140242 View Post

Finally, multiples of small factors can be easily eliminated for each row.





To extend the example for classes greater than 2 for each class we must use this:

It is possible to eliminate the multiples of the small factors p_j>PrimesBase[n_PB] with p_j<bW and p_j!=p and p_j!=RW[n]
for each RW[i] take a vector FACTOR of size dim_step+1 with dim_step=(tok-fromk) initially set to True

all multiples of p_j can be set to False in this way:



Code:
r_t1=Euclidean_Diophantine(bW,p_j); //function return y in  Diophantine equation  bW * x + p_j * y  = 1
r_t=(r_t1*RW[i])%bW;
if (r_t>0)
    r_t-=bW;
C2=(-bW+p_j)*r_t/bW;
C1=r_t-bW+p_j;
for (m =bW+C1+C2; m<=dim_step && m>=0; m += p_j)
    FACTOR[m] = false;
and then use it in this way to check for possible factors:


Code:
for(k=0;k<=dim_step;k++)
    if (FACTOR[k])
    {
        D=RW[i]+bW*k;
        ....
    }

Last fiddled with by User140242 on 2022-08-13 at 10:15
User140242 is offline   Reply With Quote
Old 2022-08-13, 10:15   #50
Dobri
 
"Καλός"
May 2018

3·112 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
...
For p == 1 (mod 4), this automatically rules out q = 2*k*p + 1 for k = 12*m + 1, 12*m + 5, or 12*m + 9 since 2*k*p + 1 == 3 (mod 8) for such k.
Thanks, this nicely eliminates the cases for k = 12m + 1, 12m + 5, and 12m + 9 indeed.
Quote:
Originally Posted by Dobri View Post
...
2(12m+8)p + 1,
...
2(12m+11)p + 1, m = 0, 1, 2,...,

cannot be factors of M1277.
However, the cases for k = 12m + 8 and 12m + 11 still need a theoretical interpretation.
I do not have a counterexample with p mod 6 = 5 that would result in a prime q = 2kp + 1 for k = 12m + 8 or 12m + 11 that divides 2p - 1.
Currently, I am checking the known prime factors in the GIMPS database for a counterexample.
Such a counterexample with p mod 6 = 5 could be rare or does not exist.
Dobri is offline   Reply With Quote
Old 2022-08-13, 11:10   #51
charybdis
 
charybdis's Avatar
 
Apr 2020

85710 Posts
Default

Quote:
Originally Posted by Dobri View Post
However, the cases for k = 12m + 8 and 12m + 11 still need a theoretical interpretation.
I do not have a counterexample with p mod 6 = 5 that would result in a prime q = 2kp + 1 for k = 12m + 8 or 12m + 11 that divides 2p - 1.
Currently, I am checking the known prime factors in the GIMPS database for a counterexample.
Such a counterexample with p mod 6 = 5 could be rare or does not exist.
These have the simplest explanation of all. If p and k are both 2 mod 3 then 2kp+1 is divisible by 3 and so can't be prime.
charybdis is offline   Reply With Quote
Old 2022-08-14, 07:59   #52
Dobri
 
"Καλός"
May 2018

3·112 Posts
Default

Quote:
Originally Posted by charybdis View Post
These have the simplest explanation of all. If p and k are both 2 mod 3 then 2kp+1 is divisible by 3 and so can't be prime.
Thanks, this flawlessly eliminates the cases for k = 12m + 8 and 12m + 11 indeed.
Also, divisibility by 3 is observed for k = 12m + 5 since 2(12m + 5)(6n + 5) + 1 gives the coefficient 2×5×5 + 1 = 51 which is divisible by 3.
Despite the equivalence between 2 mod 3 and 5 mod 6 (and between 1 mod 3 and 1 mod 6) for prime number considerations, I still use 'mod 6' for uniformity with a few other threads.

What I am trying to evaluate is the additive dependence between the values of k for several factors for a given Mersenne number.
On the basis of quite limited observations for k up to 11 (see posts #29 and #30), the values of k for another factor are obtained as follows:
- the sum of a prime number (or 1) and 2n such as 5 + 22 = 32 and 1 + 23 = 32;
- the sum of 1 and a prime number giving 2n such as 1 + 3 = 22 and 1 + 7 = 23;
- the sum of two prime numbers giving 2n such as 3 + 5 = 23; or
- the sum of 2n and a prime number giving a prime number such as 22 + 3 = 7 and 23 + 3 = 11.

The exhaustive computations for k = 12 are ongoing. The custom source code was modified to collect data not only for p < 109 but also for p < 230.
Dobri is offline   Reply With Quote
Old 2022-08-17, 03:21   #53
Dobri
 
"Καλός"
May 2018

3×112 Posts
Default

For k = 12, all possible pairs of two factors for a given Mersenne number are observed with Δk = 1, 3, 4, 5, 7, 8, 9, and 11, where Δk = k2 - k1 with k2 = 12 and k2 > k1. No cases of three factors for a given Mersenne number are found.

For k = 13, only cases with Δk = 1, 4, 9, and 12 for a given Mersenne number are found, where Δk = k2 - k1 with k2 = 13 and k2 > k1. Here 1 + 12 = 13 and 4 + 9 = 13.
Dobri is offline   Reply With Quote
Old 2022-08-17, 07:37   #54
User140242
 
Jul 2022

22·13 Posts
Default

Quote:
Originally Posted by Dobri View Post
For k = 12, all possible pairs of two factors for a given Mersenne number are observed with Δk = 1, 3, 4, 5, 7, 8, 9, and 11, where Δk = k2 - k1 with k2 = 12 and k2 > k1. No cases of three factors for a given Mersenne number are found.

For k = 13, only cases with Δk = 1, 4, 9, and 12 for a given Mersenne number are found, where Δk = k2 - k1 with k2 = 13 and k2 > k1. Here 1 + 12 = 13 and 4 + 9 = 13.
It is possible to find the values ​​of Δk like this:

if you use a basis bW=2*p*k we have

for k = 12 = 2*2*3

q = r + bW*d where r are the possible remainders with 0 <= r <bW if we consider that q = 1 mod 2p then r = 1 mod 2p

hence r = 1 + 2p*b with 0 <= b < k

so for example if k = 12 and p = 29 the possible remainders are

(1, 59, 117, 175, 233, 291, 349, 407, 465, 523, 581, 639)

from these remainders you have to remove those that have factors in common with bW or remove the multiples of 3 since r = 1 mod 2p

and since bW = 0 mod 8 we must consider that it must be r = 7 mod 8 or r = 1 mod 8 therefore remain

(1, 175, 233, 407) so if you take the indices we find Δk or we consider (r-1)/2/p

(0,3,4,7)

for p = 31 we find (1, 311, 497, 559) or (0, 5, 8, 9)

for p = 37 we find (1, 223, 593, 815) or (0, 3, 8, 11)

for p = 47 we find (1, 95, 377, 847) or (0, 1, 4, 9)

as mentioned in a previous post there are 4 cases based on the value of p%4 and p%6

if k = 13 then bW is not divisible by 8 it is not convenient to use it in any case the procedure does not change

surely you have forgotten some cases for example p=37 and q=223 then k1 = 3 and Δk = 13-3 = 10

Last fiddled with by User140242 on 2022-08-17 at 08:24
User140242 is offline   Reply With Quote
Old 2022-08-17, 10:10   #55
Dobri
 
"Καλός"
May 2018

3×112 Posts
Default

Quote:
Originally Posted by User140242 View Post
...

surely you have forgotten some cases for example p=37 and q=223 then k1 = 3 and Δk = 13-3 = 10
No cases have been forgotten.
In the quoted example, 237-1 = 137438953471, then 13743895347 / 223 = 616318177, and k2 = (616318177-1)/(2×37) = 8328624, thus Δk = 8328624 - 3 = 8328621 = 3×7×396601, which is unrelated to k = 13.
Dobri is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Repeating residues in LL tests of composite Mersenne numbers Viliam Furik Number Theory Discussion Group 22 2020-12-08 14:45
Mersenne number with exponent 333333367 is composite TheGuardian GPU Computing 25 2019-05-09 21:53
Factoring composite Mersenne numbers using Pollard Rho jshort Factoring 9 2019-04-09 16:34
2 holes in bizarre theorem about composite Mersenne Numbers wildrabbitt Math 120 2016-09-29 21:52
Factoring highly composite Mersenne numbers philmoore Factoring 21 2004-11-18 20:00

All times are UTC. The time now is 01:47.


Sat Oct 1 01:47:12 UTC 2022 up 43 days, 23:15, 0 users, load averages: 1.10, 1.15, 1.12

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.

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