mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2021-01-01, 21:00   #1
bhelmes
 
bhelmes's Avatar
 
Mar 2016

22×89 Posts
Default a p+1 factoring test for Mp ?

A peaceful and pleasent new year 2021,


Is a p+1 factoring test for Mp possible or not ?

You could use complex numbers and make a similar factoring test like p-1.

In the section math there is no description about it

and I see no argument why this should not be possible.

Thanks if you spend me some lines.

Bernhard
bhelmes is offline   Reply With Quote
Old 2021-01-01, 21:30   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

225468 Posts
Default

Using Mp and p+1 in one sentence has an unintended consequence that your brain initially assumes that "p" is the same.
You should have phrased you question that (assumed) you mean Williams's p+1 algorithm. Where "p" is actually "f", i.e. the factor to be found.

It is possible but will be comparable to ecm. f+1 has the same chances to be smooth as any other number of the same size.*
Except you can run many ecm curves, but only one p+1 "curve".
_____
*compare: for Mersennes, f-1 contains p, and (f-1)/p has a significantly better chance of being smooth than any sibling of f.
Batalov is offline   Reply With Quote
Old 2021-05-26, 01:20   #3
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

2×17×71 Posts
Default

P+1 can be used to factor Mersenne numbers. Stage 1 takes a little less than twice as long as P-1 while stage 2 is slightly faster.

See: https://mersenneforum.org/showpost.p...52&postcount=5
ixfd64 is offline   Reply With Quote
Old 2021-05-27, 07:16   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

9,791 Posts
Default

That's not what Serge said.

The "p" in P-1 and P+1 is the prime (or not) factor you look for (in fact, p stands for "Pollard", the guy who invented/refined the algorithms, and it is a misconception that it stands for "prime", but we will go with it for now). The P-1 (respective P+1) methods will find a prime factor p of any number (not necessary mersenne), if p-1 (respective p+1) is "smooth enough" - whatever that means, it is not the goal here to teach Pollard factorization algorithms, the idea is that "p" represents the prime factor we look for.

On the other hand, for mersenne numbers, p is the exponent, while the factor we are hunting for is commonly denoted q. (i.e. q=1 mod 8, or q=2kp+1, etc). Therefore, when you talk about p-1 (or p+1) for mersenne numbers Mp, you in fact talk about two different p's. The name is quite confusing, as you do not refer to the (known) exponent p, but to the (unknown) factor q that you hunt for.

That is why I jokingly (and without any disrespect for Mr. Pollard) proposed in the past that, when referring to mersenne numbers, to call this method Q-1. It would be more clear, avoid any confusion, stick with the common notation, etc. The discussion is here on the forum, around somewhere. But unfortunately, "it didn't catch"

Last fiddled with by LaurV on 2021-05-27 at 07:20
LaurV is online now   Reply With Quote
Old 2021-05-27, 17:32   #5
masser
 
masser's Avatar
 
Jul 2003
wear a mask

2×5×173 Posts
Default

Quote:
Originally Posted by LaurV View Post
That is why I jokingly (and without any disrespect for Mr. Pollard) proposed in the past that, when referring to mersenne numbers, to call this method Q-1. It would be more clear, avoid any confusion, stick with the common notation, etc. The discussion is here on the forum, around somewhere. But unfortunately, "it didn't catch"
I always think of the factoring methods as F-1 and F+1, where F stands for factor, which may or may not be prime.
masser is online now   Reply With Quote
Old 2021-05-27, 17:40   #6
axn
 
axn's Avatar
 
Jun 2003

3×17×101 Posts
Default

Quote:
Originally Posted by masser View Post
I always think of the factoring methods as F-1 and F+1, where F stands for factor, which may or may not be prime.
Definitely needs to be prime.
axn is online now   Reply With Quote
Old 2021-05-28, 13:16   #7
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·2,503 Posts
Default

Quote:
Originally Posted by axn View Post
Quote:
Originally Posted by masser View Post
I always think of the factoring methods as F-1 and F+1, where F stands for factor, which may or may not be prime.
Definitely needs to be prime.


Many reports to the "fond of a factor? ..." thread, e.g. this one for M103830131 give composite factors, apparently found by P-1.

As I understand it, the method can find the factor P (or F or divisor D) if P-1 (F-1, D-1) is "smooth enough." Similarly with P+1 (F+1, D+1). Of course, P-1 (F-1, D-1) will always have the exponent as a factor.

The factorizations of f-1 for the composite factor f, and of q1 - 1 and q2-1 for its prime factors q1 and q2 are as follows. I note that for q1-1 and q2-1, the exponent 103830131 is the largest factor. I note that (q1 - 1)/103830131 and (q2 - 1)103830131 are a bit "smoother" than (f-1)/103830131, but the latter only has one prime factor larger than 103830131.
Code:
? f= 199531333730879095999006796725214407904194653871;factor(f-1)
%1 = 
[2 1]

[3 1]

[5 1]

[11 1]

[190573 1]

[1235887 1]

[103830131 1]

[24724847920361120655726019 1]

? q1=415767534785818078323247;q2=479910808412848576977793;factor(q1-1)
%2 = 
[2 1]

[3 1]

[431 1]

[1187 1]

[2089 1]

[624467 1]

[103830131 1]

? factor(q2-1)
%3 = 
[2 7]

[3 1]

[19 1]

[720773 1]

[878929 1]

[103830131 1]

?
Dr Sardonicus is offline   Reply With Quote
Old 2021-05-28, 14:07   #8
axn
 
axn's Avatar
 
Jun 2003

3·17·101 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post


Many reports to the "fond of a factor? ..." thread, e.g. this one for M103830131 give composite factors, apparently found by P-1.

As I understand it, the method can find the factor P (or F or divisor D) if P-1 (F-1, D-1) is "smooth enough." Similarly with P+1 (F+1, D+1). Of course, P-1 (F-1, D-1) will always have the exponent as a factor.
The method(s) will find composite factor if all the individual prime factors are appropriately smooth. The smoothness of the composite factor itself is irrelevant. You can make up examples and try it out yourself.
axn is online now   Reply With Quote
Old 2021-05-28, 14:33   #9
axn
 
axn's Avatar
 
Jun 2003

3·17·101 Posts
Default Oh, what the hell. Let me try.

Let F = 97#+1 = 2305567963945518424753102147331756071 = 2336993 · 13848803 · 71237436024091007473549

q1-1 = 2336993-1 = 2^5 · 7 · 10433

q2-1 = 13848803-1 = 2 · 11 · 629491

q3-1 = 71237436024091007473549-1 = 2^2 · 3 · 37 · 2029 · 740533 · 106782195581

Let N=F*M89

Let's try with F-1 as the exponent
Code:
? N=2305567963945518424753102147331756071 *  618970019642690137449562111;
? r=Mod(3,N)^2305567963945518424753102147331756070;
? gcd(N, lift(r)-1)
1
Nope, didn't find it.

Now let's try with something that will find the individual primes, i.e. lcm(q1-1, q2-1, q3-1)

Code:
? l=lcm( lcm(2336993-1, 13848803-1), 71237436024091007473549-1 );
? r=Mod(3,N)^l;
? gcd(N, lift(r)-1)
2305567963945518424753102147331756071
Finds it.
axn is online now   Reply With Quote
Old 2021-05-28, 14:42   #10
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

9,791 Posts
Default

Quote:
Originally Posted by masser View Post
I always think of the factoring methods as F-1 and F+1, where F stands for factor, which may or may not be prime.
The factor must be prime. I see axn replied already, but to state it clear, P-1 method works because of Fermat theorem that says that for any prime q and for any base b coprime with q, we have b^(q-1)=1 (mod q). This allows us to raise the expression to a random power n (which is unknown) and in that case we get b^(n*(q-1)) in the left side, while in the right side we still have 1, because 1 raised to any power still stays 1. So, when we compute b^E in Mr. Pollard's algorithm, where E is a product of a lot of small primes, in case q-1 is "smooth", i.e. also a product of many small primes, we have some high chance that n*(q-1) is part of E, for some n (for a lot of them in fact). In that case, b^E-1 is a multiple of q (because we subtract 1 in both sides and then b^(n*(q-1))-1 (which is b^E-1 for some random n) is zero (mod q) after subtraction on the right side. And if so, then the gcd between b^E-1 and Mp will reveal the factor q.

For a composite q, the theorem doesn't hold (with very few exceptions, the pseudoprimes), we would have to compute b^(eulerphi(q)) which we don't know (if we knew it, we could factor Mp without any of this headache).

It is only for primes q and few pseudoprimes that eulerphi(q) (and respective, the order of b in q) is q-1 or a factor of q-1. Generally, it is not.

Last fiddled with by LaurV on 2021-05-29 at 03:35
LaurV is online now   Reply With Quote
Old 2021-05-29, 23:33   #11
masser
 
masser's Avatar
 
Jul 2003
wear a mask

2·5·173 Posts
Default

Ah, my bad. Thanks for the clarification, axn and LaurV!
masser is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Trial factoring after P1 test Lorenzo Information & Answers 3 2019-08-07 14:38
Yet another new factoring algorithm\primality test:Digital Coding ?? tServo Miscellaneous Math 3 2014-04-10 18:52
Trial factoring/P-1 torture test? cmokruhl Software 2 2005-08-03 03:54
Hardware failure only detected on torture test or also when factoring/LL-testing...? Jasmin Hardware 10 2005-02-14 01:58
I've chosen primality test task, but info shows P-1 factoring! Why ? Unregistered Software 3 2004-02-23 16:45

All times are UTC. The time now is 02:29.


Tue Oct 26 02:29:30 UTC 2021 up 94 days, 20:58, 0 users, load averages: 2.32, 1.86, 1.65

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.