mersenneforum.org How are the large factors more than 100 digits found?
 Register FAQ Search Today's Posts Mark Forums Read

 2020-08-26, 19:59 #1 Ensigm   Aug 2020 2·3·19 Posts How are the large factors more than 100 digits found? Like this 128-digit factor of M1171, or this 104-digit factor of M1193. If the list https://members.loria.fr/PZimmermann/records/top50.html is up to date, then the largest factor found using ECM has just 83 digits. How are these factors with more than 100 digits found?
 2020-08-26, 20:05 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 9,391 Posts These are found by NFS method. Mersenne numbers are a subset of the Cunningham project, where the exact method for factoring specific numbers is listed.
2020-08-26, 20:20   #3
Ensigm

Aug 2020

2·3·19 Posts

Quote:
 Originally Posted by Batalov These are found by NFS method.

I see, thank you. For a given number, at what level shall we stop using ECM and switch to NFS?

2020-08-26, 20:37   #4
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,391 Posts

Quote:
 Originally Posted by Ensigm I see, thank you. For a given number, at what level shall we stop using ECM and switch to NFS?
There are different heuristics, they depend on a lot of factors/considerations.
Usually. people pre-factor with TF, ECM etc until X% of the SNFS-complexity, or of GNFS-size. (where X varies between different opinions; search the forum, as well as SSW webpage and mathworld and similar).

The problem in a nutshell is: 1) when factor is already known - you can easily look retrospectively and make a conclusion: "We would have needed N times _more_ time to keep ECMming and we would have found it ..or not" (and we could even arrive at paradoxical conslusion: "we would have saved so much time by not ECMming, skipping it altogether"); 2) we don't know the factor. We ecm up to the point when time to factor by NFS becomes less than the estimated time to get lucky with ECM (and factoring in probability that maybe it is out of reach of ECM).

2020-08-26, 20:38   #5
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

3×1,579 Posts

Quote:
 Originally Posted by Ensigm I see, thank you. For a given number, at what level shall we stop using ECM and switch to NFS?
There are two flavors of NFS: Special, abbreviated SNFS, and general GNFS.

For numbers where SNFS is faster, a rule of thumb is to ECM up to 0.22 * the difficulty of the number; e.g. SNFS-300 would get ECM up to 66 digits (about 1.4 * T65).

For numbers where GNFS is faster or SNFS is not possible, a rule of thumb is ECM to 0.31 * the number of digits; a GNFS-200 would get 62 digits (2 * T60, or a T60 plus a T60 worth of T65-sized curves).

These rules of thumb are not super accurate; to be precise, one gives up on ECM when the marginal next set of ECM curves has less chance to factor the number than the fraction of expected NFS-solving time the set of curves takes. That calculation is tricky, to say the least, so the rules of thumb above exist; both my stated ratios are on the low side, many people do a bit more ECM than indicated here.

2020-08-26, 21:10   #6
bsquared

"Ben"
Feb 2007

22×23×37 Posts

Quote:
 Originally Posted by Ensigm I see, thank you. For a given number, at what level shall we stop using ECM and switch to NFS?
If your interest is limited to factoring Mersenne numbers, then the practical advice is probably: never. Unless you represent a small government or large research collaboration? Only they have the resources needed to approach the smallest unfactored Mersenne number by NFS.

If you are asking in general then Batalov and VBCurtis have good advice.

 Similar Threads Thread Thread Starter Forum Replies Last Post Kalli Hofmann Marin's Mersenne-aries 14 2021-04-12 13:12 mahnouman Information & Answers 19 2013-02-22 06:11 aketilander PrimeNet 9 2011-05-17 11:32 dsouza123 Factoring 6 2004-04-26 16:57 alpertron ElevenSmooth 8 2003-10-15 10:29

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

Sun Apr 18 08:38:19 UTC 2021 up 10 days, 3:19, 0 users, load averages: 3.55, 2.13, 1.60