mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2007-01-12, 14:08   #1
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

56318 Posts
Default P-1

Doing P-1 on Cullen numbers: Cn = n*2^n+1, we know the only factors of P-1 is 2 and n, so we can choose B1>2 and B2>n or even B1>n and B2>B1 if n is not too large.

But still this doesn't always work, under what condition does P-1 fail?

According to:
http://www.mersennewiki.org/index.php/P-1

it can fail when P-1 has a repeated factor above squareroot of B1, but what other conditions can it fail?

Last fiddled with by ATH on 2007-01-12 at 14:09
ATH is offline   Reply With Quote
Old 2007-01-12, 14:18   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by ATH View Post
Doing P-1 on Cullen numbers: Cn = n*2^n+1, we know the only factors of P-1 is 2 and n, so we can choose B1>2 and B2>n or even B1>n and B2>B1 if n is not too large.

But still this doesn't always work, under what condition does P-1 fail?

According to:
http://www.mersennewiki.org/index.php/P-1

it can fail when P-1 has a repeated factor above squareroot of B1, but what other conditions can it fail?
The Wiki is wrong. It does not fail. If an integer N = p^2 qrs... (say)
and p-1 is appropriately smooth, then the algorithm simply pulls out p^2
instead of p. You then just compute a square root.

Similarly of N = pqrs.... and (say) both p-1 and q-1 are smooth,
then p-1 will pull out the product pq from N. One then separates
p and q by appropriate LOWERING of B1 or B2 or both.
R.D. Silverman is offline   Reply With Quote
Old 2007-01-12, 14:29   #3
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

1011100110012 Posts
Default

Thanks for the answer.

What I also meant was, why doesn't P-1 always work on cullen numbers? P-1 doesn't depend on a random sigma like ECM, only on the smoothness of P-1, which for cullen numbers we know. But P-1 still fails sometimes even if B1>2, B2>n or even if B1>n.
ATH is offline   Reply With Quote
Old 2007-01-12, 14:45   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by ATH View Post
Thanks for the answer.

What I also meant was, why doesn't P-1 always work on cullen numbers? P-1 doesn't depend on a random sigma like ECM, only on the smoothness of P-1, which for cullen numbers we know. But P-1 still fails sometimes even if B1>2, B2>n or even if B1>n.
Huh? How do you know the a priori smoothness of p-1?

Certainly if N = n*2^n + 1, then we know the smoothness of N-1,
but this is *irrelevant*. You want a *factor* p of N to have p-1 be
smooth and this has NOTHING to do with the smoothness of N.

Why would anyone ever think that the smoothness of N and
the smoothness of p-1 where p | N might be related???
R.D. Silverman is offline   Reply With Quote
Old 2007-01-12, 16:49   #5
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

B9916 Posts
Default

Sorry nevermind, I just had a "D'oh" moment. I posted without thinking it through. For some reason I thought about p-1 must be smooth since n-1 is so very smooth. Just delete this thread.
ATH is offline   Reply With Quote
Old 2007-01-12, 18:24   #6
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

53516 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Quote:
Originally Posted by ATH View Post
According to:
http://www.mersennewiki.org/index.php/P-1

it can fail when P-1 has a repeated factor above squareroot of B1
The Wiki is wrong. It does not fail. If an integer N = p^2 qrs... (say)
and p-1 is appropriately smooth, then the algorithm simply pulls out p^2
instead of p. You then just compute a square root.
Please notice that the wiki talks about the factors of p-1, not of N. If p-1 has a repeated prime factor f greater than \sqrt{B1} you will not be able to find it because the exponent E (using the wiki notation) will include the factor f once, so a^E\not\equiv 1 in that case (unless you were extremely lucky in selecting the number a). Thus the gcd will be equal to 1, and no factors of N will be found.
alpertron is offline   Reply With Quote
Old 2007-01-12, 18:43   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by alpertron View Post
Please notice that the wiki talks about the factors of p-1, not of N. If p-1 has a repeated prime factor f greater than \sqrt{B1} you will not be able to find it because the exponent E (using the wiki notation) will include the factor f once, so a^E\not\equiv 1 in that case (unless you were extremely lucky in selecting the number a). Thus the gcd will be equal to 1, and no factors of N will be found.

It depends on how one forms M, the exponent. One computes
GCD(a^M-1, N) with M = 2^a_1 3^a_2 5^a_3 7^a_4 .......p_k^a_k
for chosen a_k. We do not naiively take M = p_k#.

Of course if one chooses a_i = 1 for some primes, and p_i divides p-1
more than once, then one will fail to find p. This is remedied by taking a_i > 1.

Yes, if p_i ^R exactly divides p-1, but M only includes p_i^(R-1),
then you won't find p. Such instances are very rare. I know of no
Cunningham result (for example) where p-1 failed because of this.
If one is worried about such a failure, then simply increase the a_k.
This only slows the algorithm linearly.
R.D. Silverman is offline   Reply With Quote
Old 2007-01-12, 19:03   #8
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

46408 Posts
Default

Peter Montgomery once suggested on the GIMPS mailing list to use a_i = floor(1.5 * log_{p_i}(B1)), i.e. include prime powers up to B1^(1.5). (I'm not 100% sure of the constant 1.5, but it was in that ballpark)

GMP-ECM and, afaik, Prime95 both include only prime powers ≀B1. The extra cost of including slightly larger powers is very small, but so is the extra chance of finding factors.

For P-1, the probability of a prime power q^k dividing p-1 is 1/((q-1)q^(k-1)), so if we want to include all primes and prime powers that have a probability better than some constant c, we might want to include some very small primes in a power "one greater". Again, the effect on the probability of success is miniscule for reasonable B1 values.

For ECM, we know that 12 divides the order, and 3 appears in an exponent even higher than the 3/2 one might expect, on average. GMP-ECM and, afaik, Prime95 don't include 2 or 3 in a higher power than the highest power not exceeding B1. For small B1 values, it would make sense to do so, but for the B1 used for factoring Cunningham numbers etc., the effect is again miniscule. For very small B1, as might be used for factoring residuals in NFS sieving, taking into account the higher average exponent for 2 and 3 should be worthwhile.

Alex

Last fiddled with by akruppa on 2007-01-12 at 19:57 Reason: Missing 1/ Thanks, Bob
akruppa is offline   Reply With Quote
Old 2007-01-12, 19:33   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by akruppa View Post
For P-1, the probability of a prime power q^k dividing p-1 is (q-1)q^(k-1),

Alex
Huh???

Hint: Your "probability" as given is an integer greater than 1!!!

It should be 1/[your expression] assuming that q does not divide p.
[remember that p need not be prime]
R.D. Silverman is offline   Reply With Quote
Old 2007-01-13, 13:01   #10
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

3·11·307 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
The Wiki is wrong. It does not fail. If an integer N = p^2 qrs... (say)
and p-1 is appropriately smooth, then the algorithm simply pulls out p^2
instead of p. You then just compute a square root.

Similarly of N = pqrs.... and (say) both p-1 and q-1 are smooth,
then p-1 will pull out the product pq from N. One then separates
p and q by appropriate LOWERING of B1 or B2 or both.
Both of you are right and both of you are wrong!

A single run of P-1 can fail to find a prime factor by discovering a factorization into two composites. In this case, the Wiki is right and you are wrong.

Multiple runs of P-1, with different parameters on each run, can always find a prime factor (and can find all of them). In this circumstance the Wiki is wrong and you are right.


Paul
xilman is offline   Reply With Quote
Old 2007-01-13, 16:57   #11
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22×32×5×13 Posts
Default

Quote:
Originally Posted by xilman View Post
Multiple runs of P-1, with different parameters on each run, can always find a prime factor (and can find all of them).
My copy of C&P is on walk about right now, but I think I recall a problem that is to show there are numbers that cannot be factored by P-1. I further think the answer is that when N has factors p and q such that the two largest factors of p-1 are the same as the two largest factors of q-1, P-1 will never find p and q. The likelyhood of finding such an N that has not been specially constructed is very small.
wblipp is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 03:59.

Sat Oct 31 03:59:56 UTC 2020 up 51 days, 1:10, 2 users, load averages: 2.06, 2.21, 2.15

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