20210101, 21:00  #1 
Mar 2016
2^{2}×89 Posts 
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 p1. 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 
20210101, 21:30  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
22546_{8} Posts 
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, f1 contains p, and (f1)/p has a significantly better chance of being smooth than any sibling of f. 
20210526, 01:20  #3 
Bemusing Prompter
"Danny"
Dec 2002
California
2×17×71 Posts 
P+1 can be used to factor Mersenne numbers. Stage 1 takes a little less than twice as long as P1 while stage 2 is slightly faster.
See: https://mersenneforum.org/showpost.p...52&postcount=5 
20210527, 07:16  #4 
Romulan Interpreter
"name field"
Jun 2011
Thailand
9,791 Posts 
That's not what Serge said.
The "p" in P1 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 P1 (respective P+1) methods will find a prime factor p of any number (not necessary mersenne), if p1 (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 p1 (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 Q1. 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 20210527 at 07:20 
20210527, 17:32  #5  
Jul 2003
wear a mask
2×5×173 Posts 
Quote:


20210527, 17:40  #6 
Jun 2003
3×17×101 Posts 

20210528, 13:16  #7  
Feb 2017
Nowhere
2·2,503 Posts 
Quote:
Many reports to the "fond of a factor? ..." thread, e.g. this one for M103830131 give composite factors, apparently found by P1. As I understand it, the method can find the factor P (or F or divisor D) if P1 (F1, D1) is "smooth enough." Similarly with P+1 (F+1, D+1). Of course, P1 (F1, D1) will always have the exponent as a factor. The factorizations of f1 for the composite factor f, and of q1  1 and q21 for its prime factors q1 and q2 are as follows. I note that for q11 and q21, the exponent 103830131 is the largest factor. I note that (q1  1)/103830131 and (q2  1)103830131 are a bit "smoother" than (f1)/103830131, but the latter only has one prime factor larger than 103830131. Code:
? f= 199531333730879095999006796725214407904194653871;factor(f1) %1 = [2 1] [3 1] [5 1] [11 1] [190573 1] [1235887 1] [103830131 1] [24724847920361120655726019 1] ? q1=415767534785818078323247;q2=479910808412848576977793;factor(q11) %2 = [2 1] [3 1] [431 1] [1187 1] [2089 1] [624467 1] [103830131 1] ? factor(q21) %3 = [2 7] [3 1] [19 1] [720773 1] [878929 1] [103830131 1] ? 

20210528, 14:07  #8  
Jun 2003
3·17·101 Posts 
Quote:


20210528, 14:33  #9 
Jun 2003
3·17·101 Posts 
Oh, what the hell. Let me try.
Let F = 97#+1 = 2305567963945518424753102147331756071 = 2336993 · 13848803 · 71237436024091007473549
q11 = 23369931 = 2^5 · 7 · 10433 q21 = 138488031 = 2 · 11 · 629491 q31 = 712374360240910074735491 = 2^2 · 3 · 37 · 2029 · 740533 · 106782195581 Let N=F*M89 Let's try with F1 as the exponent Code:
? N=2305567963945518424753102147331756071 * 618970019642690137449562111; ? r=Mod(3,N)^2305567963945518424753102147331756070; ? gcd(N, lift(r)1) 1 Now let's try with something that will find the individual primes, i.e. lcm(q11, q21, q31) Code:
? l=lcm( lcm(23369931, 138488031), 712374360240910074735491 ); ? r=Mod(3,N)^l; ? gcd(N, lift(r)1) 2305567963945518424753102147331756071 
20210528, 14:42  #10  
Romulan Interpreter
"name field"
Jun 2011
Thailand
9,791 Posts 
Quote:
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 q1 or a factor of q1. Generally, it is not. Last fiddled with by LaurV on 20210529 at 03:35 

20210529, 23:33  #11 
Jul 2003
wear a mask
2·5·173 Posts 
Ah, my bad. Thanks for the clarification, axn and LaurV!

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Trial factoring after P1 test  Lorenzo  Information & Answers  3  20190807 14:38 
Yet another new factoring algorithm\primality test:Digital Coding ??  tServo  Miscellaneous Math  3  20140410 18:52 
Trial factoring/P1 torture test?  cmokruhl  Software  2  20050803 03:54 
Hardware failure only detected on torture test or also when factoring/LLtesting...?  Jasmin  Hardware  10  20050214 01:58 
I've chosen primality test task, but info shows P1 factoring! Why ?  Unregistered  Software  3  20040223 16:45 