mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2006-03-27, 18:58   #23
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

2×3,853 Posts
Default

Quote:
Originally Posted by ewmayer
Sadly, the old aphorism "'tis better to have tried and failed..." has apparently fallen into widespread disuse in much of the modern world.
Another favorite quote of mine:

"Far better it is to dare mighty things, to win glorious triumphs even though checkered by failure, than to rank with those poor spirits who neither enjoy nor suffer much because they live in the gray twilight that knows neither victory nor defeat." -- Theodore Roosevelt
Xyzzy is offline   Reply With Quote
Old 2006-03-30, 21:40   #24
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2·59·83 Posts
Default

Getting back to the original post: whether a given factorization is impressive or not is a function of "factor difficulty." For sieve-based factoring of Mersenne (and similar special-factor-form) numbers, factor difficulty is proportional to the product of the factor index k (which measures how many factor candidates q needed to to be tried) times the work in testing each candidate q. For q's needing N machine words to store, the latter is O(N^3) for small N (O(N) bits in the factor times O(N^2) for each corresponding mod-q multiply), transitioning to O(N^2*log N) for q's large enough to allow fast-transform-based arithmetic to be used. Thus, while k = 20 possessed by the factor in the original post might be impressive if the q in question has several millions of digits, it's quite trivial for q's of only a few machine words. No disrespect intended, merely a statement of fact. Now, for q's of this size range if someone were to find a factor some Mersenne number having a nontrivially small k, say the smallest factor of the following (using for exponents some 70-digit primes which occur in the first few thousand decimal digits of Pi):

M7195429162991930645537799140373404328752628889639958794757291746426357

(not trivial but still fairly easy), or of

M3852254995466672782398645659611635488623057745649803559363456817432411

(a little harder), well, then I'd be at least moderately impressed. ;)
ewmayer is online now   Reply With Quote
Old 2006-03-31, 03:04   #25
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

874110 Posts
Default

Quote:
Originally Posted by ewmayer
M7195429162991930645537799140373404328752628889639958794757291746426357
Luigi's Factor4 knocked out a factor in the ~240 bit range for this in less than 20 minutes, however for some reason it didn't post it to the results.txt

Quote:
Originally Posted by ewmayer
M3852254995466672782398645659611635488623057745649803559363456817432411
Starting a run now.....
Uncwilly is online now   Reply With Quote
Old 2006-03-31, 03:23   #26
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

8,741 Posts
Default

Just missed the edit deadline. Factor4 worked fine, notepad didn't read the result.txt file correctly.

M7195429162991930645537799140373404328752628889639958794757291746426357 has a factor: 957164768977838582192020192849031737427989705415465878713793977276619713569

M3852254995466672782398645659611635488623057745649803559363456817432411 has a factor: 22788707831582286845380020155651359827337650244785629920055214225748565104481

This is just me running Luigi's program. It took less than 1/2 total for both of these. (While surfing the net, downloading, etc.)
Uncwilly is online now   Reply With Quote
Old 2006-04-05, 17:44   #27
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2·59·83 Posts
Default

OK, now that we're all limbered up, let's try a couple slightly tougher ones:

M570658748822569815793678976697422057505968344086973502014102067

M6402474964732639141992726042699227967823547816360093417216412199
ewmayer is online now   Reply With Quote
Old 2006-05-01, 15:35   #28
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

25·149 Posts
Default

Quote:
Originally Posted by ewmayer
OK, now that we're all limbered up, let's try a couple slightly tougher ones:

M570658748822569815793678976697422057505968344086973502014102067

M6402474964732639141992726042699227967823547816360093417216412199

First of all, thanks to Uncwilly that sponsored my little factoring applet

Second, I have often publicly admitted that Ernst's Mfactor runs far faster than my poor Factor4. I don't want to invoke a flame war about this subject: my first posting wanted to express my joy in developing a factoring applet from scratch, while learning the basis of Mersenne numbers factoring.

I'm well aware that the result is not to be taken as an absolute record, because the "k" was pretty small; it was, however, the factor of the biggest Mersenne number checked out (at that time), as Will Edgington pointed out, that made me smile (you can check it on his Mersenne pages).

Ernst taught me a lot about this subject, and I thank him as well.

It's not a matter of "size", it's a matter of new ideas for a search, a matter of sharing ideas and machine idle cycles.

BTW, I started to work on the new numbers to see how my applet works.

Ernst still remembers what happened with M41234123412341 that I proposed on Mersenneforum: he indeed found a huge factor (more than 80 bits, IIRC) that now is part of Will Edgington database thanks to his Mfactor.
That one was BIG!

I'll let you know how Factor4 behaves with those Mersennes you proposed.

Luigi
ET_ is offline   Reply With Quote
Old 2006-05-01, 16:34   #29
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

12A016 Posts
Default

Quote:
Originally Posted by ewmayer
OK, now that we're all limbered up, let's try a couple slightly tougher ones:

M570658748822569815793678976697422057505968344086973502014102067

M6402474964732639141992726042699227967823547816360093417216412199

Here is the first one:

M570658748822569815793678976697422057505968344086973502014102067 has a factor: 322107495328491256282531776450837995333351643082236449882652963072723913

237.54 bit depth

Now go for the second...

Luigi
ET_ is offline   Reply With Quote
Old 2006-05-02, 17:54   #30
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

25·149 Posts
Default

...and here is the other.

M6402474964732639141992726042699227967823547816360093417216412199 has a factor: 59547637466852043611708058111909725657028150812842162510646420336832110759


Luigi
ET_ is offline   Reply With Quote
Old 2006-05-02, 18:09   #31
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2×59×83 Posts
Default

OK, let's move on to Master's level:

M12160287649628674460477464915995054973742562690104903778198683593

M24247014121478057345510500801908699603302763478708108175450119307
ewmayer is online now   Reply With Quote
Old 2006-05-02, 22:44   #32
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

25×149 Posts
Default

Quote:
Originally Posted by ewmayer
OK, let's move on to Master's level:

M12160287649628674460477464915995054973742562690104903778198683593

M24247014121478057345510500801908699603302763478708108175450119307
It seems that you took away my "62-digits record"

Anyway, it's been a matter of days (I guess you're testing Mfactor 2.99) as Will has not updated his April 9th database yet...

Congratulations for you and your software
I'm cheching your two new monsters while downloading GMP 4.2

You gave me fuel for improvements...

Luigi
ET_ is offline   Reply With Quote
Old 2006-05-06, 13:16   #33
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

25×149 Posts
Default

OK, let's move on to master's level...

M12160287649628674460477464915995054973742562690104903778198683593 has a factor: 543592246870442485937175551111623340804481341938942752102988291735322287319

Done up to 250 bits.

Luigi

Last fiddled with by ET_ on 2006-05-06 at 13:16
ET_ is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factor a 108-digit number sweety439 Factoring 9 2016-12-21 21:22
mersenne prime as a factor of another number kurtulmehtap Math 21 2010-11-08 18:21
Time needed to factor a 150 digit number ladderbook Factoring 14 2008-11-27 13:02
How do I prove a 4000 digit number is prime?? VJS Lounge 4 2005-05-09 20:56
The first (non-merseinne) 10 million-digit prime number!!! ron29730 Miscellaneous Math 17 2004-05-15 20:23

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

Tue Oct 27 23:16:37 UTC 2020 up 47 days, 20:27, 2 users, load averages: 1.87, 1.81, 1.79

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

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.