mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2006-04-18, 15:22   #1
Robertcop
 
Feb 2006

316 Posts
Default 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.
Robertcop is offline   Reply With Quote
Old 2006-04-18, 17:13   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2006-04-18, 17:45   #3
Robertcop
 
Feb 2006

3 Posts
Default

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?
Robertcop is offline   Reply With Quote
Old 2006-04-18, 18:02   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2006-04-18, 18:43   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

1068210 Posts
Default

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
xilman is offline   Reply With Quote
Old 2006-04-19, 16:52   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2006-04-22, 19:49   #7
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

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
cheesehead is offline   Reply With Quote
Old 2006-04-24, 10:50   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

Quote:
Originally Posted by cheesehead
Robertcop,
Hypocrite.
R.D. Silverman is offline   Reply With Quote
Old 2006-04-24, 13:49   #9
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

1001101000112 Posts
Default

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

Alex
akruppa is offline   Reply With Quote
Old 2006-04-24, 16:57   #10
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

101001101110102 Posts
Default

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
xilman is offline   Reply With Quote
Old 2006-04-30, 22:23   #11
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

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
cheesehead is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
No factors found aketilander PrimeNet 9 2011-05-17 11:32
CPU Time and Factors Found Rodrigo Operation Billion Digits 8 2010-08-14 20:36
Fermat 12 factors already found? UberNumberGeek Factoring 6 2009-06-17 17:22
ECM Server for Record Size Factors at 8195 wblipp ElevenSmooth 1 2003-11-25 15:47
More factors found with a new program alpertron ElevenSmooth 8 2003-10-15 10:29

All times are UTC. The time now is 10:11.

Thu May 13 10:11:38 UTC 2021 up 35 days, 4:52, 1 user, load averages: 2.43, 2.10, 1.93

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