YAFU-1.34

[bsquared]

Originally Posted by Dubslow

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

A good C programmer would probably have only needed half that much to accomplish the same thing .

Also, thanks for your own contributions. I appreciate your willingness to dive in anywhere in the codebase and help out.

Along those lines, thanks again to all developers, beta testers, and bug reporters. YAFU is getting way too big for me to handle on my own.

[Mr. Odd]

Factoring the C128 from 10^154+19 using 1.34:

GNFS elapsed time: 41060
SNFS elapsed time: 7196

Woooo! Thanks so much for making this happen!

[bsquared]

I just updated sourceforge with 1.34.3 binaries (and related source) that contains a bugfix. <fingers crossed> Hopefully this is the last one

TL;DR section:
One of the recent changes involved me updating all of the related factorization packages that are linked into yafu (GMP, MPIR, msieve, and GMP-ECM). This I did with varying degrees of clumsiness, the result being the bug referenced above. Now all of the associated libraries and headers should be consistent, and as a bonus, yafu now uses MPIR 2.6.0, GMP 5.1.1, and GMP-ECM 6.4.2.

Happy factoring!

[WraithX]

Originally Posted by bsquared

There is a lot of new stuff in this version, highlights include:

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.

Also of note, you can manually run APR-CL (prime proving) or BPSW (probable prime test) on individual numbers.

All you have to do is type:
aprcl(10^199+153)
And you can prove this 200 digit number prime in just a few seconds! Just so you can get an idea of how long it will take to prove the primality of various sized numbers, here is a short list of times on my computer:

 100 digits : 5^143+2                 :     0.3125s
 150 digits : 3^313*4+5               :     1.1719s
 200 digits : 7^235*9+2               :     3.0469s
 250 digits : 5^356*8-1               :     6.4844s
 300 digits : 424^114+3               :    12.7344s
 350 digits : 1160^114+7              :    23.6563s
 400 digits : (291^163-1)/290         :    39.3281s
 450 digits : 232^190+7               :    58.0313s
 500 digits : 1014^166+7              :    88.1406s
 550 digits : 10^549*9-7              :   147.4688s
 600 digits : 1432^190+7              :   210.3281s
 650 digits : 2^2159+375              :   265.9844s
 700 digits : (157^319+319^157)/28    :   403.0781s
 750 digits : 10^749*2+89             :   519.9531s
 800 digits : (10^799*61-7)/9         :   709.7500s
 850 digits : 2^2821-183              :   974.4688s
 900 digits : (24^653-1)/23           :  1063.8125s
 950 digits : 10^949*4-9              :  1422.8125s
1000 digits : 10^999+7                :  1588.3125s

The APR-CL code can handle numbers up to 6021 digits in length, but those numbers take a VERY long time to prove. I recently tested it on a 6002 digit input and it was proven prime in 1.56e6 seconds! Also, around those sizes you should probably switch to Primo since it will generate a primality certificate which is easy, and quick, to verify. With APR-CL there is no certificate so to verify primality, someone else would have to run APR-CL again, or some other prime proving code like Primo.

Happy factoring and/or prime proving!

[Mr. Odd]

I just factored a C148 with SNFS in 26 hours (vs. ~120 with GNFS).

I must say it would appear SNFS is a better bet than long ECM runs. The C128 that took 2 hours with SNFS - I figure ECM for no more than 30 minutes should be fine before sending it to SNFS. I think the crossover point from ECM to SNFS is somewhere between 125 and 135 digits on my system.

[bsquared]

Originally Posted by Mr. Odd

I just factored a C148 with SNFS in 26 hours (vs. ~120 with GNFS).

I must say it would appear SNFS is a better bet than long ECM runs. The C128 that took 2 hours with SNFS - I figure ECM for no more than 30 minutes should be fine before sending it to SNFS.

That sounds about right. The commonly used rule of thumb is 2/9 of the snfs difficulty in ecm. So if the difficulty of your c128 is also 128 (they need not be the same!) then ecm to t28.4 (or, if you know the c128 will take 2 hours to snfs, then ecm for 26.7 minutes).

[swellman]

I feel dumb asking this question, but how do I force GNFS poly search even on a special form composite? There are situations where GNFS is prefered over SNFS.

When I run yafu 1.34 it only does SNFS poly search on my xyyx type composite. The -np flag does not change this behavior.

Still playing with 1.34, and so far the new functionality rocks. The additional primality tests are impressive. I'm not very familiar with them, but it's nice to be able to run several rigorous tests that identify a number as being "almost certainly" prime in a short time.

[bsquared]

That... is not a dumb question at all. In fact it seems I've overlooked that possibility At least, nothing is occurring to me as to a way to force it to use gnfs. I guess we'll have at least one more patch to 1.34 at some point. I'll try to get it done tomorrow.

[LaurV]

I know! I know! Pick me! Pick me!

You have to find a factor using ECM, first. Then, as B2 said before, it will not detect that the remaining composite comes from a SNFS-able form, and it will do GNFS...

[ET_]

Originally Posted by LaurV

I know! I know! Pick me! Pick me!

You have to find a factor using ECM, first. Then, as B2 said before, it will not detect that the remaining composite comes from a SNFS-able form, and it will do GNFS...

...even if the initial number was a repdigit?

Luigi

[swellman]

Originally Posted by LaurV

I know! I know! Pick me! Pick me!

You have to find a factor using ECM, first. Then, as B2 said before, it will not detect that the remaining composite comes from a SNFS-able form, and it will do GNFS...

Yafu is too smart for that! With one exception, all the xyyx numbers being factored have had smaller factors stripped out but Yafu still recognizes the special form.

[begin obligatory xyyx pitch]Come on over and try it for yourself! Lots of composites needing to be factored.[/pitch]