mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2013-02-25, 15:57   #1
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13·257 Posts
Default 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 = 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.

Last fiddled with by bsquared on 2013-02-25 at 15:59 Reason: add link
bsquared is offline   Reply With Quote
Old 2013-02-25, 18:43   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

213448 Posts
Default

Now, THAT's news....
Thanks a billion!
LaurV is offline   Reply With Quote
Old 2013-02-25, 22:43   #3
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·2,399 Posts
Default

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!
Dubslow is offline   Reply With Quote
Old 2013-02-25, 22:48   #4
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13·257 Posts
Default

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.
bsquared is offline   Reply With Quote
Old 2013-02-26, 00:47   #5
skan
 
skan's Avatar
 
Apr 2012

10111102 Posts
Default

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
skan is offline   Reply With Quote
Old 2013-02-26, 01:14   #6
swellman
 
swellman's Avatar
 
Jun 2012

22·3·241 Posts
Default

Great news! Thanks for all the work.

swellman is online now   Reply With Quote
Old 2013-02-26, 04:19   #7
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13×257 Posts
Default

Quote:
Originally Posted by bsquared View Post

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.
bsquared is offline   Reply With Quote
Old 2013-02-26, 06:05   #8
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×2,399 Posts
Default

Fun fact: Somewhere between 2500-3000 lines of new NFS code were added, written almost entirely by Ben
Dubslow is offline   Reply With Quote
Old 2013-02-26, 12:47   #9
Mr. Odd
 
Mar 2010

5510 Posts
Default

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?
Mr. Odd is offline   Reply With Quote
Old 2013-02-26, 17:30   #10
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

64158 Posts
Default

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 is offline   Reply With Quote
Old 2013-02-26, 17:33   #11
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13·257 Posts
Default

Quote:
Originally Posted by Mr. Odd View Post
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.
bsquared is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 12:47.

Thu Nov 26 12:47:11 UTC 2020 up 77 days, 9:58, 4 users, load averages: 1.41, 1.29, 1.34

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