CADO-NFS minimum factorization digits limit

[totmalone]

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:

➜ cado-nfs git:(master) ✗ ./cado-nfs.py 27
Traceback (most recent call last):
  File "./cado-nfs.py", line 144, in <module>
    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 ?

[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!

[totmalone]

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

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

[charybdis]

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.

[VBCurtis]

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.

[firejuggler]

Yafu SIQS is good from 60 to 90 digits. Below that, ecm/ PM1 is the way to go.

[totmalone]

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

[totmalone]

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

[VBCurtis]

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.

[totmalone]

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