YAFU-1.34

bsquared · 2013-02-25, 15:57

There is a lot of new stuff in this version, 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.

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.

bsquared · 2013-02-26, 04:19

Quote:

Originally Posted by bsquared

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.

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

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

. Let me know if there are any other problems.

bsquared · 2013-02-26, 17:33

Quote:

Originally Posted by Mr. Odd

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?

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.

2013-02-25, 15:57	#1
bsquared "Ben" Feb 2007 7245₈ Posts	YAFU-1.34 There is a lot of new stuff in this version, highlights include: Fully automated SNFS factorization. Polynomial selection is supported for a variety of special forms: N = ab^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. Last fiddled with by bsquared on 2013-02-25 at 15:59 Reason: add link*

2013-02-26, 00:47	#5
skan Apr 2012 94₁₀ Posts	Great job, thanks though I've just posted a possible bug (related with compilation?) Last fiddled with by skan on 2013-02-26 at 01:38

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Yafu	bsquared	YAFU	1276	2019-01-12 04:46
Running YAFU via Aliqueit doesn't find yafu.ini	EdH	YAFU	8	2018-03-14 17:22
Yafu bug.	storflyt32	YAFU	2	2015-06-29 05:19
yafu-1.33	bsquared	YAFU	12	2012-11-08 04:12
yafu-1.32.1	bsquared	YAFU	21	2012-09-04 19:44

2013-02-25, 18:43	#2
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 24055₈ Posts	Now, THAT's news.... Thanks a billion!

2013-02-25, 22:43	#3
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 3·29·83 Posts	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. Thanks a billion Ben!

2013-02-25, 22:48	#4
bsquared "Ben" Feb 2007 7245₈ Posts	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.

2013-02-26, 01:14	#6
swellman Jun 2012 3·1,303 Posts	Great news! Thanks for all the work.

2013-02-26, 06:05	#8
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 3×29×83 Posts	Fun fact: Somewhere between 2500-3000 lines of new NFS code were added, written almost entirely by Ben

2013-02-26, 12:47	#9
Mr. Odd Mar 2010 2²×3×5 Posts	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?

2013-02-26, 17:30	#10
bsquared "Ben" Feb 2007 23·163 Posts	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 . Let me know if there are any other problems.