Size of prime factors found by p-1 method

[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.

[R.D. Silverman]

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.

[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?

[R.D. Silverman]

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.

[xilman]

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

[R.D. Silverman]

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.

[cheesehead]

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.

[R.D. Silverman]

Originally Posted by cheesehead

Robertcop,

Hypocrite.

[akruppa]

Originally Posted by R.D. Silverman

Hypocrite.

Why?

Alex

[xilman]

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

[cheesehead]

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. :)