mersenneforum.org P-1
 Register FAQ Search Today's Posts Mark Forums Read

 2007-01-12, 14:08 #1 ATH Einyen     Dec 2003 Denmark 56318 Posts 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
2007-01-12, 14:18   #2
R.D. Silverman

Nov 2003

26·113 Posts

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

 2007-01-12, 14:29 #3 ATH Einyen     Dec 2003 Denmark 1011100110012 Posts 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.
2007-01-12, 14:45   #4
R.D. Silverman

Nov 2003

26·113 Posts

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

 2007-01-12, 16:49 #5 ATH Einyen     Dec 2003 Denmark B9916 Posts 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.
2007-01-12, 18:24   #6
alpertron

Aug 2002
Buenos Aires, Argentina

53516 Posts

Quote:
Originally Posted by R.D. Silverman
Quote:
 Originally Posted by ATH 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.

2007-01-12, 18:43   #7
R.D. Silverman

Nov 2003

26×113 Posts

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

 2007-01-12, 19:03 #8 akruppa     "Nancy" Aug 2002 Alexandria 46408 Posts 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
2007-01-12, 19:33   #9
R.D. Silverman

Nov 2003

26×113 Posts

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

2007-01-13, 13:01   #10
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

3·11·307 Posts

Quote:
 Originally Posted by R.D. Silverman 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

2007-01-13, 16:57   #11
wblipp

"William"
May 2003
New Haven

22×32×5×13 Posts

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