mersenneforum.org > Math a p+1 factoring test for Mp ?
 Register FAQ Search Today's Posts Mark Forums Read

 2021-01-01, 21:00 #1 bhelmes     Mar 2016 22×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 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
 2021-01-01, 21:30 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 225468 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, f-1 contains p, and (f-1)/p has a significantly better chance of being smooth than any sibling of f.
 2021-05-26, 01:20 #3 ixfd64 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 P-1 while stage 2 is slightly faster. See: https://mersenneforum.org/showpost.p...52&postcount=5
 2021-05-27, 07:16 #4 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 9,791 Posts 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
2021-05-27, 17:32   #5
masser

Jul 2003

2×5×173 Posts

Quote:
 Originally Posted by LaurV 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.

2021-05-27, 17:40   #6
axn

Jun 2003

3×17×101 Posts

Quote:
 Originally Posted by masser 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.

2021-05-28, 13:16   #7
Dr Sardonicus

Feb 2017
Nowhere

2·2,503 Posts

Quote:
Originally Posted by axn
Quote:
 Originally Posted by masser 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]

?

2021-05-28, 14:07   #8
axn

Jun 2003

3·17·101 Posts

Quote:
 Originally Posted by Dr Sardonicus 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.

 2021-05-28, 14:33 #9 axn     Jun 2003 3·17·101 Posts 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.
2021-05-28, 14:42   #10
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

9,791 Posts

Quote:
 Originally Posted by masser 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

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

 Similar Threads Thread Thread Starter Forum Replies Last Post Lorenzo Information & Answers 3 2019-08-07 14:38 tServo Miscellaneous Math 3 2014-04-10 18:52 cmokruhl Software 2 2005-08-03 03:54 Jasmin Hardware 10 2005-02-14 01:58 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