CADO-NFS minimum factorization digits limit

[VBCurtis]

One more thing, since I didn't mention it in my "3 steps":
For numbers smaller than 50-55 digits, steps 1-2 alone are enough; ECM will crack the number as fast or faster than a sieve method, and the time spent is less than a second anyway.
For 55ish-95ish digits, the quadratic sieve is faster than GNFS- one would run the QS via Yafu (or msieve, if you didn't acquire yafu) after running some ECM.
For numbers 95+ digits, the 3 steps I wrote and you quoted are appropriate. The factoring forum posts and advice generally assume 100+ digit numbers as inputs, else one shouldn't be trying GNFS.

For 92-99 digits, which software is faster depends on your specific machine, the parameters passed to CADO, and the version of yafu. It doesn't matter a whole lot, unless you're doing a bunch of jobs of that size- then you might care that one package is 10% faster than another, and you might compare software to find out.

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

I already installing yafu 2 and I already try it, it work like i expected... but when I try to factor 15 I get this result:

Applying tune_info entry for LINUX64 - Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz


YAFU Version 2.07
Built with GCC 11
Using GMP-ECM 7.0.5-dev, Powered by GMP 6.2.1
Detected Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
Detected L1 = 32768 bytes, L2 = 9437184 bytes, CL = 64 bytes
Using 1 random witness for Rabin-Miller PRP checks
Cached 664579 primes; max prime is 9999991

===============================================================
======= Welcome to YAFU (Yet Another Factoring Utility) =======
=======             bbuhrow@gmail.com                   =======
=======     Type help at any time, or quit to quit      =======
===============================================================

>> factor(15)
fac: factoring 15
fac: using pretesting plan: normal
fac: using specified qs/gnfs crossover of 100 digits
fac: using specified qs/snfs crossover of 75 digits
input from file = 1802716097522165018257858828415111497060066282677325501816640492782221110851604465066510547671104729
input to yafu = 15
div: primes less than 10000
div: found prime factor = 3
div: found prime factor = 5
Total factoring time = 0.0528 seconds


***factors found***

P1 = 3
P1 = 5

ans = 1

It's seems running using NFS ? or it's just automatics choose what method to factor an integer ?

[axn]

Originally Posted by totmalone

It's seems running using NFS ? or it's just automatics choose what method to factor an integer ?

div: primes less than 10000
div: found prime factor = 3
div: found prime factor = 5

It performed trial division and found 3 & 5, completing the factorization. It never went to the more complex factoring algorithms.

For a larger number, it would've performed additional steps like Pollard's rho, P-1, ECM, and eventually would've finished it off by either SIQS or NFS (depending on the size of the composite and the qs/nfs crossover points).

[VBCurtis]

Originally Posted by totmalone

It's seems running using NFS ? or it's just automatics choose what method to factor an integer ?

You ought to run something that actually needs NFS to see what the output looks like during the job. It looks nothing like this.
If you'd like to see an NFS job, I can send you a number of 110 digits or so that I'd like factors for. It'll take you an hour or less on an older desktop or modern laptop.