mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   YAFU (https://www.mersenneforum.org/forumdisplay.php?f=96)
-   -   YAFU-1.34 (https://www.mersenneforum.org/showthread.php?t=17852)

bsquared 2013-02-25 15:57

YAFU-1.34
 
There is a lot of new stuff in [URL="https://sourceforge.net/projects/yafu/"]this version[/URL], highlights include:

Fully automated SNFS factorization. Polynomial selection is supported for a variety of special forms:
N = a*b^n +/- c, for b < 100, c < 2^30, N < 1024 bits
N = b^n +/- 1, for b > 100, N < 1024 bits
N = a^n +/- b^n, for gcd(a,b) = 1, a,b <= 12, N < 1024 bits
N = x^y + y^x, for 1 < x < y < 151, N < 1024 bits

There are two ways to run it. "nfs(number)" will autodetect any of the above forms, and proceed with the primitive factor of the input - but only in "pure" form (i.e., the number can't have been reduced by any known large factors). Use "snfs(number, cofactor)", where "number" is the pure form (i.e. 2^1039-1) and "cofactor" is the number reduced by any known large factors.


Next, WraithX contributed his port of APRCL to YAFU, so now every factor found will be automatically proved prime. A couple new options control when it is run and how verbose the output is: -aprcl_p <num> and -aprcl_d <num>. The defaults are: below 500 digits are automatically proved (the upper end of that range can take a minute or two) and above 200 digits extra verbosity is enabled.


1.34 also contains the first real speedup of my SIQS code in a while. New SSE2 code gives a 2-3% speedup, or, on supported systems, SSE4.1 code gives about a 10% speedup. SSE4.1 is automatically detected and used if found.


Finally, there are quite a few bugfixes and minor updates. Check the changelog for details.

May thanks to all bug reporters and developers that contributed to this version! Very much appreciated!

Happy factoring,
- ben.

LaurV 2013-02-25 18:43

Now, THAT's news....
Thanks a billion!

Dubslow 2013-02-25 22:43

Sweet!

Can we see your Msieve patch?

As it is then, YAFU using Msieve and GMP-ECM is now the best way to automagically factor about any number that can be handled by modern algorithms. :cool: Thanks a billion Ben!

bsquared 2013-02-25 22:48

Sure, I'll post it sometime soon.

Also, there appears to be a problem with factoring certain small inputs with siqs that missed my (woefully insufficient) testing process... somewhere around 130 bits or so. I'm looking into it.

skan 2013-02-26 00:47

Great job, thanks

though I've just posted a possible bug (related with compilation?)

swellman 2013-02-26 01:14

Great news! Thanks for all the work.

:bow wave:

bsquared 2013-02-26 04:19

[QUOTE=bsquared;331006]

Also, there appears to be a problem with factoring certain small inputs with siqs that missed my (woefully insufficient) testing process... somewhere around 130 bits or so. I'm looking into it.[/QUOTE]

Fixed this... sourceforge now has an updated set of binaries.

Dubslow 2013-02-26 06:05

Fun fact: Somewhere between 2500-3000 lines of new NFS code were added, written almost entirely by Ben :cool:

Mr. Odd 2013-02-26 12:47

Does the factor() function automatically invoke snfs if it finishes ECM with a cofactor that requires NFS and the original form meets the proper criteria?

bsquared 2013-02-26 17:30

It turns out the Win32 executable was linked against the wrong ecm library, which was causing it to crash. I've now corrected this (and another unrelated bug). Please re-download (version 1.34.2). Sorry for the churn everyone ... like I said, there was a lot of new stuff in this release :smile:. Let me know if there are any other problems.

bsquared 2013-02-26 17:33

[QUOTE=Mr. Odd;331079]Does the factor() function automatically invoke snfs if it finishes ECM with a cofactor that requires NFS and the original form meets the proper criteria?[/QUOTE]

I actually wasn't sure, so I tested it out and no, it won't. If ecm doesn't find a factor, then it should start snfs, but if it does then the snfs detection code might not recognize it as a special form. You'd have to kill the gnfs poly selection (or run ecm only) and re-start with snfs(form, cofactor). Sorry, an oversight on my part.


All times are UTC. The time now is 13:51.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.