mersenneforum.org Résumé factoring?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2021-04-05, 08:49   #12
Unitome

Apr 2021

17 Posts

Quote:
 Originally Posted by LaurV If you took the RSA number and changed a 1 into a 2, you have a 50% chance you got a number divisible by 3, plus a ~16% chance your number is divisible by 7, etc, so a quite high chance your new number has very small prime factors. You will need to run a lot of other stuff (TF, P-1, ECM) on it to make it "NFS-ready", before attempting to find any (enough) independent relations... Try yafu on your new number and see what factors will it come with.
This is what I needed to hear! Thank you! None of the instructions mention this! I guess I should say none of the ones I was using mention that, which were the gilchrist beginners guide and the post 3 on the stickied beginners guide. It appears that post 1 does say to do YAFU first, but that guide is not functioning (for me at least) and only post 3 is, so that is what I was focused on.

Last fiddled with by Unitome on 2021-04-05 at 08:55

2021-04-05, 09:02   #13
LaurV
Romulan Interpreter

Jun 2011
Thailand

5×1,889 Posts

Quote:
 Originally Posted by Unitome This is what I needed to hear! Thank you! None of the instructions mention this!
Well, that's kind of common sense, you will run NFS only after you picked all "low hanging fruits", i.e. extracted all small factors you could. Otherwise it makes no sense to waste the time doing NFS, and the algorithms assume that at least some basic TF was done. The RSA numbers are by definition "hard", they don't have small factors. But if 3 is not a factor, it means that the number is either 1 or 2 (mod 3), so changing a digit from 1 to 2 (remember the school rule of divisibility to 3? sum the digits?) will add 1 to the modulus, you get respective 2 or 0 (mod 3), and so on. So you have a 50% chance that your "change" introduced a small prime factor 3 (and add more for 7, 11, etc, or even 5, if you did that for the last digit), causing NFS to go on the weeds.

Last fiddled with by LaurV on 2021-04-05 at 09:05

2021-04-06, 00:43   #14
Unitome

Apr 2021

100012 Posts

Quote:
 Originally Posted by LaurV Well, that's kind of common sense, you will run NFS only after you picked all "low hanging fruits", i.e. extracted all small factors you could. Otherwise it makes no sense to waste the time doing NFS, and the algorithms assume that at least some basic TF was done. The RSA numbers are by definition "hard", they don't have small factors. But if 3 is not a factor, it means that the number is either 1 or 2 (mod 3), so changing a digit from 1 to 2 (remember the school rule of divisibility to 3? sum the digits?) will add 1 to the modulus, you get respective 2 or 0 (mod 3), and so on. So you have a 50% chance that your "change" introduced a small prime factor 3 (and add more for 7, 11, etc, or even 5, if you did that for the last digit), causing NFS to go on the weeds.
For me, common sense is that GGNFS already does that ;). I don't know why it wouldn't. Seems like common sense that it would. Or at least an error output that accurately portrays the problem (ERROR: small factors found, please run ECM first). Unless GGNFS was conceived of as basically an RSA algorithm in which case it makes sense.

Last fiddled with by Unitome on 2021-04-06 at 00:54

 2021-04-06, 01:12 #15 VBCurtis     "Curtis" Feb 2005 Riverside, CA 34×59 Posts GGNFS is exactly and only the siever program that finds relations. It is not, and never was, a package to run an entire NFS job. If you want something fool-proof, use YAFU. In fact, beginners should use it anyway, and only try what you're doing once they have enough experience to think they can choose better settings themselves to get faster factorization jobs- or, those who prefer to run individual steps manually (such as, ahem, ECM).
2021-04-06, 08:28   #16
Unitome

Apr 2021

1710 Posts

Quote:
 Originally Posted by VBCurtis GGNFS is exactly and only the siever program that finds relations. It is not, and never was, a package to run an entire NFS job. If you want something fool-proof, use YAFU. In fact, beginners should use it anyway, and only try what you're doing once they have enough experience to think they can choose better settings themselves to get faster factorization jobs- or, those who prefer to run individual steps manually (such as, ahem, ECM).
Perfect thanks, ya it looks like YAFU is using the GGNFS folder binaries so it is a one-stop-shop (ie: will it give the full prime factorization, and as speedy as running GGNFS) for random/new numbers under say c160? What program is recommended to do ECM separately?

Last fiddled with by Unitome on 2021-04-06 at 08:52

2021-04-06, 08:40   #17
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

2×5×587 Posts

Quote:
 Originally Posted by VBCurtis GGNFS is exactly and only the siever program that finds relations. It is not, and never was, a package to run an entire NFS job.
Once upon a time GGNFS was a collection of programs that would do a complete factorization itself using the factLat.pl script to pull them together. Many of these tools haven't been used in years for anything meaningful. I am not sure which programs were written from scratch for ggnfs. The siever wasn't and I suspect the polynomial selection wasn't(pol5) although it had an alternative that probably was.

2021-04-06, 11:57   #18
EdH

"Ed Hall"
Dec 2009

2×3×619 Posts

Quote:
 Originally Posted by Unitome . . . What program is recommended to do ECM separately?
You can do just the ECM phase with YAFU by using ECM(). You can run ECM directly, but it will run single-threaded. You can also use ecm.py to multithread ECM. Check near the last post for the latest revision.

YAFU will step through several B1 values, while the others will perform your given number of curves on your given B1 [B2].

2021-04-06, 15:42   #19
chris2be8

Sep 2009

2×1,021 Posts

Quote:
 Originally Posted by henryzz Once upon a time GGNFS was a collection of programs that would do a complete factorization itself using the factLat.pl script to pull them together. Many of these tools haven't been used in years for anything meaningful. I am not sure which programs were written from scratch for ggnfs. The siever wasn't and I suspect the polynomial selection wasn't(pol5) although it had an alternative that probably was.
I think pol5 was written as part of ggnfs. But you would be better off using msieve for polynomial selection today. In fact all you need is the lattice sievers, msieve and a current driver script (factMsieve.pl or factmsieve.py). The rest of ggnfs is only of historical interest now.

Chris

2021-04-07, 08:03   #20
Unitome

Apr 2021

17 Posts

Quote:
 Originally Posted by EdH You can do just the ECM phase with YAFU by using ECM(). You can run ECM directly, but it will run single-threaded. You can also use ecm.py to multithread ECM. Check near the last post for the latest revision. YAFU will step through several B1 values, while the others will perform your given number of curves on your given B1 [B2].
Thanks!

Also just for any newbies who read this someday, I tested YAFU and GGNFS and GGNFS is much faster than YAFU for numbers that GGNFS can factor. Roughly 40% faster on 100 digit numbers.

Last fiddled with by Unitome on 2021-04-07 at 08:08

2021-04-07, 14:24   #21
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

34×59 Posts

Quote:
 Originally Posted by Unitome Thanks! Also just for any newbies who read this someday, I tested YAFU and GGNFS and GGNFS is much faster than YAFU for numbers that GGNFS can factor. Roughly 40% faster on 100 digit numbers.
This makes no sense- YAFU uses the GGNFS sievers, and you cannot use just GGNFS to factor a number (Henryzz's historical note aside). Do you mean you used factmsieve.py script as an alternative to YAFU? Also, a single test at 100 digits is in no way indicative of how performance will scale to other sizes- if you run the same comparison at 110 and 120 digits, the performance difference will change markedly.

Did YAFU use quadratic sieve, instead of NFS? Perhaps you don't have YAFU "tuned" yet for your hardware. Sorry that I don't recall how to do so.

2021-04-07, 15:40   #22
chris2be8

Sep 2009

37728 Posts

Quote:
 Originally Posted by Unitome Thanks! Also just for any newbies who read this someday, I tested YAFU and GGNFS and GGNFS is much faster than YAFU for numbers that GGNFS can factor. Roughly 40% faster on 100 digit numbers.
Did YAFU run ECM before it started GNFS? Telling yafu to factor a number will make it look for small factors with ECM etc before resorting to QS or GNFS. That's a waste of time if you know the number has no small factors.

Another thing worth doing is to read all the INSTALL and Readme files bundled with ggnfs and msieve. Then read them again (it will take several readings for it to all sink in). And every year or so re-read them for bits you didn't quite understand last time. The same is true of the readme etc that come with ECM. And the README and docfile bundled with YAFU.

Chris

 Similar Threads Thread Thread Starter Forum Replies Last Post baih Miscellaneous Math 9 2020-09-21 07:11 xx005fs GPU Computing 3 2018-10-27 14:49

All times are UTC. The time now is 15:43.

Tue May 11 15:43:06 UTC 2021 up 33 days, 10:23, 1 user, load averages: 2.09, 2.09, 2.10