20210928, 04:22  #1 
"Felix"
Sep 2021
Indonesia
7 Posts 
CADONFS minimum factorization digits limit
I want to ask if CADONFS have a fix minimum digit limit for factorization ? I want to use CADONFS for my undergraduate thesis, I planed to use CADONFS 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:
➜ cadonfs git:(master) ✗ ./cadonfs.py 27 Traceback (most recent call last): File "./cadonfs.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) 
20210928, 04:37  #2 
"Curtis"
Feb 2005
Riverside, CA
5634_{10} 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! 
20210928, 07:31  #3  
"Felix"
Sep 2021
Indonesia
7 Posts 
Quote:


20210928, 10:12  #4 
"Oliver"
Sep 2017
Porta Westfalica, DE
1,321 Posts 
You will not be able to proof your point by doing such small NFS factorisations. Yes, for RSA numbers, NFS is wellsuited, 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. 
20210928, 12:12  #5 
Apr 2020
1110011101_{2} Posts 
CADO is refusing to run because it can't find a parameter file for a 2digit 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^21, g(x)=x4, but f(x) is reducible and this gives you the factorization straight away. 
20210928, 16:07  #6  
"Curtis"
Feb 2005
Riverside, CA
2×3^{2}×313 Posts 
Quote:
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. 

20210928, 19:16  #7 
"Vincent"
Apr 2010
Over the rainbow
2^{2}·7·103 Posts 
Yafu SIQS is good from 60 to 90 digits. Below that, ecm/ PM1 is the way to go.

20210929, 02:09  #8  
"Felix"
Sep 2021
Indonesia
7 Posts 
Quote:
Ahhh I see, I get it already I will change my thesis topics... So it more reasonable... Thanks again 

20210929, 02:12  #9  
"Felix"
Sep 2021
Indonesia
7 Posts 
Quote:


20210929, 02:26  #10  
"Curtis"
Feb 2005
Riverside, CA
1011000000010_{2} Posts 
Quote:
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 (gmpecm 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 timetofactor 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 1525% 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. 

20210929, 02:29  #11  
"Felix"
Sep 2021
Indonesia
7 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Parameter explorations for CADO 165170 digits  VBCurtis  CADONFS  98  20230111 13:19 
Some CADONFS Work At Around 175180 Decimal Digits  EdH  CADONFS  127  20201007 01:47 
How to set the limit of digits of qs in yafu ...  rockzur  Factoring  1  20190824 15:40 
How I Run a Larger Factorization Via CADONFS on Several Ubuntu Machines  EdH  EdH  0  20180225 18:00 
CADO workshop on integer factorization  akruppa  Factoring  14  20080918 23:52 