Does a large P-1 test eliminate need for ECM tests

[10metreh]

Originally Posted by FactorEyes

In the spirit of this thread, I would like to add that I am working on a new implementation of Pollard rho which should be able to crack 2^1061-1 on a cluster which I am building in my garage. Using 65,536 CPUs, as well as careful ASM subroutines to take advantage of branch prediction at the hardware level, both P-1 and ECM will be rendered obsolete.

April fools cannot be done after midday.

[FactorEyes]

Originally Posted by 10metreh

April fools cannot be done after midday.

No, really: poor asymptotic behavior is no reason to be discouraged by a particular algorithm. There are always ways to reduce the constant factor.

As a bonus, the assembly code also completely factors the exponents of all known Mersenne primes.

[UberNumberGeek]

Originally Posted by R.D. Silverman

B2 = B1 * 100 is a legacy assertion. It was once true based upon the
fastest ECM implementation at the time (back in the 1980's and early
90's; due to P. Montgomery).

Now, if one wants to OPTIMIZE the parameters using a convolution/FFT
based step 2, then B2 = B1^2 will maximize the per unit time probability
of success. Once, again, you need to read my paper to see the
analysis of why this is true.

My apologies for being at least two decades behind. As the Prime95 software utilizes B2 = B1 * 100 for ECM testing, and that is also what is mentioned in the Elliptic curve method Wiki (http://mersennewiki.org/index.php/Elliptic_curve_method ) as the "default B2", I made my foolish assumption.

Has anyone associated with the Prime95 software mentioned a possible upgrade to ECM based upon Dr. Silverman's research?

Originally Posted by R.D. Silverman

(1) It is P-1 test (singular).

Again, being ignorant both on these methods for finding factors and Andi47's post of

Originally Posted by Andi47

We did in spring 2008 (I did the B1, Alex did the B2): B1 = 103e10, B2 = 1e18

I took that to mean two P-1 tests were performed. With the exception of this current post, I hope to not speak so ignorantly again.

Originally Posted by R.D. Silverman

(2) Your second assertion is grossly false. Especially if you are reaching
your 'conclusion' by comparing the B1,B2 limits between P-1 and ECM.
ECM uses *multiple* curves.

That was a pathetic and embarrassing assertion on my part, and for it I had already offered my mea culpa, but it occurred after your post. 10metreh and fivemack had already explained to me twice by your posting that no comparison can be made between B1 and B2 limits of P-1 and ECM testing. Yes, another statement by me born out of pure ignorance, though done so in the spirit of seeking answers and the hopes of learning.

Originally Posted by R.D. Silverman

(Once more: READ MY PAPER

I shall endeavor to locate and, if necessary, procure a copy of your paper, though, according to Alex,

Originally Posted by akruppa

It won't do him a blind bit of good, not without learning some basics first. The standard recommendation "Crandall & Pomerance, Prime numbers" is the best I can think of to get a first idea of how P-1 and ECM work. They go into rather more detail on elliptic curve arithmetic than one really needs to understand how to use ECM, though.

Therefore, I apparently have much to learn before I can potentially hope to be even remotely capable of comprehending your work.

Originally Posted by akruppa

What's a good text for elementary facts on smoothness probabilities, explaining stuff like Dickman's ρ(α) function, and that for a given p, B/ρ(log(p)/log(B)) has a minimum for some positive B?

Alex

Alex, I offer you my gratitude for your suggestion and another opportunity to learn. Indeed, I thank all who offered guidance and education in my post as well as in those which I had already read.

[bsquared]

Originally Posted by UberNumberGeek

I shall endeavor to locate and, if necessary, procure a copy of your paper, though, according to Alex,

It's available by following the 2nd link after googling the following:

A Practical Analysis of the Elliptic Curve Factoring Algorithm Wagstaff

[UberNumberGeek]

Originally Posted by bsquared

It's available by following the 2nd link after googling the following:

A Practical Analysis of the Elliptic Curve Factoring Algorithm Wagstaff

Thank you, bsquared. I have always greatly enjoyed your avatar and posts.

Even though I have ended up looking quite stupid today and increase that valid belief which each of my posts, at least I now better understand ECM and P-1 testing and what their limits entail, which was my goal. I also now have two solid sources for potentially increasing my understanding and what I know. Though, to paraphrase the Mad Hatter, I can't very well have less knowledge about these subjects, now can I?

[akruppa]

Originally Posted by UberNumberGeek

My apologies for being at least two decades behind. As the Prime95 software utilizes B2 = B1 * 100 for ECM testing, and that is also what is mentioned in the Elliptic curve method Wiki (http://mersennewiki.org/index.php/Elliptic_curve_method ) as the "default B2", I made my foolish assumption.

Has anyone associated with the Prime95 software mentioned a possible upgrade to ECM based upon Dr. Silverman's research?

The fast stage 2 with complexity in O(sqrt(B2)) (give or take a few logs) needs a lot of memory. If you're working with huge numbers as Prime95 is designed to do, it's not very feasible (although memory sizes in computers are becoming large enough that some time it might... you'd want to be able to store several hundred, better a few thousand residues in memory, which for candidate Mersenne primes means several gigabytes, even if you don't store them FFT-ready).
The enhanced standard stage 2 (see Montgomery, "Speeding the Pollard and elliptic curve methods of factorization" for details) uses far less memory and currently is simply the only option for Prime95, at least as far as factoring as support for primality testing is concerned. It has complexity O(B2), though.

Alex

[R.D. Silverman]

Originally Posted by akruppa

It won't do him a blind bit of good, not without learning some basics first. The standard recommendation "Crandall & Pomerance, Prime numbers" is the best I can think of to get a first idea of how P-1 and ECM work. They go into rather more detail on elliptic curve arithmetic than one really needs to understand how to use ECM, though.

What's a good text for elementary facts on smoothness probabilities, explaining stuff like Dickman's ρ(α) function, and that for a given p, B/ρ(log(p)/log(B)) has a minimum for some positive B?

Alex

It depends not upon the reader's level of knowledge, but
rather on the reader's maturity and level of mathematical sophistication.

Knuth, TAOCP Vol 2 has an excellent exposition for Dickman's function,
but requires maturity. It also introduces an analysis of factoring
algorithm run time using smoothness probabilities.

[R.D. Silverman]

Originally Posted by akruppa

The fast stage 2 with complexity in O(sqrt(B2)) (give or take a few logs) needs a lot of memory. If you're working with huge numbers as Prime95 is designed to do, it's not very feasible (although memory sizes in computers are becoming large enough that some time it might... you'd want to be able to store several hundred, better a few thousand residues in memory, which for candidate Mersenne primes means several gigabytes, even if you don't store them FFT-ready).
The enhanced standard stage 2 (see Montgomery, "Speeding the Pollard and elliptic curve methods of factorization" for details) uses far less memory and currently is simply the only option for Prime95, at least as far as factoring as support for primality testing is concerned. It has complexity O(B2), though.

Alex

Sure. But is generally not effective to run ECM on million-plus digit
Mersenne numbers in order to do trial factoring. Simple trial division
or P-1 works quite well. P-1 is particularly effect when looking for a
small, single factor because (as you know) we already know a large
factor of P-1.. Is GIMPS really running ECM on their candidates?
At 10million+ digits, I would not recommend it.

[mdettweiler]

Originally Posted by R.D. Silverman

Sure. But is generally not effective to run ECM on million-plus digit
Mersenne numbers in order to do trial factoring. Simple trial division
or P-1 works quite well. P-1 is particularly effect when looking for a
small, single factor because (as you know) we already know a large
factor of P-1.. Is GIMPS really running ECM on their candidates?
At 10million+ digits, I would not recommend it.

GIMPS's primary use of ECM at this point (at least, that goes for assignments handed out by PrimeNet--users can still enter whatever exponent they want into the client manually) is limited to relatively smaller candidates which have already been fully proven composite, to contribute to finding a full factorization of the numbers.

[akruppa]

Originally Posted by R.D. Silverman

Sure. But is generally not effective to run ECM on million-plus digit
Mersenne numbers in order to do trial factoring. Simple trial division
or P-1 works quite well. P-1 is particularly effect when looking for a
small, single factor because (as you know) we already know a large
factor of P-1.. Is GIMPS really running ECM on their candidates?
At 10million+ digits, I would not recommend it.

GIMPS routinely uses P-1 before an LL test, but not ECM. I was thinking of a fast stage 2 for P-1 in my posting. The polynomial multi-point evaluation stage 2 for ECM can't use the trick of evaluating along a geometric progression, so you need a general product/remainder tree which uses far more memory. ECM (with fast stage 2 or not) is right out for eliminating candidate Mersenne primes.

Alex

[Mr. P-1]

Originally Posted by R.D. Silverman

It depends not upon the reader's level of knowledge, but
rather on the reader's maturity and level of mathematical sophistication.

I would expect it to depend upon both. In any case, the two are likely to be correlated.

For myself, I "understand" the P-1 algorithm in the sense that I could give an elementary proof that it finds the factors it purports to, starting from Fermat's little theorem and using only high-school algebra. Fermat I can prove from group theory, and so on back to first principles.

Yet explanations by specialists such as yourself are often incomprehensible to me.