mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2019-12-08, 01:28   #254
PhilF
 
PhilF's Avatar
 
Feb 2005
Colorado

2·3·7·13 Posts
Default

Quote:
Originally Posted by storm5510 View Post
I have never understood the use of a random number, Sigma in this case. It seems to overly complicate the process.
With quadrillions upon quadrillions (that is a huge understatement actually) of possible ECM curves that could be run, do you have an alternative to random when it comes to picking which one to run?
PhilF is online now   Reply With Quote
Old 2019-12-08, 14:26   #255
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

69416 Posts
Default

Quote:
Originally Posted by PhilF View Post
With quadrillions upon quadrillions (that is a huge understatement actually) of possible ECM curves that could be run, do you have an alternative to random when it comes to picking which one to run?
No, I do not. I wish there was another way. A lot of people spent a lot of time running ECM's on M1277. In the end, everyone had to surrender. At the time, I remember someone writing, "A factor will be found using SNFS." If a person takes it out into decimal form, it is 385 digits long, if I remember correctly. As far as I know, none of the YAFU functions can handle something that large. As the same time, other programs would say this is too small. All of us will simply have to carry on with what is available now.
storm5510 is offline   Reply With Quote
Old 2019-12-08, 16:22   #256
PhilF
 
PhilF's Avatar
 
Feb 2005
Colorado

2×3×7×13 Posts
Default

Quote:
Originally Posted by storm5510 View Post
No, I do not. I wish there was another way. A lot of people spent a lot of time running ECM's on M1277. In the end, everyone had to surrender. At the time, I remember someone writing, "A factor will be found using SNFS." If a person takes it out into decimal form, it is 385 digits long, if I remember correctly. As far as I know, none of the YAFU functions can handle something that large. As the same time, other programs would say this is too small. All of us will simply have to carry on with what is available now.
That is true. But I recall someone else wrote "M1277 will never be factored".

It is easy to lose perspective of how large the numbers we are dealing with really are. We talk about a 385 digit number like it is just a number, when the total number of atoms in the entire universe is only 70 or 80 digits. That puts it somewhere between ten quadrillion vigintillion and one-hundred thousand quadrillion vigintillion

No, I have never heard of a vigintillion until now either.
PhilF is online now   Reply With Quote
Old 2019-12-08, 18:05   #257
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

32·7·71 Posts
Default

Quote:
Originally Posted by storm5510 View Post
A lot of people spent a lot of time running ECM's on M1277. In the end, everyone had to surrender.
Who says we surrendered? A typical estimate (not very accurate at this size) for ECM depth to run in pretesting before SNFS is 0.21 * digits. 0.21 * 385 is just over 80 digits. So, ECM curves at the 80 digits level should be run before we move to SNFS. As far as I know, we're not done with the 75-digit level yet, so we are maybe 10-15% of the way done with ECM on this number.

Some very rough numbers:
Let's say we've done t73 worth of ECM. The nth digit worth of ECM has a 1/n chance to find a factor, so going from 73 digits to 80 digits has, say, 8-9% chance to find a factor.

Before we get to t80 worth of ECM, someone will more precisely calculate the "right" amount of ECM to do. The SNFS job itself can be run with current software (and a cluster to solve the matrix); it is perhaps 4-8x tougher than RSA-240, the largest GNFS job known to be solved.
VBCurtis is online now   Reply With Quote
Old 2019-12-09, 00:56   #258
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

22×421 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
Who says we surrendered?
Surrendered? The last time I looked at it on PrimeNet. The amount of submitted work had dropped off a lot.

Forgive me for my ignorance: T73?
storm5510 is offline   Reply With Quote
Old 2019-12-09, 01:25   #259
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

32×7×71 Posts
Default

Tnn = digit level to which ECM has been performed. e.g. T50 is shorthand for saying the standard number of curves have been performed at the 50-digit level (B1 = 43M, with the exact number of curves depending on B2 choice).

There are conversions available to convert from other B1 choices, usually via the GMP-ECM -v flag, which tells you how many curves at your chosen B1/B2 it would take to complete T50 or T55 or whatever.

Common use is to only report in 5-digit increments, e.g. T65 or T70; I used T73 as a non-standard way to say "half a T75", while also saying that we've run enough curves to expect to find 71 or 72 digit factors (with "expect" far from "sure we would have found").

Speaking in generalities, it takes about 6x as much work to complete the 5-digit-higher T-level. So, T50 is about 6x longer than T45, likewise T80 is about 6x longer than T75.

Edit: as for surrender, Ryan does more work than the rest of us put together; primenet showing a slowdown may just mean he moved on to other candidates. I interpret "surrender" as "gave up", while the reality is that many folks remain interested and may continue ECM in 2020.

Edit2: I typo'ed, and should have said T73 expects to find factors 73 digits or smaller. That is, after a T70 has been completed, one would expect that half a T75 would find "most" 71 72 73 digit factors (as well as nearly any <71 digit factors that the T70 missed).

Last fiddled with by VBCurtis on 2019-12-09 at 01:33
VBCurtis is online now   Reply With Quote
Old 2019-12-09, 14:03   #260
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

32248 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
...Edit2: I typo'ed, and should have said T73 expects to find factors 73 digits or smaller. That is, after a T70 has been completed, one would expect that half a T75 would find "most" 71 72 73 digit factors (as well as nearly any <71 digit factors that the T70 missed).
I got it. Thanks! PhilF did a lot of work as well using GMP-ECM by running stage one with Prime95.

M1277 was factored to 2^67, I believe. None of the current programs will run an exponent this small, except for Prime95 and GMP-ECM. Prime95 says to run ECM.

Someone in the past ran a huge P-1 test. The lower bound was 13 digits long.
storm5510 is offline   Reply With Quote
Old 2019-12-10, 10:30   #261
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22·7·11·29 Posts
Default

Quote:
Originally Posted by storm5510 View Post
M1277 was factored
Man, you gave me palpitations...
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
ARM ASM request ET_ Programming 0 2018-11-01 14:57
Bug/request Dubslow YAFU 4 2012-03-31 03:07
Odd request? Xyzzy Lounge 23 2011-03-08 17:50
Prime95 featured in Maximum PC! ixfd64 Software 10 2010-05-31 15:21
GMP-ECM Request rogue GMP-ECM 4 2009-11-23 15:07

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

Wed Nov 25 23:20:48 UTC 2020 up 76 days, 20:31, 3 users, load averages: 1.37, 1.35, 1.33

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.