mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2020-08-26, 19:59   #1
Ensigm
 
Aug 2020

3×5×7 Posts
Post 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?
Ensigm is online now   Reply With Quote
Old 2020-08-26, 20:05   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×4,591 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2020-08-26, 20:20   #3
Ensigm
 
Aug 2020

3×5×7 Posts
Default

Quote:
Originally Posted by Batalov View Post
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?
Ensigm is online now   Reply With Quote
Old 2020-08-26, 20:37   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23DE16 Posts
Default

Quote:
Originally Posted by Ensigm View Post
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).
Batalov is offline   Reply With Quote
Old 2020-08-26, 20:38   #5
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

5×29×31 Posts
Default

Quote:
Originally Posted by Ensigm View Post
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.
VBCurtis is online now   Reply With Quote
Old 2020-08-26, 21:10   #6
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3,347 Posts
Default

Quote:
Originally Posted by Ensigm View Post
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.
bsquared is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Nearly all Factors up to 2^69 found between 2.9G and 2.95G Kalli Hofmann Marin's Mersenne-aries 12 2019-11-06 11:49
Best Way to find large factors mahnouman Information & Answers 19 2013-02-22 06:11
No factors found aketilander PrimeNet 9 2011-05-17 11:32
5dpf, 5 digits from the end partial factors dsouza123 Factoring 6 2004-04-26 16:57
More factors found with a new program alpertron ElevenSmooth 8 2003-10-15 10:29

All times are UTC. The time now is 03:01.

Wed Dec 2 03:01:01 UTC 2020 up 83 days, 11 mins, 1 user, load averages: 1.33, 1.36, 1.43

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.