mersenneforum.org  

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

Reply
 
Thread Tools
Old 2021-08-28, 23:15   #12
Dobri
 
May 2018

193 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
The question of whether factoring Mp - 1 would help in factoring Mp was discussed on this very forum about a year ago, here. It specifically mentions the exponent 1277. And, as of this posting, the thread title is still visible on the Mersenne Forum home page.
The short answer to the question is "No."
Thank you for providing a link to a previous thread, of which I was unaware about, discussing this matter.
I did not intend to create a separate thread or provide extensive details on a work in progress but rather to post a few hints and see if there are similar attempts for factorization of composite Mersenne numbers.
One heuristic scheme I am currently testing and modifying is to use the factors of 2p-1-1 (which are obviously coprime with Mp) as a factor base in a version of the rational sieve and proceed in a series of iterations in potentially finding factors of Mp. As pointed out in a previous post, the factors of 2p+1-1 are also known. This gives me an idea to attempt a hybrid rational sieve using a combined factor base.
Dobri is offline   Reply With Quote
Old 2021-08-28, 23:32   #13
Dobri
 
May 2018

19310 Posts
Default

Quote:
Originally Posted by tuckerkao View Post
x11-1 = didn't get any Google Search results, but since there are answers for x5-1 and x5+1, the same patterns should be observable.
x11 - 1 = (x - 1)(x10 + x9 + x8 + x7 + x6 + x5 + x4 + x3 + x2 + x + 1)
https://mathworld.wolfram.com/GeometricSeries.html
https://www.wolframalpha.com/input/?i=x%5E11-1
Dobri is offline   Reply With Quote
Old 2021-08-29, 00:33   #14
tuckerkao
 
"Tucker Kao"
Jan 2020
Head Base M168202123

48710 Posts
Default

22^n + 1 have the higher chance to be a prime.

I always wondering why nobody is testing 3n - 2 or 3n + 2.

Last fiddled with by tuckerkao on 2021-08-29 at 00:34
tuckerkao is offline   Reply With Quote
Old 2021-08-29, 00:36   #15
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

23·5·17 Posts
Default

Quote:
Originally Posted by tuckerkao View Post
...
x2p±1-1 = Always composite
Nope. 22*2-1 - 1 is 23-1, prime. 22*3-1 - 1 is 25-1, prime. 22*3+1 - 1 is 27-1, prime. 22*7-1 - 1 is 213-1, prime.
Viliam Furik is online now   Reply With Quote
Old 2021-08-29, 00:40   #16
tuckerkao
 
"Tucker Kao"
Jan 2020
Head Base M168202123

7478 Posts
Default

Quote:
Originally Posted by Viliam Furik View Post
Nope. 22*2-1 - 1 is 23-1, prime. 22*3-1 - 1 is 25-1, prime. 22*3+1 - 1 is 27-1, prime. 22*7-1 - 1 is 213-1, prime.
I think I've made the error by not knowing how to put the powers in 2 layers. For some reason SUP & /SUP doesn't work inside another SUP & /SUP bracket.

x2^(p+1)-1 = Maybe a Prime
x2^(p-1)-1 = Always composite, p > 3
x2^p+1-1 = Always composite, p ≥ 3
x2^p-1-1 = Maybe a Prime

Last fiddled with by tuckerkao on 2021-08-29 at 01:10
tuckerkao is offline   Reply With Quote
Old 2021-08-29, 05:52   #17
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

23×5×157 Posts
Default

Quote:
Originally Posted by tuckerkao View Post
For some reason SUP & /SUP doesn't work inside another SUP & /SUP bracket.
Nesting BB code used to work in the past, some older posts do that. But an "upgrade" sometime ago broke it.
retina is offline   Reply With Quote
Old 2021-08-29, 13:57   #18
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×47×53 Posts
Default

Quote:
Originally Posted by tuckerkao View Post
<snip>
x2p+1 = Maybe a prime
<snip>
Did you mean x2^p + 1?
Dr Sardonicus is offline   Reply With Quote
Old 2021-08-29, 16:10   #19
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

115668 Posts
Default

Quote:
Originally Posted by Dobri View Post
Thank you for providing a link to a previous thread, of which I was unaware about, discussing this matter.
<snip>
So, you didn't even bother reading the thread titles listed on the Mersenne Forum home page.
Quote:
One heuristic scheme I am currently testing and modifying is to use the factors of 2p-1-1 (which are obviously coprime with Mp) as a factor base in a version of the rational sieve
Good luck with that.
Dr Sardonicus is offline   Reply With Quote
Old 2021-08-29, 18:29   #20
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·52·43 Posts
Default

FWIW, for odd positive integers a, b & n = a*b, there are relationships between the factors of n-1 and factors of n which can be used to make the solution-space for factors of n smaller. However this reduction may or may not be marginal. Unfortunately for large composites it often (but not always) is.
For example:
GCD(a-1,n-1) == GCD(b-1,n-1)
always holds true.

Example:
65341= 361*181 => gcd(65341-1, 361-1) == gcd(65341-1, 181-1) == 180 => 65341 == (2*180+1) * (1*180+1)



Pari-GP code:
Code:
\\EDE-100-A Relevance of factors of n-1 to factors of n by Rashid Naimi 2021/8/29
\\ The following Pari-GP code shows that for odd positive integers a, b & n= a*b, GCD(a-1,n-1) == GCD(b-1,n-1)
runningN = 1
runningGcd = 1
theExp = 2 \\determines the upper range for both a & b
forstep(a=3,19^theExp ,2,{
    forstep(b=3,19^theExp ,2,
        n=a*b;
        ag=gcd(a-1,n-1);
        bg=gcd(b-1,n-1);
        if(ag > runningGcd && !ispower(n),
            runningN =n;
            runningGcd =ag;
        );
        print("** ",n," >> ",ag);
        if(ag != bg,
            print("**** Counterexample ****");
            next(19); \\\\ Halt RUN if a counterexample is found
        );
    );
})

print("***** ",runningN ," >> ",runningGcd );
factor(runningN)

Last fiddled with by a1call on 2021-08-29 at 18:32
a1call is offline   Reply With Quote
Old 2021-08-31, 01:19   #21
tuckerkao
 
"Tucker Kao"
Jan 2020
Head Base M168202123

487 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
Did you mean x2^p + 1?
That was what I meant to type in, but the script coding seemed to take the inner layer out, thus the entire expression looked like another equation.
tuckerkao is offline   Reply With Quote
Old 2021-08-31, 01:42   #22
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·47·53 Posts
Default

Quote:
Originally Posted by tuckerkao View Post
Quote:
Originally Posted by Dr Sardonicus View Post
Did you mean x2^p + 1?
That was what I meant to type in, but the script coding seemed to take the inner layer out, thus the entire expression looked like another equation.
Yes, some bbcode tags inside of bbcode tags don't work.

I advise you to hit "Preview Post," and check the preview every time before you post a message. That way, you won't have to bother trying to remember which nested bbcode tags work and which ones don't. If any nested bbcodes are squirrelly, you'll see it in the preview window. You can then edit the message in the Message window (NOT the Preview window). You can check "Preview Message" repeatedly and edit repeatedly until it looks satisfactory, before you hit "Submit Reply."
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sieving success as a heuristic for odds of a prime diep Probability & Probabilistic Number Theory 0 2020-11-21 17:14
rogue's sieves rogue And now for something completely different 4 2017-07-31 19:36
Experimenting with ksieve Cruelty Riesel Prime Search 18 2006-06-25 03:44

All times are UTC. The time now is 18:11.


Tue Oct 19 18:11:05 UTC 2021 up 88 days, 12:40, 0 users, load averages: 1.59, 1.38, 1.22

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.