20070112, 14:08  #1 
Einyen
Dec 2003
Denmark
5631_{8} Posts 
P1
Doing P1 on Cullen numbers: Cn = n*2^n+1, we know the only factors of P1 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 P1 fail? According to: http://www.mersennewiki.org/index.php/P1 it can fail when P1 has a repeated factor above squareroot of B1, but what other conditions can it fail? Last fiddled with by ATH on 20070112 at 14:09 
20070112, 14:18  #2  
Nov 2003
2^{6}·113 Posts 
Quote:
and p1 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 p1 and q1 are smooth, then p1 will pull out the product pq from N. One then separates p and q by appropriate LOWERING of B1 or B2 or both. 

20070112, 14:29  #3 
Einyen
Dec 2003
Denmark
101110011001_{2} Posts 
Thanks for the answer.
What I also meant was, why doesn't P1 always work on cullen numbers? P1 doesn't depend on a random sigma like ECM, only on the smoothness of P1, which for cullen numbers we know. But P1 still fails sometimes even if B1>2, B2>n or even if B1>n. 
20070112, 14:45  #4  
Nov 2003
2^{6}·113 Posts 
Quote:
Certainly if N = n*2^n + 1, then we know the smoothness of N1, but this is *irrelevant*. You want a *factor* p of N to have p1 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 p1 where p  N might be related??? 

20070112, 16:49  #5 
Einyen
Dec 2003
Denmark
B99_{16} Posts 
Sorry nevermind, I just had a "D'oh" moment. I posted without thinking it through. For some reason I thought about p1 must be smooth since n1 is so very smooth. Just delete this thread.

20070112, 18:24  #6  
Aug 2002
Buenos Aires, Argentina
535_{16} Posts 
Quote:


20070112, 18:43  #7  
Nov 2003
2^{6}×113 Posts 
Quote:
It depends on how one forms M, the exponent. One computes GCD(a^M1, 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 p1 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 p1, but M only includes p_i^(R1), then you won't find p. Such instances are very rare. I know of no Cunningham result (for example) where p1 failed because of this. If one is worried about such a failure, then simply increase the a_k. This only slows the algorithm linearly. 

20070112, 19:03  #8 
"Nancy"
Aug 2002
Alexandria
4640_{8} 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)
GMPECM 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 P1, the probability of a prime power q^k dividing p1 is 1/((q1)q^(k1)), 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. GMPECM 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 20070112 at 19:57 Reason: Missing 1/ Thanks, Bob 
20070112, 19:33  #9 
Nov 2003
2^{6}×113 Posts 

20070113, 13:01  #10  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
3·11·307 Posts 
Quote:
A single run of P1 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 P1, 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 

20070113, 16:57  #11 
"William"
May 2003
New Haven
2^{2}×3^{2}×5×13 Posts 
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 P1. I further think the answer is that when N has factors p and q such that the two largest factors of p1 are the same as the two largest factors of q1, P1 will never find p and q. The likelyhood of finding such an N that has not been specially constructed is very small.
