ECM question
 

I found a TF factor that P-1 would never find (~2.6 million GHzD) and I was wondering approx how long it should take for ECM to find it. The P-1 parameters would be B1=3 and B2=~1.42e+13.

I know the 'normal' B1/B2 for a ~25 digit number is 50,000/5,000,000. Would this indicate this factor could not be found by ECM?

[QUOTE=bcp19;338759]I found a TF factor that P-1 would never find (~2.6 million GHzD) and I was wondering approx how long it should take for ECM to find it. The P-1 parameters would be B1=3 and B2=~1.42e+13.

I know the 'normal' B1/B2 for a ~25 digit number is 50,000/5,000,000. Would this indicate this factor could not be found by ECM?[/QUOTE]

ECM doesn't care about the factorization of P-1, only about the size of the factor. If the factor is ~25 digits, then with B1=50k there is about a 37% chance (1 / exp(1)) of missing the factor after running a couple hundred curves (GMP-ECM reports 221, but that's with a much large B2). Run twice as many curves and the chance of missing it goes to about 14% (1 / exp(2)), and so on.

[QUOTE=bsquared;338763]ECM doesn't care about the factorization of P-1, only about the size of the factor. If the factor is ~25 digits, then with B1=50k there is about a 37% chance (1 / exp(1)) of missing the factor after running a couple hundred curves (GMP-ECM reports 221, but that's with a much large B2). Run twice as many curves and the chance of missing it goes to about 14% (1 / exp(2)), and so on.[/QUOTE]

If people (who profess an interest in this subject) would ever actually
READ what has been written, they wouldn't have to ask such questions.

My joint paper with Sam Wagstaff Jr. should be REQUIRED READING
for anyone who wants to discuss ECM.

I ask: why wouldn't anyone interested in this subject want to read it?
Is the answer: laziness? Or is it that the claim of interest is a shallow one?

[QUOTE=R.D. Silverman;338765]If people (who profess an interest in this subject) would ever actually
READ what has been written, they wouldn't have to ask such questions.

My joint paper with Sam Wagstaff Jr. should be REQUIRED READING
for anyone who wants to discuss ECM.

I ask: why wouldn't anyone interested in this subject want to read it?
Is the answer: laziness? Or is it that the claim of interest is a shallow one?[/QUOTE]

[IMO] Why should anyone have to learn how to design/fabricate the modulation circuitry surrounding an IR light emitting diode just to turn on their TV? They just want to know what buttons to press (note to BCP - this may not pertain to you... it is a general answer).

Now pretend that the instruction manual to their remote control exists only in scavenger hunt form, where they follow one clue to another clue to another clue, etc., until they can learn how to turn on their TV. That is close to how it is with advanced number theory software - tools that are fun to use but that have widely-dispersed, partially-hidden, and variable-content instruction manuals. This forum provides a short-cut through much of that.

If someone following the short cut discovers something shiny along the way, and goes off and learns some number theory as a result, then that's a bonus, but not necessarily the primary purpose of this forum. As such your link to your paper is great, but your comments not so much. [/IMO]

[QUOTE=bsquared;338767][IMO] Why should anyone have to learn how to design/fabricate the modulation circuitry surrounding an IR light emitting diode just to turn on their TV? They just want to know what buttons to press (note to BCP - this may not pertain to you... it is a general answer).
[/QUOTE]

But the OP was not doing that! He wasn't asking what buttons to push to
run the software.

He was asking about the capabilities of the algorithm!!!!

[QUOTE=R.D. Silverman;338768]But the OP was not doing that! He wasn't asking what buttons to push to
run the software.

He was asking about the capabilities of the algorithm!!!![/QUOTE]

A request for functional specifications of an algorithm does not equal a request for in-depth knowledge of the innards of it, so I think there is still a distinction.

But like I said, I'm not taking exception with you trying to get people to learn about the algorithm, I'm taking exception with your methods.

[QUOTE=R.D. Silverman;338765]If people (who profess an interest in this subject) would ever actually
READ what has been written, they wouldn't have to ask such questions.

My joint paper with Sam Wagstaff Jr. should be REQUIRED READING
for anyone who wants to discuss ECM.

I ask: why wouldn't anyone interested in this subject want to read it?
Is the answer: laziness? Or is it that the claim of interest is a shallow one?[/QUOTE]
<sigh> I agree with bsquared here, why do I have to reinvent the wheel in order to drive a car? Millions of engineers have already put billions of hours of research into building cars, yet I should drop everything and start at square one so as to not be lazy and answer my own questions. :rolleyes:

So, to put it simply yet verbosely, while trial factoring 63186931 I found a 72.184 bit factor of length 22 digits. In the expression 2kp-1, k = 3 × 14154475893511. From scratch this TF would take a little over 30 GHzD to be found. As I stated P-1 would take over 2.6 million GHzD. While I understand ECM is largely dependant on luck time-wise when it comes to finding a factor since it could be found on Curve 1 or Curve 1001, I was curious if this factor [I][U]could even be found[/U][/I] under normal 25 digit length B1/B2 parameters. When I plugged this exponent into P95 with a B1 of 50,000 and 300 curves (which seems to be the recommended amount) it said the run would last 63 days on my laptop. I didn't feel like waiting that long (or wasting those resources) to see if it would find it, so I felt it was time to ask the experts.

You may also note I did not ask this question in the MATH section, where I was sure I'd get a lecture. But, hey, lectures seem to find me.

[QUOTE=bcp19;338773]...of length 22 digits. ... I was curious if this factor [I][U]could even be found[/U][/I] under normal 25 digit length B1/B2 parameters[/QUOTE]
With almost no exception, the answer to the question "could ECM possibly find this factor?" is "yes". The answer to the question "could ECM possibly fail to find this factor?" is also, with almost no exception, "yes". The only issue is how long you should expect it to take; or to put it another way, how lucky you have to be to find it in a reasonable amount of time.
The answer to "is ECM at digit level x the best general-purpose way a good way to find this factor of size y?" is yes if x is close to y (no more than 3** apart).
[QUOTE=bcp19;338773]When I plugged this exponent into P95 with a B1 of 50,000 and 300 curves (which seems to be the recommended amount) it said the run would last 63 days on my laptop.[/QUOTE]
Since 22 is smaller than 25, the actual amount of curves expected* is lower than 300; let's say 100**. [URL="http://www.mersenne.ca/credit.php?worktype=ECM&exponent=63186931&f_exponent=&b1=50000&b2=5000000&numcurves=100&factor=&frombits=&tobits=&submitbutton=Calculate"]100 curves is 357 GHz-days[/URL]. However, let's assume this was ECMd like ECM is usually run, going up subsequent digit levels for an efficient search. The 20-digit level ([URL="http://www.mersennewiki.org/index.php/ECM"]B1=11000, 90 curves[/URL], [URL="http://www.mersenne.ca/credit.php?worktype=ECM&exponent=63186931&f_exponent=&b1=11000&b2=1100000&numcurves=90&factor=&frombits=&tobits=&submitbutton=Calculate"]70 GHz-days[/URL]) had a decent chance of finding it. Thus you could expect to spend about 200** GHz-days. If you were to put, say, 95% confidence lower and upper bounds on how many GHz-days it should take to find, it'd be a VERY wide range**. Still, it's easy to see that it's somewhere between P-1 (~4 GHz-days) and TF (~2.6 million GHz-days), much closer to P-1, but still impractical.

If you knew in advance that the factor was 22 digits, you could choose a B1 that optimized that digit level, and maybe find it in about expected 150** GHz-days.

* "expected" being the same as what bsquared defined earlier: there is about a 37% chance (1 / exp(1)) of missing the factor after running enough curves to expect to find the factor.
** Numbers marked with this have been made up on the spot, and may be wildly inaccurate, but can help give you an idea of what you're dealing with.

Now that you know the factor, you use the Magma Calculator to check which B1/B2 would be required for random sigma values:

[url]http://magma.maths.usyd.edu.au/calc/[/url]

Just paste this code in and change the sigma value s at the bottom to a random (32 bit I think) number.

[CODE]
FindGroupOrder2 := function (p, s)
K := GF(p);
v := K ! (4*s);
u := K ! (s^2-5);
x := u^3;
b := 4*x*v;
a := (v-u)^3*(3*u+v);
A := a/b-2;
x := x/v^3;
b := x^3 + A*x^2 + x;
E := EllipticCurve([0,b*A,0,b^2,0]);
return FactoredOrder(E);
end function;

p := 5366267349746657428447;
s := 10000;
FindGroupOrder2(p, s);
[/CODE]

For s:=10000 the group order is:
[ <2, 4>, <3, 1>, <5, 1>, <57223, 1>, <16530659, 1>, <23637431, 1> ]

The last 2 digits is the B1 and B2 value required to find the factor with sigma = 10000, so B1 = 17e6 and B2=24e6.

So you can just try random sigma values to see how low you can find B1/B2.

You can also download the Magma Calculator but I haven't tried that.

[QUOTE=Mini-Geek;338776]Still, it's easy to see that it's somewhere between P-1 (~4 GHz-days) and TF (~2.6 million GHz-days), much closer to P-1, but still impractical.[/QUOTE]

Correction: TF (8.6) and P-1 (2.6 million), with ECM's range being closer to TF.

I had momentarily confused your case for the more commonly-noted case of a large P-1 factor, where P-1 is the quick way and TF is the slow way. E.g. [URL="http://www.mersenne.ca/exponent/60052913"]this factor[/URL] I found that, at 41 digits, would take 1.24 GHz-days of P-1 or 18 quintillion (1.8*10^19) GHz-days of TF.

[QUOTE=Mini-Geek;338776]

<snip>

If you knew in advance that the factor was 22 digits, you could choose a B1 that optimized that digit level, and maybe find it in about expected 150** GHz-days.

[/QUOTE]

Once again, if people BOTHERED TO READ MY PAPER, they would find that it
discusses HOW to select parameters when the size of the factor is unknown.

After running some trials one uses information from the ECM FAILURE,
and the theoretical distribution of factor sizes along with BAYES THEOREM
to reselect parameters in an optimal way.

Instead of banning Bob next time, the gerbils should just replace all of his posts with "I deem you an idiot. Go read my paper." Almost no content will be lost.

[QUOTE=VBCurtis;338814]Instead of banning Bob next time, the gerbils should just replace all of his posts with "I deem you an idiot. Go read my paper." Almost no content will be lost.[/QUOTE]

There is a big difference between being an idiot (i.e. [i]incapable[/i] of learning
and thinking) and being [b]WILLFULLY IGNORANT[/b].

The former can't be helped. The latter is a bad [b]CHARACTER FLAW[/b]
and is all too prevalent within this forum. It is contemptible.

Maybe when you grow up and obtain a little intellectual discipline (the lot of)
you will understand this.

[QUOTE=R.D. Silverman;338832]There is a big difference between being an idiot (i.e. [i]incapable[/i] of learning
and thinking) and being [b]WILLFULLY IGNORANT[/b].

The former can't be helped. The latter is a bad [b]CHARACTER FLAW[/b]
and is all too prevalent within this forum. It is contemptible.

Maybe when you grow up and obtain a little intellectual discipline (the lot of)
you will understand this.[/QUOTE]

Also, being an idiot is a relative thing. Everyone is an idiot on some scale. But is giving up always the same as being ignorant? Different people set up different goals of understanding.

Someone is not satisfied before he can run a program and understand when it can be used.
Someone is not satisfied if he cannot understand the mathematics behind the program.
Someone is not satisfied if he cannot write the program himself.
Someone is not satisfied if he cannot improve parts of the algorithms by himself.
Someone is not satisfied if he cannot improve the (global) knowledge in the mathematics behind.

You set up a different level for the willful ignorance than others. I admire that, but sometimes one has to face the reality: not everyone of us has the potential to understand (relatively) simple mathematics and less potential to solve difficult mathematical problems.

I, for example, am quite confident that I could quite easily understand most of the mathematics behind, but choose not to devote my time to that. I tackle with (harder) problems on other fields of mathematics. I may run programs without fully understanding everything, but I would not sill call the related ignorance a serious character flaw.

[QUOTE=rajula;338838]Also, being an idiot is a relative thing. Everyone is an idiot on some scale. But is giving up always the same as being ignorant? Different people set up different goals of understanding.

Someone is not satisfied before he can run a program and understand when it can be used.
Someone is not satisfied if he cannot understand the mathematics behind the program.
Someone is not satisfied if he cannot write the program himself.
Someone is not satisfied if he cannot improve parts of the algorithms by himself.
Someone is not satisfied if he cannot improve the (global) knowledge in the mathematics behind.

You set up a different level for the willful ignorance than others. I admire that, but sometimes one has to face the reality: not everyone of us has the potential to understand (relatively) simple mathematics and less potential to solve difficult mathematical problems.

I, for example, am quite confident that I could quite easily understand most of the mathematics behind, but choose not to devote my time to that. I tackle with (harder) problems on other fields of mathematics. I may run programs without fully understanding everything, but I would not sill call the related ignorance a serious character flaw.[/QUOTE]


One can't get a little bit pregnant. If people are unwilling to learn the
theory behind this subject, then STOP ASKING QUESTIONS ABOUT THE
(capabilities of) ALGORITHMS. (which is what kicked off this thread)

You can ask questions about how to run the software. You can run code
without full understanding. But when one starts asking about the capabilities
of algorithms and how to select parameters, you have crossed the line
of merely running code.

[QUOTE=R.D. Silverman;338843]One can't get a little bit pregnant. If people are unwilling to learn the
theory behind this subject, then STOP ASKING QUESTIONS ABOUT THE
(capabilities of) ALGORITHMS. (which is what kicked off this thread)

You can ask questions about how to run the software. You can run code
without full understanding. But when one starts asking about the capabilities
of algorithms and how to select parameters, you have crossed the line
of merely running code.[/QUOTE]
Congrats Bob, between you and David I have decided to stop all GIMPS processing. After all, what is the point of running a program that I don't understand and am unable to create myself? You and David now share the dubious honor of causing the biggest decline in GIMPS processing in recent history (heck, probably the biggest since the project started). 400,000+GHzD per year gone. Between his childishness and your pendantic nature creating mountains out of molehills, I have had enough.

[QUOTE=R.D. Silverman;338843]One can't get a little bit pregnant. If people are unwilling to learn the
theory behind this subject, then STOP ASKING QUESTIONS ABOUT THE
(capabilities of) ALGORITHMS. (which is what kicked off this thread)

You can ask questions about how to run the software. You can run code
without full understanding. But when one starts asking about the capabilities
of algorithms and how to select parameters, you have crossed the line
of merely running code.[/QUOTE]:rant::blahblah::showoff::tantrum::deadhorse::weirdo::bob::ban::ban::ban::explode::bs meter:

This is pure BS, Bob. Such things are discussed all the time. That is what a forum is for. If you don't like the question, maybe you could just have a tall, refreshing glass of STFU. Telling people that they should read your paper is beyond pedantic. It is pure, pompous puffery. Your exceptional mathematical accomplishments are just that: exceptional. To insist that others duplicate your course of study is also beyond arrogance. While you obviously get a lot of pleasure out of putting down those who fall short of your exalted state, you could, perhaps forgo a bit of that wanking in the interests of the project. Since you don't, you mainly prove that your entire goal is stupid a$$holiness. This is not a professional journal, nor is it your private playground to be the bully of.

Hey, look at the bright side: At least Bob's pompous puffery comes without Youtube link-spam accompaniment.

Bob, if you find yourself using ALL-CAPS and [b]LOUD BOLDFACE[/b] as frequently as above, may I suggest it's time to (once again) take a deep breath, and remind yourself that most of our participants - including George and me, among others - are amateurs with respect to the field of number theory?

And yes, that includes no small number of willful ignoramuses, but methinks you often apply that label to anyone not willing to drop everything else right this instant and spend a year-long sabbatical studying your collected papers.

If you don't like it, no one is forcing you to be here.

[QUOTE=bcp19;338866]You and David now share the dubious honor of causing the biggest decline in GIMPS processing in recent history (heck, probably the biggest since the project started). 400,000+GHzD per year gone. Between his childishness and your pendantic nature creating mountains out of molehills, I have had enough.[/QUOTE]

We will definitely miss your input. Thank you for all the cycles, money and time you contributed.

[QUOTE=ewmayer;338886]Hey, look at the bright side: At least Bob's pompous puffery comes without Youtube link-spam accompaniment.[/QUOTE]:-)

[quote]If you don't like it, no one is forcing you to be here.[/quote]Theory:

Mr. Silverman seems to have an addiction to posting here in the manner he does. It's that addiction that forces him to post as he does. Therefore, methods of persuasion that won't work on addiction probably won't work with Mr. Silverman, either. Cold-turkey banning seems to have had some effect for short periods after he's been reinstated.

(accidental duplicate post deleted)

[QUOTE=ewmayer;338886]And yes, that includes no small number of willful ignoramuses, but methinks you often apply that label to anyone not willing to drop everything else right this instant and spend a year-long sabbatical studying your collected papers.[/QUOTE]

I am a willful ignoramus. :smile:

I think Bob behaves like a jerk.

[QUOTE=ewmayer;338886]<snip>[/QUOTE]
:goodposting:+1 from me.

[QUOTE=ewmayer;338886]Hey, look at the bright side: At least Bob's pompous puffery comes without Youtube link-spam accompaniment.

Bob, if you find yourself using ALL-CAPS and [B]LOUD BOLDFACE[/B] as frequently as above, may I suggest it's time to (once again) take a deep breath, and remind yourself that most of our participants - including George and me, among others - are amateurs with respect to the field of number theory?

And yes, that includes no small number of willful ignoramuses, but methinks you often apply that label to anyone not willing to drop everything else right this instant and spend a year-long sabbatical studying your collected papers.

If you don't like it, no one is forcing you to be here.[/QUOTE]
<applause> +1
I agree with klander, RD *is* exceptional in his field, but some of us excel in other things. I spent 20 years in the Navy working on Aviation Electronics, I intimately know the workings of radars, inertial nav units, short, medium and long range communication as well as a host of things I cannot talk about. I am far from ignorant, but I am uneducated in certain areas. [I][U]We all are[/U][/I]. At the same time, none of us can turn back the time dial 40 years and choose a different education path.

I'd hate to be his doctor and accidentally ask a math question of him.......

This thread has run its course, and is locked.