mersenneforum.org  

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

Reply
 
Thread Tools
Old 2021-09-29, 04:58   #12
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

125548 Posts
Default

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.
VBCurtis is offline   Reply With Quote
Old 2021-10-02, 03:18   #13
totmalone
 
totmalone's Avatar
 
"Felix"
Sep 2021
Indonesia

78 Posts
Question It's a following question

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.

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:
Code:
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 ?
totmalone is offline   Reply With Quote
Old 2021-10-02, 03:24   #14
axn
 
axn's Avatar
 
Jun 2003

2·3·17·53 Posts
Default

Quote:
Originally Posted by totmalone View Post
It's seems running using NFS ? or it's just automatics choose what method to factor an integer ?
Code:
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).
axn is online now   Reply With Quote
Old 2021-10-02, 03:49   #15
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

22×3×457 Posts
Default

Quote:
Originally Posted by totmalone View Post
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.
VBCurtis 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 95 2022-07-07 14:15
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 14:00.


Mon Oct 3 14:00:42 UTC 2022 up 46 days, 11:29, 0 users, load averages: 1.38, 1.58, 1.65

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

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔