mersenneforum.org > Math Size of prime factors found by p-1 method
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2006-04-18, 15:22 #1 Robertcop   Feb 2006 3 Posts Size of prime factors found by p-1 method Hi, I have a question concerning the effectiveness of Pollard's p-1 method. For which size of prime factors (number of diggits) would one use this method? Thx R.
2006-04-18, 17:13   #2
R.D. Silverman

Nov 2003

11101001001002 Posts

Quote:
 Originally Posted by Robertcop Hi, I have a question concerning the effectiveness of Pollard's p-1 method. For which size of prime factors (number of diggits) would one use this method? Thx R.
The question itself is wrong. One does not use P-1 to look for
any particular sized factor.

Generally, one tries trial division first (to say log^2 N), followed by
Pollard Rho, followed by P-1/P+1. One hopes to simply get lucky
with P-1 before starting ECM.

Running P-1 is equivalent to running ECM with just a SINGLE curve.
P-1 runs a lot faster than ECM, which is why it is worthwhile.

P-1 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.
P-1 is especially effective for Cunningham numbers where one knows that
the factor lies in a given equivalence class.

 2006-04-18, 17:45 #3 Robertcop   Feb 2006 3 Posts Ok, thanks a lot. Is there nothing to say about the size of the prime factor p if (p-1) is smooth and so the P-1 method is succesful?
2006-04-18, 18:02   #4
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by Robertcop Ok, thanks a lot. Is there nothing to say about the size of the prime factor p if (p-1) is smooth and so the P-1 method is succesful?
There is nothing meaningful to say.

2006-04-18, 18:43   #5
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

2·5,557 Posts

Quote:
 Originally Posted by R.D. Silverman There is nothing meaningful to say.
I don't think that answer is entirely accurate, at least not with a reasonable interpretation of the question.

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 p-1 which is B-smooth.

As Bob says, running p-1 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

2006-04-19, 16:52   #6
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by xilman I don't think that answer is entirely accurate, at least not with a reasonable interpretation of the question. 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 p-1 which is B-smooth. As Bob says, running p-1 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
Note that the original question did not specify a smoothness bound.
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.

 2006-04-22, 19:49 #7 cheesehead     "Richard B. Woods" Aug 2002 Wisconsin USA 22·3·641 Posts Robertcop, Perhaps an explanation I wrote about P-1 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 P-1 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 P-1 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 2006-04-22 at 20:03
2006-04-24, 10:50   #8
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by cheesehead Robertcop,
Hypocrite.

2006-04-24, 13:49   #9
akruppa

"Nancy"
Aug 2002
Alexandria

2,467 Posts

Quote:
 Originally Posted by R.D. Silverman Hypocrite.
Why?

Alex

2006-04-24, 16:57   #10
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

2·5,557 Posts

Quote:
 Originally Posted by akruppa Why? Alex
Bob almost certainly screwed up. He misinterpreted Cheesehead's salutation to the poster with forum name "Robertcop" as invective directed at himself. Remember that "Bob" is a conventional contraction of "Robert".

Bob, am I right?

Paul

2006-04-30, 22:23   #11

"Richard B. Woods"
Aug 2002
Wisconsin USA

11110000011002 Posts

Quote:
 Originally Posted by xilman Bob, am I right?
A) Suppose that Silverman mistakenly thought my posting directed to Robertcop was really directed to himself rather than to the OP -- why did he respond with "Hypocrite"? What could be considered hypocritical about what I posted?

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 2006-04-30 at 22:28

 Similar Threads Thread Thread Starter Forum Replies Last Post aketilander PrimeNet 9 2011-05-17 11:32 Rodrigo Operation Billion Digits 8 2010-08-14 20:36 UberNumberGeek Factoring 6 2009-06-17 17:22 wblipp ElevenSmooth 1 2003-11-25 15:47 alpertron ElevenSmooth 8 2003-10-15 10:29

All times are UTC. The time now is 00:36.

Mon Jan 17 00:36:48 UTC 2022 up 177 days, 19:05, 0 users, load averages: 1.17, 1.43, 1.39

Copyright ©2000 - 2022, 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.

โ  ยฑ โ รท ร ยท โ โ โฐ โ โ โ โ โ โค โฅ โฆ โง โจ โฉ โบ โป โผ โฝ โ โ โ โ ยฒ ยณ ยฐ
โ  โ ยฐ โ ~ โ โ โซ
โก โ โ โ โ โช โซ โโ โโ โ โ โ โ โง โจ โฉ โช โจ โ โ ๐ ๐ ๐ โฒ โณ
โ โ โ โฆ โฃ โฉ โช โ โ โ โ โ โ โ โ โ โ โ โ โ โ โค โ โ โ โต โถ โท โธ ๐
ยฌ โจ โง โ โ โ โ โ โ โ โ โ โด โต โค โฅ โข โจ โซค โฃ โฆ โฏ โฎ โฐ โฑ
โซ โฌ โญ โฎ โฏ โฐ โ โ ฮด โ โฑ โ โ
๐ข๐ผ ๐ฃ๐ฝ ๐ค๐พ ๐ฅ๐ฟ ๐ฆ๐๐ ๐ง๐ ๐จ๐ ๐ฉ๐๐ ๐ช๐ ๐ซ๐ ๐ฌ๐ ๐ญ๐ ๐ฎ๐ ๐ฏ๐ ๐ฐ๐ ๐ฑ๐ ๐ฒ๐ ๐ด๐ ๐ต๐ ๐ถ๐ ๐ท๐๐ ๐ธ๐ ๐น๐ ๐บ๐