mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > CADO-NFS

Reply
 
Thread Tools
Old 2021-09-28, 04:22   #1
totmalone
 
totmalone's Avatar
 
"Felix"
Sep 2021
Indonesia

7 Posts
Question 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 <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 ?
totmalone is offline   Reply With Quote
Old 2021-09-28, 04:37   #2
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

7×23×31 Posts
Default

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!
VBCurtis is online now   Reply With Quote
Old 2021-09-28, 07:31   #3
totmalone
 
totmalone's Avatar
 
"Felix"
Sep 2021
Indonesia

7 Posts
Thumbs up

Quote:
Originally Posted by VBCurtis View Post
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....
totmalone is offline   Reply With Quote
Old 2021-09-28, 10:12   #4
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

3×5×43 Posts
Default

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.
kruoli is offline   Reply With Quote
Old 2021-09-28, 12:12   #5
charybdis
 
charybdis's Avatar
 
Apr 2020

22×3×41 Posts
Default

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.
charybdis is offline   Reply With Quote
Old 2021-09-28, 16:07   #6
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

7×23×31 Posts
Default

Quote:
Originally Posted by totmalone View Post
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.
VBCurtis is online now   Reply With Quote
Old 2021-09-28, 19:16   #7
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

2·33·72 Posts
Default

Yafu SIQS is good from 60 to 90 digits. Below that, ecm/ PM1 is the way to go.
firejuggler is offline   Reply With Quote
Old 2021-09-29, 02:09   #8
totmalone
 
totmalone's Avatar
 
"Felix"
Sep 2021
Indonesia

78 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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 is offline   Reply With Quote
Old 2021-09-29, 02:12   #9
totmalone
 
totmalone's Avatar
 
"Felix"
Sep 2021
Indonesia

7 Posts
Default

Quote:
Originally Posted by kruoli View Post
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...
totmalone is offline   Reply With Quote
Old 2021-09-29, 02:26   #10
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

7×23×31 Posts
Default

Quote:
Originally Posted by totmalone View Post
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.
VBCurtis is online now   Reply With Quote
Old 2021-09-29, 02:29   #11
totmalone
 
totmalone's Avatar
 
"Felix"
Sep 2021
Indonesia

7 Posts
Thumbs up

Quote:
Originally Posted by VBCurtis View Post
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
totmalone is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Parameter explorations for CADO 165-170 digits VBCurtis CADO-NFS 70 2021-10-07 17:56
Some CADO-NFS Work At Around 175-180 Decimal Digits EdH CADO-NFS 127 2020-10-07 01:47
How to set the limit of digits of qs in yafu ... rockzur Factoring 1 2019-08-24 15:40
How I Run a Larger Factorization Via CADO-NFS on Several Ubuntu Machines EdH EdH 0 2018-02-25 18:00
CADO workshop on integer factorization akruppa Factoring 14 2008-09-18 23:52

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


Sat Oct 16 04:03:08 UTC 2021 up 84 days, 22:32, 0 users, load averages: 1.91, 1.48, 1.23

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.