mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2021-04-05, 08:49   #12
Unitome
 
Apr 2021

17 Posts
Default

Quote:
Originally Posted by LaurV View Post
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
Unitome is offline   Reply With Quote
Old 2021-04-05, 09:02   #13
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

223458 Posts
Default

Quote:
Originally Posted by Unitome View Post
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
LaurV is offline   Reply With Quote
Old 2021-04-06, 00:43   #14
Unitome
 
Apr 2021

100012 Posts
Default

Quote:
Originally Posted by LaurV View Post
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
Unitome is offline   Reply With Quote
Old 2021-04-06, 01:12   #15
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

10010101010112 Posts
Default

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).
VBCurtis is online now   Reply With Quote
Old 2021-04-06, 08:28   #16
Unitome
 
Apr 2021

100012 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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
Unitome is offline   Reply With Quote
Old 2021-04-06, 08:40   #17
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·5·587 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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.
henryzz is online now   Reply With Quote
Old 2021-04-06, 11:57   #18
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

2·3·619 Posts
Default

Quote:
Originally Posted by Unitome View Post
. . .
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].
EdH is offline   Reply With Quote
Old 2021-04-06, 15:42   #19
chris2be8
 
chris2be8's Avatar
 
Sep 2009

2×1,021 Posts
Default

Quote:
Originally Posted by henryzz View Post
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
chris2be8 is offline   Reply With Quote
Old 2021-04-07, 08:03   #20
Unitome
 
Apr 2021

17 Posts
Default

Quote:
Originally Posted by EdH View Post
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
Unitome is offline   Reply With Quote
Old 2021-04-07, 14:24   #21
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

34·59 Posts
Default

Quote:
Originally Posted by Unitome View Post
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.
VBCurtis is online now   Reply With Quote
Old 2021-04-07, 15:40   #22
chris2be8
 
chris2be8's Avatar
 
Sep 2009

2×1,021 Posts
Default

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
factoring 2ⁿ-2 equivalent to factoring 2ⁿ-1(I think) baih Miscellaneous Math 9 2020-09-21 07:11
OpenCL GPU P-1 Factoring and ECM Factoring xx005fs GPU Computing 3 2018-10-27 14:49

All times are UTC. The time now is 19:57.

Tue May 11 19:57:38 UTC 2021 up 33 days, 14:38, 1 user, load averages: 1.62, 1.82, 1.86

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.