Factoring Smaller Numbers

[marc]

After downloading nofactor.cmp and messing with DECOMP to get it to compile I noticed that there are some "small" exponents which have no factors. The smallest is 1061 and has only been factored up to 2^58.

Does anyone mind if I try factoring these a bit? If there isn't a problem I'll continue, if there is just tell me and I'll stop.

[smh]

Originally Posted by marc

After downloading nofactor.cmp and messing with DECOMP to get it to compile I noticed that there are some "small" exponents which have no factors. The smallest is 1061 and has only been factored up to 2^58.

Does anyone mind if I try factoring these a bit? If there isn't a problem I'll continue, if there is just tell me and I'll stop.

Not that i mind, but it would be worthless to fator these small numbers using trail factoring.

First, it would take a long time to take the factor level up one or two bits

Second, the chance of succes is almost 0. There are other methods which are much more effective in factoring small numbers.

As can be seen on this page, enough ECM curves have ben run to find almost all <45 digit factors (if they would exist).

With factoring, you're limmited to something like 19 digits or so.

[marc]

Bah, oh well. I have an urge to factor something and it just seemed interesting that these "small" numbers had no factors. Thanks for the warning.

[geoff]

Originally Posted by marc

I have an urge to factor something and it just seemed interesting that these "small" numbers had no factors.

Try finding a factor for M1061 with Prime95 ECM! It is much more interesting than trial factoring. There is always some possibility of finding a record sized factor.

Otherwise a good place to find some quick factors from the exponents in nofactor.cmp with ECM might be in the 90000-100000 range, there should still be plenty of 20-25 digit factors still to be found and the curves don't take too long, about 140 seconds each on a P4 2.66.

[xilman]

Originally Posted by marc

Bah, oh well. I have an urge to factor something and it just seemed interesting that these "small" numbers had no factors. Thanks for the warning.

There are many numbers which you can try to factor and have a reasonable expectation of making very visible progress.

As already pointed out, running Prime95's ECM factoring gives you a good chance of finding eally quite large factors --- in the 40 through 55 digits range --- and possibly factors of record breaking size. This program is very efficient but very limited in that it works only for numbers of the form 2^n+1 and 2^n-1.

If you would like to factor integers of other forms, there are a number of projects running. You could join NFSNET (http://www.nfsnet.org) or you could check out ECMNET (http://www.loria.fr/~zimmerma/records/ecmnet.html) for instance. Other projects you can find easily enough by the normal mechanisms, including search engines.


Paul

[rogue]

Originally Posted by xilman

If you would like to factor integers of other forms, there are a number of projects running. You could join NFSNET (http://www.nfsnet.org) or you could check out ECMNET (http://www.loria.fr/~zimmerma/records/ecmnet.html) for instance. Other projects you can find easily enough by the normal mechanisms, including search engines.
Paul

Paul, the ECMNET site still points to your old website a Microsoft Research.

[xilman]

Originally Posted by rogue

Paul, the ECMNET site still points to your old website a Microsoft Research.

Thanks, I hadn't noticed that myself. I should tell Paul (the other one).

Paul