20060418, 15:22  #1 
Feb 2006
3 Posts 
Size of prime factors found by p1 method
Hi,
I have a question concerning the effectiveness of Pollard's p1 method. For which size of prime factors (number of diggits) would one use this method? Thx R. 
20060418, 17:13  #2  
Nov 2003
1110100100100_{2} Posts 
Quote:
any particular sized factor. Generally, one tries trial division first (to say log^2 N), followed by Pollard Rho, followed by P1/P+1. One hopes to simply get lucky with P1 before starting ECM. Running P1 is equivalent to running ECM with just a SINGLE curve. P1 runs a lot faster than ECM, which is why it is worthwhile. P1 can, if you are lucky, rip out a 30 digit factor in a matter of seconds. It can also take a long time to find (say) a 15 digit factor. P1 is especially effective for Cunningham numbers where one knows that the factor lies in a given equivalence class. 

20060418, 17:45  #3 
Feb 2006
3 Posts 
Ok, thanks a lot. Is there nothing to say about the size of the prime factor p if (p1) is smooth and so the P1 method is succesful?

20060418, 18:02  #4  
Nov 2003
2^{2}×5×373 Posts 
Quote:


20060418, 18:43  #5  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
2·5,557 Posts 
Quote:
One can certainly say something about the probability, as a function of smoothness bound B, that a prime p of a given size in bits has p1 which is Bsmooth. As Bob says, running p1 is essentially the same as running a singe ECM curve (if we don't know anything about the structure of possible divisors; the modification is straightforward if structure is known). Tables of success probabilities for ECM curves for particular bounds are easy enough to find. Paul 

20060419, 16:52  #6  
Nov 2003
2^{2}·5·373 Posts 
Quote:
It simply said "smooth". Even with a specified bound, we can't say anything about the size; all we can do is give a probability distribution for the probability of finding factors of different sizes. And this does not really answer the question that I think was intended. 

20060422, 19:49  #7 
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·641 Posts 
Robertcop,
Perhaps an explanation I wrote about P1 a while back may be helpful: http://www.mersenneforum.org/showpos...89&postcount=3 Another way to put it is that trial factoring proceeds in order of increasing size of the factor one seeks, but P1 proceeds in order of increasing size of the largest prime factor of [(the factor one seeks)1]. There's a correlation between the order in which P1 proceeds and the average size of the factor it finds, but it's not direct as it is with trial factoring. Last fiddled with by cheesehead on 20060422 at 20:03 
20060424, 10:50  #8  
Nov 2003
2^{2}·5·373 Posts 
Quote:


20060424, 13:49  #9  
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Quote:
Alex 

20060424, 16:57  #10  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
2·5,557 Posts 
Quote:
Bob, am I right? Paul 

20060430, 22:23  #11  
"Richard B. Woods"
Aug 2002
Wisconsin USA
1111000001100_{2} Posts 
Quote:
B) Suppose, OTOH, that Silverman correctly understood that my posting directed to "Robertcop" was directed to the OP  I have the same question: what did he consider hypocritical? In case Silverman doesn't answer me here, can anyone else propose an explanation? I'm genuinely puzzled. I can conceive that Silverman could consider "Robertcop" to be negative in some way when directed to himself, but I can't think of a plausible reason for his specific response "Hypocrite" rather than something else. Inquiring llamas want to know. :) Last fiddled with by cheesehead on 20060430 at 22:28 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
No factors found  aketilander  PrimeNet  9  20110517 11:32 
CPU Time and Factors Found  Rodrigo  Operation Billion Digits  8  20100814 20:36 
Fermat 12 factors already found?  UberNumberGeek  Factoring  6  20090617 17:22 
ECM Server for Record Size Factors at 8195  wblipp  ElevenSmooth  1  20031125 15:47 
More factors found with a new program  alpertron  ElevenSmooth  8  20031015 10:29 