mersenneforum.org Factoring Smaller Numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2004-10-08, 21:43 #1 marc     Jun 2004 UK 139 Posts Factoring Smaller Numbers 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.
2004-10-08, 21:55   #2
smh

"Sander"
Oct 2002
52.345322,5.52471

22458 Posts

Quote:
 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.

 2004-10-08, 22:10 #3 marc     Jun 2004 UK 139 Posts 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.
2004-10-09, 09:27   #4
geoff

Mar 2003
New Zealand

13·89 Posts

Quote:
 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.

2004-10-09, 09:36   #5
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

2·32·17·37 Posts

Quote:
 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

2004-10-09, 11:57   #6
rogue

"Mark"
Apr 2003
Between here and the

147138 Posts

Quote:
 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.

2004-10-09, 14:17   #7
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

2·32·17·37 Posts

Quote:
 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

 Similar Threads Thread Thread Starter Forum Replies Last Post fivemack Factoring 3 2017-09-19 08:52 paulunderwood Miscellaneous Math 18 2017-08-27 14:56 skan YAFU 6 2013-02-26 13:57 siegert81 Factoring 12 2011-02-03 13:55 ShridharRasal Factoring 10 2008-03-20 17:17

All times are UTC. The time now is 16:38.

Sat May 28 16:38:27 UTC 2022 up 44 days, 14:39, 0 users, load averages: 1.06, 1.21, 1.29

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

โ  ยฑ โ รท ร ยท โ โ โฐ โ โ โ โ โ โค โฅ โฆ โง โจ โฉ โบ โป โผ โฝ โ โ โ โ ยฒ ยณ ยฐ
โ  โ ยฐ โ ~ โ โ โซ
โก โ โ โ โ โช โซ โโ โโ โ โ โ โ โง โจ โฉ โช โจ โ โ ๐ ๐ ๐ โฒ โณ
โ โ โ โฆ โฃ โฉ โช โ โ โ โ โ โ โ โ โ โ โ โ โ โ โค โ โ โ โต โถ โท โธ ๐
ยฌ โจ โง โ โ โ โ โ โ โ โ โ โด โต โค โฅ โข โจ โซค โฃ โฆ โฏ โฎ โฐ โฑ
โซ โฌ โญ โฎ โฏ โฐ โ โ ฮด โ โฑ โ โ
๐ข๐ผ ๐ฃ๐ฝ ๐ค๐พ ๐ฅ๐ฟ ๐ฆ๐๐ ๐ง๐ ๐จ๐ ๐ฉ๐๐ ๐ช๐ ๐ซ๐ ๐ฌ๐ ๐ญ๐ ๐ฎ๐ ๐ฏ๐ ๐ฐ๐ ๐ฑ๐ ๐ฒ๐ ๐ด๐๐ ๐ต๐ ๐ถ๐ ๐ท๐๐ ๐ธ๐ ๐น๐ ๐บ๐