ECM for exponents above 20,000,000

[schickel]

Originally Posted by c10ck3r

Linky linky?

Online free at ams.org.

[c10ck3r]

Originally Posted by schickel

Online free at ams.org.

To rip off a comedian I was watching the other day.

The bank called the other day and said I had an outstanding account. I was pleased- I hadn't kept that large of a balance, and for them to take time out of their day to tell me it was outstanding was a real ego-boost. The gal went on, sadly, to tell me that it meant I had a negative balance. I started to freak out. Now I'm REALLY broke. Like, I'm so broke, when people offer free mix tapes on the streets, I have to turn them down. They say its $0.00, but I'm so broke I can't afford that much!

[TObject]

Originally Posted by R.D. Silverman

My suggestion: Do not bother listening to axn. He does not know what he
is talking about. ECM bounds are related to P-1 bounds.

Read:

Robert Silverman & Samuel Wagstaff Jr.
A Practical Analysis of ECM.
Mathematics of Computation

This paper describes the relationship between P-1 and ECM.

To axn: do us all a favor: Study this subject before making further
erroneous pronouncements.

I appreciate the information. Thank you very much for the article.

Please do not smack axn, though; I certainly hope we can correct and supplement each other with more respect than a pack of raging baboons.

Thanks again for the paper.

[axn]

Originally Posted by R.D. Silverman

Robert Silverman & Samuel Wagstaff Jr.
A Practical Analysis of ECM.
Mathematics of Computation

Has anyone gone thru this paper?

Originally Posted by R.D. Silverman

This paper describes the relationship between P-1 and ECM.

Can you point me to the part where the paper discusses the above?

[R.D. Silverman]

Originally Posted by axn

Has anyone gone thru this paper?

Clearly, the referrees did before the paper was published. Several other
computational number theorists have sent comments to me.....

Can you point me to the part where the paper discusses the above?

It discusses using ECM with just one curve, and points out that
the optimal B1/B2 params for just one curve apply to P-1. Indeed, if
running just one curve P-1 is faster.......

[axn]

Originally Posted by R.D. Silverman

Clearly, the referrees did before the paper was published. Several other
computational number theorists have sent comments to me.....

Apologies. I didn't mean to imply that your paper is somehow bad (if that is what you understood). I went thru the paper and didn't see the type of discussion I was expecting. Thought that maybe someone else had better luck.

Originally Posted by R.D. Silverman

Indeed, if
running just one curve P-1 is faster.......

I saw a statement to this effect. However, given the context of this thread, I was expecting something more.

[R.D. Silverman]

Originally Posted by axn

Apologies. I didn't mean to imply that your paper is somehow bad (if that is what you understood). I went thru the paper and didn't see the type of discussion I was expecting. Thought that maybe someone else had better luck.



I saw a statement to this effect. However, given the context of this thread, I was expecting something more.

What else is needed? If you want further explanation, please ask.
Running P-1 is the same as running ECM with just one curve. (only faster!)

Indeed. P-1 has a benefit over ECM when running only one curve for certain
sets of numbers: those known to have P-1 lie in a certain congruence class.
[such as Cunninghams (and extensions), Fibonacci/Lucas, etc]

[jasonp]

The 10x rule of thumb for P-1 stage 1 is used only because P-1 stage 1 is computationally faster than ECM stage 1, and if you are willing to commit to performing ECM for that long then you may as well let P-1 run for that long as well.

It has nothing to do with the relative probability of P-1 finding a factor, compared to ECM.

For stage 2, you can use a method whose runtime is linear in the stage 2 bound (this is the 'classical' stage 2 that Bob's paper analyzes) or if you have a ton of memory then you can use fast algorithms that allow B2 to be ~B1^2 instead of a fixed multiple of B1, and still take the same time. The second choice is not suitable for large Mersenne numbers, as it would require huge batches of them.

[akruppa]

Originally Posted by jasonp

The second choice is not suitable for large Mersenne numbers, as it would require huge batches of them.

I've been wondering about that... current Mp candidates have residues of about 4-8MB each, so on a contemporary system, you could fit on the order of 2^10 residues. That would be enough to make a multipoint evaluation stage 2 worthwhile. We'd need a fast convolution product, however... knowing that 2 is a p-th principal root of unity is intriguing, if only p were not prime! A prime length FFT is considerably less intriguing, and generic convolution algorithms would blow up memory use by a factor of several, probably making the polynomial stage 2 uncompetitive. Maybe an external FFT would do the trick.

[PageFault]

Can anyone recommend an ECM test for me? I like running bizarre work, the kind others won't touch. I am intrigued by ECM on low Mersenne numbers, such that I have a chance (albeit small) of finding a monster factor. Current box is a cheap work HP and sometime soon I will build a much nicer personal box dedicated for ECM.

I wish I had time to read the linked material, alas I am Dirctor of Operations for a new and rapidly growing mining company and am currently developing two small mines simultaneously (lack of sleep is an issue).

I can allocate 1350 MB of ram and don't care if the test takes months. I want to find a monster. I used to like P-1, but the gpu crowd effectively ruined that and TF as well.

[kracker]

GPU's have ""ruined"" TF but not P-1. Not many people use GPU's to P-1 at the moment.