"I am experimenting with heuristic sieves."

[Dobri]

Originally Posted by Dr Sardonicus

The question of whether factoring M_p - 1 would help in factoring M_p 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 2^p-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 2^p+1-1 are also known. This gives me an idea to attempt a hybrid rational sieve using a combined factor base.

[Dobri]

Originally Posted by tuckerkao

x¹¹-1 = didn't get any Google Search results, but since there are answers for x⁵-1 and x⁵+1, the same patterns should be observable.

x¹¹ - 1 = (x - 1)(x¹⁰ + x⁹ + x⁸ + x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² + x + 1)
https://mathworld.wolfram.com/GeometricSeries.html
https://www.wolframalpha.com/input/?i=x%5E11-1

[tuckerkao]

2^{2^n} + 1 have the higher chance to be a prime.

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

[Viliam Furik]

Originally Posted by tuckerkao

...
x^2p±1-1 = Always composite

Nope. 2^2*2-1 - 1 is 2³-1, prime. 2^2*3-1 - 1 is 2⁵-1, prime. 2^2*3+1 - 1 is 2⁷-1, prime. 2^2*7-1 - 1 is 2¹³-1, prime.

[tuckerkao]

Originally Posted by Viliam Furik

Nope. 2^2*2-1 - 1 is 2³-1, prime. 2^2*3-1 - 1 is 2⁵-1, prime. 2^2*3+1 - 1 is 2⁷-1, prime. 2^2*7-1 - 1 is 2¹³-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.

x^{2^(p+1)}-1 = Maybe a Prime
x^{2^(p-1)}-1 = Always composite, p > 3
x^{2^p+1}-1 = Always composite, p ≥ 3
x^{2^p-1}-1 = Maybe a Prime

[retina]

Originally Posted by tuckerkao

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.

[Dr Sardonicus]

Originally Posted by tuckerkao

<snip>
x^2p+1 = Maybe a prime
<snip>

Did you mean x^{2^p} + 1?

[Dr Sardonicus]

Originally Posted by Dobri

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.

One heuristic scheme I am currently testing and modifying is to use the factors of 2^p-1-1 (which are obviously coprime with Mp) as a factor base in a version of the rational sieve

Good luck with that.

[a1call]

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:

\\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)

[tuckerkao]

Originally Posted by Dr Sardonicus

Did you mean x^{2^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.

[Dr Sardonicus]

Originally Posted by tuckerkao

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."