Odd Perfect numbers - a factoring challenge
 

For those of you interested in factoring by ECM/P-1, I saw the following today on the nmbrthry listserve:
[url]http://listserv.nodak.edu/scripts/wa.exe?A2=ind0409&L=nmbrthry&F=&S=&P=1064[/url]
Basically, the author says that he has proven that any odd perfect number must have at least 47 prime factors (including repetitions), and that improving this result depends upon finding factors of the three numbers listed in the posting. Gmp-ecm would probably be the preferred tool here.

I was about to post this, too. I've emailed Kevin G. Hare, asking for info on previous factoring effort so that we can choose bounds accordingly, but haven't received a reply yet.

I've done P-1 on the c301 with B1=100M, and on the c789 and c927 with B1=10M.

I'm attaching files with the numbers to factor. Unfortunately I don't have a lot of cpu time available at present, but I'll start off with 100 curves at B1=1M on the c301.

If you can run gmp-ecm, please help factor these numbers!

Alex

I'm running gmp-ecm on the C301 at the 30-digit level. I have about 15 (slowish) CPUs on it at moment and it will be done soon. If nothing is found I'll bump it up to the 35-digit level and then 40 digits.

If anyone else is doing ECM work on the C301, let me know so we don't duplicate too much work at the same level.

-Don Leclair

OK then, I'm doing 500@25e4 on the C789, this will take a few hours.

Dave

[QUOTE=dleclair]I'm running gmp-ecm on the C301 at the 30-digit level. I have about 15 (slowish) CPUs on it at moment and it will be done soon. If nothing is found I'll bump it up to the 35-digit level and then 40 digits.

If anyone else is doing ECM work on the C301, let me know so we don't duplicate too much work at the same level.

-Don Leclair[/QUOTE]
I loaded the 2 smaller numbers into my home ECMNET soon after the NMBRTHRY moderator let loose the posting. Not having any information about the work done so far I assumed that no work had been done.

Pari-gp is amazingly slow at calculating the largest number. I gave up after about 2 hours cpu and loaded only the 2 smaller ones. Kevin Hare has since mailed me the decimal representation of the largest.

Since then a few hundred curves at B1=50K have completed, as have around 50 at B1=250K. Needless to say, no factors have yet been found.

Paul

[QUOTE=dleclair]
If anyone else is doing ECM work on the C301, let me know so we don't duplicate too much work at the same level.[/QUOTE]

I recently ran Dario Alpern's applet to 350, which gets 25 curves at the 35 digit level but jumps there straight from the 25 digit level. I'm not running any more at the present.

These roadblocks suggest he may have found some other factors that are not in Richard Brent's data base. I wonder if he has found factors of

sigma(127[sup]108[/sup])
sigma(16[sup]192[/sup])
sigma(2801[sup]78[/sup])

or if his approach doesn't need these.

I did a quick check to ensure there are no algebraic factors (of polynomials in 11, 547, 3221 respectively). Indeed there aren't. Should this be obvious to me?

Dave

I've done 100@1M for the c301. I'm doing 100@1M on the c927 now.

Note that sigma(11^18), sigma(547^18) and sigma(3221^12) are prime. sigma(p^n) is simply p^0+p^1+...+p^n, i.e. if n+1 is prime, the (n+1)st cyclotomic polynomial evaluated at p, which also explanins the absence of algebraic factors.

Alex

I'm talking about (for instance) the poly in 11 being irreducible, not the poly in sigma(11^18).

For example, take sigma(sigma(2^4)^2). Here sigma(2^4) = 31 is prime, also 2+1 is prime and sigma(p^2) = p^2 + p + 1 which is irreducible in Z[p].

So in this case the composition of two irreducible cyclotomic polynomials has an algebraic factor:

(x^2 - x + 1)(x^6 + 3x^5 + 5x^4 + 6x^3 + 7x^2 + 6x + 3)

This is really what I meant. Am I making sense?

Dave

Yes, perfect sense! Good point.

According to Pari, both phi_17(phi_19(x)) and phi_23(phi_13(x)) are irreducible.

Alex

For the C301, I've finished 1100 curves at B1=1M with gmp-ecm 5.0.3 so it is unlikely that there are any 35-digit or smaller factors.

A few minutes ago my machines started 2900 curves at 3M (the 40-digit level). That should be done late tomorrow.

If no factors are found I plan to stop when the 40-digit level is complete.

-Don Leclair

On the C789, I fInished 500 curves at b1=25e4; I'm now trying some at b1=1e6.

Dave

I didn't actually need any of these factorizations. Given that I wanted to show there were more than 47 prime factors, I would never need any factors of sigma(p^m) where m> 47. (Actually, there are a lot of other restrictions which made it even easier).

I just put up a list of factorizations that I did need at:
[url]http://www.math.uwaterloo.ca/~kghare/ODDPERFECT/Odd.html[/url]

This list is somewhat incomplete, as the way I did my data entry in my code was sort of annoying, but it is a start. It should be complete by sometime next week.


[QUOTE=wblipp]I recently ran Dario Alpern's applet to 350, which gets 25 curves at the 35 digit level but jumps there straight from the 25 digit level. I'm not running any more at the present.

These roadblocks suggest he may have found some other factors that are not in Richard Brent's data base. I wonder if he has found factors of

sigma(127[sup]108[/sup])
sigma(16[sup]192[/sup])
sigma(2801[sup]78[/sup])

or if his approach doesn't need these.[/QUOTE]

[QUOTE=dleclair]I'm running gmp-ecm on the C301 at the 30-digit level. I have about 15 (slowish) CPUs on it at moment and it will be done soon. If nothing is found I'll bump it up to the 35-digit level and then 40 digits.

If anyone else is doing ECM work on the C301, let me know so we don't duplicate too much work at the same level.

-Don Leclair[/QUOTE]

Thanks for the help. There are a number of people working on this problem that don't regularly read this forum. (Mostly from the Number Theory mailling list). I am attempting to write down all of the work that has been going on so far.
This can be viewed at
[url]http://www.math.uwaterloo.ca/~kghare/ODDPERFECT/MissingValues.html[/url]

I will be monitoring both this forum and the mailling list, and writing down any information.
If there is anything in particular you want me to include, just let me know.
(kghare@math.uwaterloo.ca)


Kevin

I've done 100@1M on the c927.

Re. Dave's question: is there an easy way of telling if the composition of two cyclotomic polynomicls is irreducible, or if not, what its factors are?

Alex

For the C301 I've completed 2900 curves at B1=3M, finishing the sweep for 40-digit factors.

I'm going to stop at this point. Happy hunting to the rest of you!

-Don Leclair

I've found a P34 factor of the C789 :banana:

1520135498523547561326750429418247

For those who are interested:

sigma = 807838452,
group order 2^4 3 13 19 29 3251 29989 354181 997153 128404457

Since Kevin doesn't want a complete factorization, I won't be doing any more work on the remaining composite. I'm now starting some curves at 25e4 on the C927, assuming Paul hasn't done more than 500 yet.

Dave

[QUOTE=dave_dm]I'm now starting some curves at 25e4 on the C927, assuming Paul hasn't done more than 500 yet.

Dave[/QUOTE]

Actually 25e4 seems to be pretty much done. I meant 1e6.

Dave

I've found a P35 factor of the C927:

46973400441039677515399714233826061

sigma = 2520761059
group order 2^7 3^2 5 47 229 281 3137 18793 34499 94399 14044469 (particularly smooth for a P35).

As before, I'm stopping work on the remaining composite unless Kevin needs any more factors.

Dave

Wow, lucky streak, eh? Try a Fermat number while it lasts! :grin:

Alex

Outstanding work, Dave! Also thanks to Paul Zimmermann who turned up the P34 as well. Could Kevin clarify for us, is the 301 digit composite the remaining bottleneck to extending his results? In other words, did he need to find at least one factor of each of these three composites? So is it ok to quit on the two larger numbers now and just concentrate on the C301? If so, it really puts a premium on finding a factor of this number. It looks like the ECM effort on it should be going at the 45-digit level now.

Heh thanks, but remember there's no skill involved in this kind of work!

That said, I'm sure I'll have F12 factored by breakfast :)

Dave

[QUOTE=philmoore]Outstanding work, Dave! Also thanks to Paul Zimmermann who turned up the P34 as well. Could Kevin clarify for us, is the 301 digit composite the remaining bottleneck to extending his results? In other words, did he need to find at least one factor of each of these three composites? So is it ok to quit on the two larger numbers now and just concentrate on the C301? If so, it really puts a premium on finding a factor of this number. It looks like the ECM effort on it should be going at the 45-digit level now.[/QUOTE]


Yes, thats correct. I only needed to find a factor of each number, and then (hopefully) I will be able to continue with the calculation. (You never know what future problems might come up, but I doubt I will hit any for a while, if I find a factor for c301). So the only bottleneck remaining is c301.

Kevin

1000 curves done on the C301 at b1=11e6.

Dave

Dear Kevin,

btw, do you need [I]any[/I] prime factor of each number, or does it have to be the smallest factor?

Alex

[QUOTE=akruppa]Dear Kevin,

btw, do you need [I]any[/I] prime factor of each number, or does it have to be the smallest factor?

Alex[/QUOTE]

Any factor is fine. It does not need to be the smallest.

I attached a message that I had sent to the Number Theory mailing list, as I thought it might
be relevant.

Thanks again to everybody who has helped to work on this.

Kevin

-----------------------------------------------------------------------
Recap:

A Perfect number N is a number such that sigma(N) = 2 N.
where sigma is the standard sum of divisors function.

If we define Omega(N) as the total number of prime factors
of a number, I recently proved that Omega(N) >= 47 for Odd Perfect
Numbers.

The reason the bound was no higher, is I could not find factors for
c301 = sigma(sigma(11^18)^16), a 301 digit number.
c789 = sigma(sigma(547^18)^16), a 789 digit number
and
c927 = sigma(sigma(3221^12)^22), a 927 digit number.

New Stuff:

I would like to thank a huge number of people
who helped to find factors for both c789 and c927.
(I have included the factors at the end of the message.)

So c789 and c927 are done (YEAH!!!!)

The algorithm I use for the bound on Omega(N) requires at least a
partial factorization of numbers. In practice, I have observed
that a complete factorization is rarely needed. Hence the fact
that a factor was found for c789 and c927 will be incrediably useful.

If I can find a factor for the last number (c301), then
I can continue the calculations. Unfortunately there is no guarentee that
I will not run into an equally hard problem somewhere later in thecalculation. But again, based on experience, I doubt that I will happen
right away.

--------------------------------------------------------------
c789 = sigma(sigma(547^18)^16)

Factor is:

p34 = 1520135498523547561326750429418247

--------------------------------------------------------------
c927 = sigma(sigma(3221^12)^22)

Factor is:

p35 = 46973400441039677515399714233826061

--------------------------------------------------------------
c301 = sigma((sigma(11^18))^16) (C301)

= 383156579951943630348774235030845479471667515789409858435212125226351\
00246118059073205923746544331860205171086654671434719340358393954962433\
53321245760019611207664487665420776742726779780862993590544596916020496\
51098074006790199515463957685212019806746807835724736664782855114139073\
9467161074462608561

I throw in another 22 curves on C301 at B1=11M - not much, but I think every bit counts.

Work done so far (according to [url]http://www.math.uwaterloo.ca/~kghare/ODDPERFECT/MissingValues.html[/url]):
2174 curves at 11M (Chirstophe Clavier)
1000 curves done on the at b1=11e6. (Dave)

That adds up to almost 3,300 curves with B1=11M - 60% done. :banana:

Forgot one: 23 curves in total...

I've done another 1500 curves on the c301 at B1=11e6. I guess this means the 45-digit level is pretty much done.

Dave

I've done another ~160 at 11M.

Alex

Just completed 1 curve at B1=43e6.
Unfortunately, it takes > 400 MB for stage 2, so I can't ecm efficiently - disk swapping is too serious even with 512 MB RAM. :cry:

Try doing more blocks in stage 2 with the -k parameter. The default is 5. Doing more blocks makes stage 2 use less memory, but also take more time.

Alex

I tried one curve to see if my box could handle it:
[code]GMP-ECM 5.0.3 [powered by GMP 4.1.4] [ECM]
Input number is 3831565799519436303487742350308454794716675157894098584352121252263510024611805907320592374654433186020517108665467143471934035839395496243353321245760019611207664487665420776742726779780862993590544596916020496510980740067901995154639576852120198067468078357247366647828551141390739467161074462608561 (301 digits)
Using B1=44000000, B2=184367799127, polynomial Dickson(30), sigma=1301954676
Step 1 took 2382728ms
Step 2 took 1204672ms

real 63m25.494s
user 59m47.401s
sys 0m0.535s[/code]Is this time reasonable for one curve? It took 261MB for the second step... Should I continue to use the same input parameters?

PS - Thanks to akruppa for walking me through the install step by step!

[QUOTE=Xyzzy]I tried one curve to see if my box could handle it:
[code]Step 1 took 2382728ms
Step 2 took 1204672ms
[/code]Is this time reasonable for one curve?[/QUOTE]

This is almost exactly the time I see on an Athlon XP 3000+ (2154 MHz). Which cpu/clock speed are you using?

[QUOTE=Xyzzy]It took 261MB for the second step... Should I continue to use the same input parameters?[/QUOTE]

Yes, please. B1=11M is done, B1=44M is a good parameter choice now.

[QUOTE=Xyzzy]PS - Thanks to akruppa for walking me through the install step by step![/QUOTE]
You're welcome!

Alex

[QUOTE=akruppa]This is almost exactly the time I see on an Athlon XP 3000+ (2154 MHz). Which cpu/clock speed are you using?[/quote]My 3200+ A64... I guess there are no 64-bit or large L2 enhancements...

[quote]Yes, please. B1=11M is done, B1=44M is a good parameter choice now.[/quote]
I'll set it to run a total of 100 curves to start... That should take 4 days... I let it run last night so I have 12 curves done so far...

Questions:

If I run 10 curves, then after that is done, I run another 10, is that less efficient than if I run 20 all at once?

I get output to the console, but I don't see a log file being generated... Do I need to somehow redirect the output to a log file manually? I'd like to see the output on the console and have it logged too... (I know how to send the output to a log file directly, and then I suppose I could just "tail -f" that file...)

Should I be running this with the -save option or is the data from step 1 not worth keeping?

If for some reason I have to stop the program while it is in the middle of a run, can I stop it without losing work?

Thanks!

[QUOTE=Xyzzy]My 3200+ A64... I guess there are no 64-bit or large L2 enhancements...[/QUOTE]

Large L2 benefits gmp-ecm very little. Apparantly GMP 5.0 will have AMD64 asm support, but it isn't due until "end of 2005" :sad: The GMP site does not tell if there will be any improvements for AMD64 in GMP 4.2 which is due this november.

[QUOTE=Xyzzy]Questions:

If I run 10 curves, then after that is done, I run another 10, is that less efficient than if I run 20 all at once?[/QUOTE]

No difference.

[QUOTE=Xyzzy]I get output to the console, but I don't see a log file being generated... Do I need to somehow redirect the output to a log file manually? I'd like to see the output on the console and have it logged too... (I know how to send the output to a log file directly, and then I suppose I could just "tail -f" that file...)[/QUOTE]

That's one way. I usually prefix the ecm command with "nohup", which intercepts the SIGHUP signal in case I want to log off, and redirects any output to the file nohup.out. To watch progress, I usually use "less nohup.out" and give the "F" command (does basically the same thing as "tail -f").

[QUOTE=Xyzzy]Should I be running this with the -save option or is the data from step 1 not worth keeping?[/QUOTE]

Not worth keeping. If we later advance to a higher B1 value, we'll do all fresh curves.

[QUOTE=Xyzzy]If for some reason I have to stop the program while it is in the middle of a run, can I stop it without losing work?

Thanks![/QUOTE]

Unfortunately not. The curves that have been completed so far are ok and should be counted towards the total for that B1 level, but the curve that has been interrupted is lost. In gmp-ecm 5.0, there's so interrupt-and-resume mechanism as in Prime95.

Alex

[QUOTE=akruppa]Yes, please. B1=11M is done, B1=44M is a good parameter choice now.[/QUOTE]

Rather irrelecant question, but isn't 43M the "next" step (meaning: how it is done 'according to the manual' - which ensures that curves from several people have the same bounds)?

[quote]The GMP site does not tell if there will be any improvements for AMD64 in GMP 4.2 which is due this november.[/quote]

Are the any big performance improvements for gmp-ecm in conjunction with other CPUs?

The expected-time-over-B1 curve is really flat near the optimal B1 for a given factor size, being off by 2.3% has no discernible effect on efficiency. For all practical purposes, 43M and 44M are equally "right".

I only know what the GMP page says about 4.2: "...and some speed improvements." I don't really know which parts are being improved, or by how much. Paul Zimmermann mentioned that he worked on GMP's Schönhage-Strassen multiplication some more, so that may be faster. It will only ever be used for really large input numbers, though.

Alex

I've finished 28 curves at 44e6... Do I need to post the sigma values?

I am probably going to stop here for a few days while I explore GMP-ECM a bit more... I never could get it to work before so now that it is working I want to play with it!

I'm curious about the Debian package specifically... Does it connect to a server automatically to get work or do you have to feed it work manually?

[url]http://packages.debian.org/testing/math/gmp-ecm[/url]

Finally, if anyone knows of a resource that explains all of this, as if explaining it to a small child, please link me... I've read most of the stuff linked from the various math pages and all I get is a headache...

Ideally, I'd like to understand what ECM is doing and how to choose interesting work...

Up until recently I have just run all this math stuff without understanding it even the littlest bit, but now that I have some free time I'd like to learn something...

Unfortunately, I've only taken math up to Trig... Well, I took Calc 1, but I got a D... And I took (and enjoyed!) Finite Mathematics, but that wasn't even like math to me... Hopefully my previous pitiful math performance is not a predictor of my future success...

gmp-ecm alone can't connect to servers.
What you need in addition is the ECMNET client. If you have problems compiling the source, look here: [url]http://www.ecompute.org/factors/unix.html[/url]

[QUOTE=Xyzzy]I've finished 28 curves at 44e6... Do I need to post the sigma values?[/QUOTE]
No. It is extremely unlikely that anyone will pick the same sigma values again. They are chosen pseudorandomly and any one sigma is as good as any other.

[QUOTE=Xyzzy]Finally, if anyone knows of a resource that explains all of this, as if explaining it to a small child, please link me... I've read most of the stuff linked from the various math pages and all I get is a headache...

Ideally, I'd like to understand what ECM is doing and how to choose interesting work...

Up until recently I have just run all this math stuff without understanding it even the littlest bit, but now that I have some free time I'd like to learn something...

Unfortunately, I've only taken math up to Trig... Well, I took Calc 1, but I got a D... And I took (and enjoyed!) Finite Mathematics, but that wasn't even like math to me... Hopefully my previous pitiful math performance is not a predictor of my future success...[/QUOTE]Hmm. Might be difficult.

Here's one approach to understanding what is happening which is correct though wildly unconventional and doesn't describe any of the beautiful mathematics of elliptic curves. In fact, I'll explain several factoring algorithms simultaneously.

I hope you are comfortable with the concepts "greatest common divisor", aka GCD, and "composite number". If not, then I'd have to go back a long long way. If you are, I'll define a "highly composite number" to be one which has a large number of prime factors. Factorials, 2*3*4*5*6*..., are highly composite numbers for instance.

Right, what is going on in ECM (and a number of other algorithms including P-1, P+1 and Pollard rho) is that successive iterations of a fairly simple function are generating numbers which are more and more highly composite. Every so often --- it could be every iteration, though in practice that turns out to be needlessly inefficient --- the GCD is taken of this quantity and the number N to be factored. If the GCD is neither 1 nor N we've found a proper factor of N. The more prime factors in the highly composite number, the more likely it is to share one with N. (Aside: if we knew how to calculate factorials mod N efficiently we would have an efficient factoring algorithm. Unfortunately we don't, so we have to make do with other kinds of highly composite numbers.)

The difference between P-1, rho, ECM with different sigma and so forth is bound up in the function that is iterated. For instance, P-1 picks a value "x_0", often taken to be 3 though it doesn't much matter, and repeatedly evaluates x_{i+1} = (x_i)^p_i where p_i is the i'th prime. Then every so often we calculate GCD(N, x_i - 1). In the case of Pollard rho, the function iterated is usually x_{i+1} = (x_i)^2 + 1 and we calculate GCD(N, x_i - x_j) for carefully chosen values of i and j.

In the case of ECM, the sigma value is used to specify an equation of the form y^2 = x^3 +ax +b. This is called an elliptic curve. An initial point on the curve, (x_0, y_0) is also found, by which I mean that x_0 and y_0 are both rational numbers (the ratio of integers) and that when plugged in, they satisfy the equation. The values of a and b are also rational numbers; they may be integers but need not be. Different values of sigma produce different values of a and b.

The next bit glosses over a large amount of mathematics. The function that is iterated is called "elliptic curve addition". It can be shown that if you perform a well-defined sequence of manipulations (additions, multiplication and, crucially, division) on the x and y coordinates of a point which lies on a curve the result is the coordinates of another point which lies on the curve. So given an initial point it is possible to generate a sequence of other points. All the arithmetic has to be carried out modulo N, the number to be factored.

The manipulation involved in elliptic curve addition generates a new point (x_{i+1} , y_{i+1}) from an existing point (x_i,y_i). This new point has the general form polynomial_1(x_i,y_i) / polynomial_2(x_i,y_i). The two polynomials depend on a and b and hence on sigma. Note the division. Some more math which I sweep under the carpet tells us that in order to perform division modulo N, we have to evaluate a GCD with N. Voila!

At base then, and more from a computational point of view than a mathematical one, ECM produces a series of highly composite integers, the polynomial_2(x_i,y_i) in the denominator above, and takes the GCD of those with the number to be factored.

I stress that the above is [b]not[/b] the conventional description of ECM. It is correct (unless I've made a typo) but it hides completely the reason [b]why[/b] the sequence of denominators may be expected to have a factor in common with N. You also have to take it on trust that different values of sigma generate different sequences of highly composite integers, though this may be rather easier to see. If one sequence fails to factor N, choose another one and hope for better luck next time.

I'm not sure I can give the conventional description of ECM in a forum like this and assuming no more than high school math. If I come across a good description I'll post it.

Hope it helps.


Note for purists: I am well aware that I did not specify what function is iterated in P+1 and have omitted everything to do with the second stages of P-1, P+1 and ECM. The description is complicated enough for present purposes without adding further complexity which doesn't add much more understanding, though the second stages are important for computational efficiency.

Paul

Something very strange happened... I installed a new OS today and went with a 64-bit distro... Instead of compiling ECM myself, I installed GMP-ECM from a preconfigured package, which happens to use an older version of GMP... Anyways:

32-bit distro, self-compiled GMP & ECM:
[code]GMP-ECM 5.0.3 [powered by GMP 4.1.4] [ECM]
Input number is 3831565799519436303487742350308454794716675157894098584352121252263510024611805907320592374654433186020517108665467143471934035839395496243353321245760019611207664487665420776742726779780862993590544596916020496510980740067901995154639576852120198067468078357247366647828551141390739467161074462608561 (301 digits)
Using B1=44000000, B2=184367799127, polynomial Dickson(30), sigma=1301954676
Step 1 took 2382728ms
Step 2 took 1204672ms[/code]
64-bit distro, pre-packaged GMP & ECM:
[code]GMP-ECM 5.0.3 [powered by GMP 4.1.3] [ECM]
Input number is 3831565799519436303487742350308454794716675157894098584352121252263510024611805907320592374654433186020517108665467143471934035839395496243353321245760019611207664487665420776742726779780862993590544596916020496510980740067901995154639576852120198067468078357247366647828551141390739467161074462608561 (301 digits)
Using B1=44000000, B2=184367799127, polynomial Dickson(30), sigma=2277007193
Step 1 took 1382108ms
Step 2 took 1055166ms[/code]Look how much faster it is! I doubt a 64-bit kernel can affect the program, but the numbers are lower, so maybe that is the case?

I'll run it overnight just to make sure... There sure is a big difference between 59m47s and 40m37s!

xilman:

Thanks for trying to explain it to me... I won't lie and say I understand it, but I will do some reading on my own and refer back to your post as I learn more...

Thanks!

[QUOTE=Xyzzy]xilman:

Thanks for trying to explain it to me... I won't lie and say I understand it, but I will do some reading on my own and refer back to your post as I learn more...

Thanks![/QUOTE]
Re-reading it afer several hours made it clear that there is a small but very important error in my explanation. Actually, there's at least one but I've only spotted on so far. Where I say
[QUOTE=xilman]The manipulation involved in elliptic curve addition generates a new point (x_{i+1} , y_{i+1}) from an existing point (x_i,y_i). This new point has the general form polynomial_1(x_i,y_i) / polynomial_2(x_i,y_i). The two polynomials depend on a and b and hence on sigma. Note the division. Some more math which I sweep under the carpet tells us that in order to perform division modulo N, we have to evaluate a GCD with N. Voila!

At base then, and more from a computational point of view than a mathematical one, ECM produces a series of highly composite integers, the polynomial_2(x_i,y_i) in the denominator above, and takes the GCD of those with the number to be factored.
[/QUOTE] I should have said:[INDENT]The manipulation involved in elliptic curve addition generates a new point (x_{i+j} , y_{i+j}) from two existing points (x_i,y_i) and (x_j,y_j). The two points could be different or could be the same point, in which case the point is elliptic-added to itself and so the operation is usually called elliptic curve doubling by analogy to what happens when we add a regular number to itself. This new point has the general form polynomial_1(x_i,y_i,x_j,y_j) / polynomial_2(x_i,y_i,x_j,y_j). The two polynomials depend on a and b and hence on sigma. Note the division. Some more math which I sweep under the carpet tells us that in order to perform division modulo N, we have to evaluate a GCD with N. Voila!

At base then, and more from a computational point of view than a mathematical one, ECM produces a series of highly composite integers, the polynomial_2(x_i,y_i,x_j,y_j) in the denominator above, and takes the GCD of those with the number to be factored.
[/INDENT]Sorry about that. I got too carried away with description of Pollard rho and P-1 ...

Paul

[QUOTE=Xyzzy]Something very strange happened... I installed a new OS today and went with a 64-bit distro... Instead of compiling ECM myself, I installed GMP-ECM from a preconfigured package, which happens to use an older version of GMP...[/QUOTE]

Hmm... maybe compiling GMP under a 64 bit OS on AMD64 makes GMP use generic C code with 64 bit types instead of the K7 asm code for 32 bits, which may very well be faster.

Perhaps try a fresh compile of GMP 4.1.4 under the 64 OS? After the configure step, you can check where the links in mpn/ point, that should clear up whether the generic C code is used. And a few bugs were fixed since 4.1.2, so compiling and installing 4.1.4 is probably a good idea.

Alex

I almost hate to say this, because everybody seems to be having so much fun hunting for factors, but I don't actually need them anymore. Due to a beautiful argument of Carl Pomerance, I now have a way to get around not knowing the factors. The basic idea is this:

If I know 3 primes to have gotten to the point where I am stuck, say q1, q2, q3
And if I know that I have 5 unknown primes left to conside the case, say p1, p2, p3, p4, p5
Then, if it is an odd perfect number I have

sigma(q1^a1 .. q3^a3 p1^b1 .. p5^b5) / q1^a1 .. q3^a3 p1^b1 .. p5^b5 = 2.

As sigma is multiplicative, I can find a bound for

sigma(p1^b1 .. p5^b5) / p1^b1 .. p5^b5 = X.

By taking a fifth root, I know that I have atleast one prime with

sigma(p1^b1)/p1^b1 > X^(1/5);

By noticing that

p1/(p1-1) > sigma(p1^b1)/p1^b1 > (p1+1)/p1,

we can solve for p1 in the equation above, and have that there must be a prime p1 less than some given value, if we were to get an odd perfect number. Of course, 3 and 5 above can be replaced with any numbers.

I started running this over the weekend, and anytime I was in one of these situations, I found that
I had to have a prime p < 30 or 40 to continue. As a result, it is fairly straight forward to simply check each of these cases in turn, and eventually come up with a contradiction.

(I have increased the existing bounds, but my computer is still running, so I don't know what the
new lower bounds for the total number of prime factors of an odd perfect number are going to stabalize to).

Kevin

Hmm... Since we don't need to work on that anymore, can someone link me to something *interesting* to work on with ECM?

(Maybe we need a perpetual factoring challenge thread!)

[QUOTE=Xyzzy]Hmm... Since we don't need to work on that anymore, can someone link me to something *interesting* to work on with ECM?

(Maybe we need a perpetual factoring challenge thread!)[/QUOTE]

What is "Interesting" is in the mind of the beholder.

I have suggested that we find all factors up to 50 digits of 2^n+1 and
2^n-1 for n < 1200. There is a long historical tradition, dating back
to Fermat and Mersenne, of this project.

If this is "too large", what about an effort just to find a factor of M1061
or perhaps P1123? Or an effort to find a 60 digit factor of something.
Perhaps we might offer some prize money for the first person to find a
60-digit factor of 2^n+1 or 2^n-1....

Note that we do NOT need an on-line effort. I can prepare a file
or files containing the numbers and people can run the ECMNET code
*off-line*. They can report their efforts and or successes by email. :banana:

The problem with this is that people can cheat; report that they ran curves
when they did not.

[QUOTE=Bob Silverman]
The problem with this is that people can cheat; report that they ran curves
when they did not.[/QUOTE]

M1061 was my choice...

What if the client prints out a sort of univocal "digital signature" (maybe involving his sigma, the numbr of curves run and some tricks to avoid decyphering)?

Luigi

Since all ecm implementations I know of are open-source, I don't think encrypting anything is going to help.

I can think of a couple of ideas that could stop cheating (I'll state them wrt stage 1 of ecm for simplicity).

1) Log the residue at regular intervals during stage 1. Then the server can choose a random interval and verify the calculation was correct.

2) Let the server choose the sigma values instead of the client and give each sigma to two different people. Verify that the end residues match.

However I don't really think cheating is much of a problem. If someone says "Hi, yesterday I ran 1000 curves on F18", they're pretty much guaranteed to be lying. On the other side of the coin, people who know the ecm algorithm like the back of their hand probably have little motivation to cheat (or am I really naive?). Has anyone ever been aware of ecm cheating going on?

I think a much more important problem is the case of someone who does lots of ecm work in good faith but has a miscompiled gmp or dodgy hardware that invalidates the calculations. Idea 2) would guard against this but I don't think the problem justifies doing every curve twice.

Dave

In the new ECMNet Client/Server (which I am still testing), cheating is still possible, but a little more difficult. It is not possible to submit an invalid factor (for numbers that are decimal expanded). It is possible to say that you did more curves or curves at a larger B1, but the new client will tell the server of the curves it has done when it is shut down not when it starts up. It is possible to bypass that by modifying code and doing other things, but as long as ECMNet doesn't collect stats, I would not expect too many people to be interested in wreaking havoc. IMHO, one of the main problems with stats is that someone always wants to rig the system to put themselves at the top.

Very cool, Pomerance's suggestion. Isn't it true, however, that knowing a factor of the C301 might help you push this method a little farther? Unfortunately, searching for factors much beyond 50 digits seems an extraordinary effort.

Mike (xyzzy), I did find some nice presentations of ECM theory by just putting "Elliptic Curve Method factoring" into Google. I wrote an account a couple years ago in this thread:
[url]http://www.mersenneforum.org/showthread.php?t=194[/url]
but I think some graphics would have helped clarify the explanation of the elliptic curve "multiplication" law. (I called it an "addition" law in my explanation, but the term "multilication" seems more standard.) If you have any questions, I would be glad to try to answer them.

I think cheating is no problem in that project. There is no hall of fame table where the contributors with the most curves are listed.
Submitting the the completed effort is just to inform the other how much effort is spent on which candidate.

Which form of 'cheating' is worse?

a. reporting work, you have not done.

b. not reporting effort, you have done.

If both are balanced, we have no problem.

If there are some security issues regarding proving the own effort, I guess that it would be too complicated for some people with other versions or own compilation of factoring tools to report, that they will just do that if they find a factor.

For example, I noticed, that there are more 40+ digit factors of numbers of the form 2^n+1 around, than the ecmp table would suggest. Of course, that could be a statistical coincidence, but I doubt that due to being too unlikely.

Nevertheless, there should be no problem, if the information on the factoring effort table is not so precise. The only thing what can happen is, that people switch to higher bounds too early. That does not reduce the chance of finding a factor much. Besides that, we switch normally a bit later to NFS than the mathematical optimum anyway (reducing the risk of missing a small factor).

The best thing is, that it is very easy to verify new factors, so that it is impossible to forge factors.

Reto

now working on:
[3M] P1119, P1128, 2^607-3

[QUOTE=philmoore]
Mike (xyzzy), I did find some nice presentations of ECM theory by just putting "Elliptic Curve Method factoring" into Google. I wrote an account a couple years ago in this thread:
[url]http://www.mersenneforum.org/showthread.php?t=194[/url]
but I think some graphics would have helped clarify the explanation of the elliptic curve "multiplication" law. (I called it an "addition" law in my explanation, but the term "multilication" seems more standard.) If you have any questions, I would be glad to try to answer them.[/QUOTE]

I think this site may be of some help to the beginners. :cool:
At least it was helpful to me :smile:

[URL=http://www.certicom.com/index.php?action=ecc_tutorial,home]Certicom Tutorial Pages[/URL]

Luigi

[QUOTE=rogue]In the new ECMNet Client/Server (which I am still testing), cheating is still possible, but a little more difficult. It is not possible to submit an invalid factor (for numbers that are decimal expanded). It is possible to say that you did more curves or curves at a larger B1, but the new client will tell the server of the curves it has done when it is shut down not when it starts up. It is possible to bypass that by modifying code and doing other things, but as long as ECMNet doesn't collect stats, I would not expect too many people to be interested in wreaking havoc. IMHO, one of the main problems with stats is that someone always wants to rig the system to put themselves at the top.[/QUOTE]

I am curious about the new combination of client and server. Does it still use the previous protocol? If that is the case you could just start a telnet session and follow the protocol to cheat heavily. Altho not intressting if no stats are maintained but still very nasty when some ranges are reported to be thoroughly checked while no work was done at all.

[QUOTE=dave_dm]I think a much more important problem is the case of someone who does lots of ecm work in good faith but has a miscompiled gmp or dodgy hardware that invalidates the calculations. Idea 2) would guard against this but I don't think the problem justifies doing every curve twice.
[/QUOTE]

I have the experience with one ecm client that there was a miscompile of ecm or ecmnet. Not sure which one since i never got in contact with the owner of the client. The sigma's reported were all the same for all factors found. The factors were indeed correct factors but not reproducable with ecm since the sigma value was incorrect.

[QUOTE=BotXXX]I am curious about the new combination of client and server. Does it still use the previous protocol? If that is the case you could just start a telnet session and follow the protocol to cheat heavily. Altho not intressting if no stats are maintained but still very nasty when some ranges are reported to be thoroughly checked while no work was done at all.[/QUOTE]

It does support the old protocol because the new client needs to be compatible with the old server and the old client needs to be compatible with the new server.

I agree that cheating can still happen, but it can't be done through telnet. You have to have a socket connection, which means that you either write a program to 'simulate' a client or you modify the current client to send back bogus info. The main thing is that the new server will validate factors, which is what the server administrator wants.

One has to think of the reasons why someone would do it and either eliminate those reasons or add security to make it harder to do. I can think of a few.

pumping up stats - There are none in ECMNet, although someone running a server can collect stats using the ECMNet logs.
the challenge of breaking security - ECMNet is too easy to hack compared to GIMPS or dnet.
being malicious - It can happen, but I don't know of any cases of it happening with ECMNet.

I'm certain that there are others, but I don't see ECMNet being a desirable targets for hackers.

I do agree that it is not possible for the server to know that the client has validly compiled GMP and GMP-ECM, but I could add code to the server that would send a number with a known factorization to each client to verify that that client returns the correct factors. If it does not, I would not accept any work done from the client. That is definitely a consideration for a future release.

[QUOTE=philmoore]Very cool, Pomerance's suggestion. Isn't it true, however, that knowing a factor of the C301 might help you push this method a little farther? Unfortunately, searching for factors much beyond 50 digits seems an extraordinary effort.[/QUOTE]

It is possible that if I know a factor to C301, I could push the method a little farther. But I still haven't reached the limit with Pomerance's method. I suspect (although I won't know for sure for a couple of weeks) that it won't actually be the lack of factors that will stop the program, but the sheer amount of time to do everything else that the algorithm requires.

[QUOTE=kghare]I suspect (although I won't know for sure for a couple of weeks) that it won't actually be the lack of factors that will stop the program, but the sheer amount of time to do everything else that the algorithm requires.[/QUOTE]

I would have guessed that knowing factors would also alleviate this problem because the search tree would be less bushy. With no factors of C301, you have to eliminate all cases of

(11[sup]18[/sup], s[sup]16[/sup], p[sup]n[/sup], ...)

Where s = sigma(11[sup]18[/sup]) and p ranges over all the possible values from the Pomerance argument.

With a factor "f" of the C301, these many branches of the search space for many values of p are replaced with a single branch

(11[sup]18[/sup], s[sup]16[/sup], f[sup]n[/sup], ...)

But perhaps I don't understand the algorithmic implications.

William

[QUOTE=wblipp]I would have guessed that knowing factors would also alleviate this problem because the search tree would be less bushy. With no factors of C301, you have to eliminate all cases of

(11[sup]18[/sup], s[sup]16[/sup], p[sup]n[/sup], ...)

Where s = sigma(11[sup]18[/sup]) and p ranges over all the possible values from the Pomerance argument.

With a factor "f" of the C301, these many branches of the search space for many values of p are replaced with a single branch

(11[sup]18[/sup], s[sup]16[/sup], f[sup]n[/sup], ...)

But perhaps I don't understand the algorithmic implications.

William[/QUOTE]

That is exactly right. The search tree would be less bushy, and the problem would be solvable faster. That being said, it doesn't take that long to use Pomerance's method, so this isn't an issue I am worrying about at the moment.

kghare,

Hi. I've also worked on odd perfect numbers a little, including publishing a paper at INTEGERS, found at: [url]http://www.integers-ejcnt.org/vol3.html[/url]

If you have a rough draft/preprint of your result, or a description of the algorithm you are using, I'd love to take a look.

Best,
Pace Nielsen

[QUOTE=Zeta-Flux]If you have a rough draft/preprint of your result, or a description of the algorithm you are using, I'd love to take a look.[/QUOTE]

Have you seen this?
[url]http://www.math.uwaterloo.ca/~kghare/Preprints/PDF/P15_Odd.pdf[/url]

Thanks for the link.

Just to let people know, there is a preprint at the preprint archive.