mersenneforum.org CADO-NFS minimum factorization digits limit
 Register FAQ Search Today's Posts Mark Forums Read

 2021-09-28, 04:22 #1 totmalone     "Felix" Sep 2021 Indonesia 716 Posts CADO-NFS minimum factorization digits limit I want to ask if CADO-NFS have a fix minimum digit limit for factorization ? I want to use CADO-NFS for my undergraduate thesis, I planed to use CADO-NFS and Shor's Algorithm to factorize some small number, since Shor's algorithm can factor below 60. But when I try to factor e.g 15, I get this error: Code: ➜ cado-nfs git:(master) ✗ ./cado-nfs.py 27 Traceback (most recent call last): File "./cado-nfs.py", line 144, in parameters, db = toplevel_params.get_cooked_parameters() File "./scripts/cadofactor/toplevel.py", line 1175, in get_cooked_parameters self.set_N_paramfile_workdir() File "./scripts/cadofactor/toplevel.py", line 647, in set_N_paramfile_workdir self.args.parameters = self.find_default_parameter_file() File "./scripts/cadofactor/toplevel.py", line 187, in find_default_parameter_file " for %s (tried %s)" % (attempts[0], ", ".join(attempts))) RuntimeError: no parameter file found for c2 (tried c2, c0) Any suggestion how I can factor small number ?
 2021-09-28, 04:37 #2 VBCurtis     "Curtis" Feb 2005 Riverside, CA 22·32·149 Posts CADO works for sizes far below the range where NFS is a good idea- say, 60 digits. Nobody would use a software package of any type to factor 15, or any other number you can factor in your head faster than you can invoke the software to do it for you. If your thesis idea includes comparing "regular" software to shor's algorithm, use trial factoring to factor numbers below 15 digits or so. Coding that yourself is a useful exercise!
2021-09-28, 07:31   #3
totmalone

"Felix"
Sep 2021
Indonesia

1112 Posts

Quote:
 Originally Posted by VBCurtis CADO works for sizes far below the range where NFS is a good idea- say, 60 digits. Nobody would use a software package of any type to factor 15, or any other number you can factor in your head faster than you can invoke the software to do it for you. If your thesis idea includes comparing "regular" software to shor's algorithm, use trial factoring to factor numbers below 15 digits or so. Coding that yourself is a useful exercise!
Thanks for your suggestion, but I want to use CADO / NFS too support my thesis point, which NFS is more practical now days than using Shor's algorithm especially factoring RSA number....

 2021-09-28, 10:12 #4 kruoli     "Oliver" Sep 2017 Porta Westfalica, DE 2·541 Posts You will not be able to proof your point by doing such small NFS factorisations. Yes, for RSA numbers, NFS is well-suited, you might even argue that if you know it is an RSA number you may skip trial factoring and ECM, but only in this case. For a general number, you would never use CADO as your only tool. That's inappropriate.
 2021-09-28, 12:12 #5 charybdis     Apr 2020 22·199 Posts CADO is refusing to run because it can't find a parameter file for a 2-digit number. If you actually put a params file together, you still get various errors, because CADO is not designed to run on numbers this small. Indeed, if you actually were to attempt NFS on the number 15, you would likely accidentally factor it at some point before the algorithm completes. For example, you might find the possible polynomial pair f(x)=x^2-1, g(x)=x-4, but f(x) is reducible and this gives you the factorization straight away.
2021-09-28, 16:07   #6
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

22×32×149 Posts

Quote:
 Originally Posted by totmalone Thanks for your suggestion, but I want to use CADO / NFS too support my thesis point, which NFS is more practical now days than using Shor's algorithm especially factoring RSA number....
Well, then you should be spending your effort studying and writing about asymptotic complexity of each algorithm rather than trying to factor tiny numbers. If you use tiny inputs for comparison, you're likely as not to reach conclusions akin to "walking is faster than driving. I know because I can walk to my mailbox faster than I can drive to it." That's a silly conclusion, but a statement like "walking is faster for distances below 500 feet, while driving is faster for distances over 500 feet" is more meaningful.

NFS is the wrong tool to use below 90 digits, and trying to factor 15 (or a ten digit number) is folly the same way a jet aircraft is the wrong tool to use to get to your mailbox.

 2021-09-28, 19:16 #7 firejuggler     "Vincent" Apr 2010 Over the rainbow 5×569 Posts Yafu SIQS is good from 60 to 90 digits. Below that, ecm/ PM1 is the way to go.
2021-09-29, 02:09   #8
totmalone

"Felix"
Sep 2021
Indonesia

7 Posts

Quote:
 Originally Posted by VBCurtis Well, then you should be spending your effort studying and writing about asymptotic complexity of each algorithm rather than trying to factor tiny numbers. If you use tiny inputs for comparison, you're likely as not to reach conclusions akin to "walking is faster than driving. I know because I can walk to my mailbox faster than I can drive to it." That's a silly conclusion, but a statement like "walking is faster for distances below 500 feet, while driving is faster for distances over 500 feet" is more meaningful. NFS is the wrong tool to use below 90 digits, and trying to factor 15 (or a ten digit number) is folly the same way a jet aircraft is the wrong tool to use to get to your mailbox.

Ahhh I see, I get it already I will change my thesis topics... So it more reasonable... Thanks again

2021-09-29, 02:12   #9
totmalone

"Felix"
Sep 2021
Indonesia

7 Posts

Quote:
 Originally Posted by kruoli You will not be able to proof your point by doing such small NFS factorisations. Yes, for RSA numbers, NFS is well-suited, you might even argue that if you know it is an RSA number you may skip trial factoring and ECM, but only in this case. For a general number, you would never use CADO as your only tool. That's inappropriate.
Sorry if I too bold... Is that a tools for factoring general number ? Some tools in web are obsolete or abandoned...

2021-09-29, 02:26   #10
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

10100111101002 Posts

Quote:
 Originally Posted by totmalone Sorry if I too bold... Is that a tools for factoring general number ? Some tools in web are obsolete or abandoned...
If you have a number you wish to factor, and no particular information about the number:
1. Try to divide by small primes, called "trial factoring". Fast, up to 10^10 or so. Literally divide by every prime up to 10^10, and then you're sure there are no factors smaller than that.

2. Use ECM (gmp-ecm is the usual software package to use ECM). Depending on what bounds you give the ECM software. this can find factors very small, like 10 digits, or quite large like 70 digits. But ECM's time-to-factor scales with the size of the *factor*, not the size of the input number- so, once one spends some time using ECM to rule out small factors, one then....

3. Use GNFS (CADO is fastest software for the GNFS algorithm, but yafu / ggnfs/msieve combination is also commonly used). The time to factor with GNFS scales with the size of the input number. Once one uses CADO a few times, one gets a good sense for how long it will take. Once you know how long GNFS will take, you can use the rule of thumb to spend 15-25% of the time it would take GNFS to run trying ECM to look for small factors.

The "yafu" software package automates all three of these steps. If you want such an automated system for yourself, have a look at EdH's blog area for directions to set up the various software packages. Note that ECM is installed on most linux systems by default; you can just type "echo {input number} | ecm -h to get some directions.

2021-09-29, 02:29   #11
totmalone

"Felix"
Sep 2021
Indonesia

7 Posts

Quote:
 Originally Posted by VBCurtis If you have a number you wish to factor, and no particular information about the number: 1. Try to divide by small primes, called "trial factoring". Fast, up to 10^10 or so. Literally divide by every prime up to 10^10, and then you're sure there are no factors smaller than that. 2. Use ECM (gmp-ecm is the usual software package to use ECM). Depending on what bounds you give the ECM software. this can find factors very small, like 10 digits, or quite large like 70 digits. But ECM's time-to-factor scales with the size of the *factor*, not the size of the input number- so, once one spends some time using ECM to rule out small factors, one then.... 3. Use GNFS (CADO is fastest software for the GNFS algorithm, but yafu / ggnfs/msieve combination is also commonly used). The time to factor with GNFS scales with the size of the input number. Once one uses CADO a few times, one gets a good sense for how long it will take. Once you know how long GNFS will take, you can use the rule of thumb to spend 15-25% of the time it would take GNFS to run trying ECM to look for small factors. The "yafu" software package automates all three of these steps. If you want such an automated system for yourself, have a look at EdH's blog area for directions to set up the various software packages. Note that ECM is installed on most linux systems by default; you can just type "echo {input number} | ecm -h to get some directions.
Thanks, It already sum up all my question... Cheers

 Similar Threads Thread Thread Starter Forum Replies Last Post VBCurtis CADO-NFS 95 2022-07-07 14:15 EdH CADO-NFS 127 2020-10-07 01:47 rockzur Factoring 1 2019-08-24 15:40 EdH EdH 0 2018-02-25 18:00 akruppa Factoring 14 2008-09-18 23:52

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

Mon Aug 8 20:05:38 UTC 2022 up 32 days, 14:52, 1 user, load averages: 1.18, 1.15, 1.13