mersenneforum.org 62-digit prime factor of a Mersenne number
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2006-03-27, 18:58   #23
Xyzzy

"Mike"
Aug 2002

2×3,853 Posts

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

 2006-03-30, 21:40 #24 ewmayer ∂2ω=0     Sep 2002 República de California 2·59·83 Posts 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. ;)
2006-03-31, 03:04   #25
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

874110 Posts

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

 2006-03-31, 03:23 #26 Uncwilly 6809 > 6502     """"""""""""""""""" Aug 2003 101×103 Posts 8,741 Posts 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.)
 2006-04-05, 17:44 #27 ewmayer ∂2ω=0     Sep 2002 República de California 2·59·83 Posts OK, now that we're all limbered up, let's try a couple slightly tougher ones: M570658748822569815793678976697422057505968344086973502014102067 M6402474964732639141992726042699227967823547816360093417216412199
2006-05-01, 15:35   #28
ET_
Banned

"Luigi"
Aug 2002
Team Italia

25·149 Posts

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

2006-05-01, 16:34   #29
ET_
Banned

"Luigi"
Aug 2002
Team Italia

12A016 Posts

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

 2006-05-02, 17:54 #30 ET_ Banned     "Luigi" Aug 2002 Team Italia 25·149 Posts ...and here is the other. M6402474964732639141992726042699227967823547816360093417216412199 has a factor: 59547637466852043611708058111909725657028150812842162510646420336832110759 Luigi
 2006-05-02, 18:09 #31 ewmayer ∂2ω=0     Sep 2002 República de California 2×59×83 Posts OK, let's move on to Master's level: M12160287649628674460477464915995054973742562690104903778198683593 M24247014121478057345510500801908699603302763478708108175450119307
2006-05-02, 22:44   #32
ET_
Banned

"Luigi"
Aug 2002
Team Italia

25×149 Posts

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

 2006-05-06, 13:16 #33 ET_ Banned     "Luigi" Aug 2002 Team Italia 25×149 Posts 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

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 Factoring 9 2016-12-21 21:22 kurtulmehtap Math 21 2010-11-08 18:21 ladderbook Factoring 14 2008-11-27 13:02 VJS Lounge 4 2005-05-09 20:56 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.