mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2013-02-26, 17:38   #12
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13·257 Posts
Default

Quote:
Originally Posted by Dubslow View Post
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.
bsquared is offline   Reply With Quote
Old 2013-02-27, 03:16   #13
Mr. Odd
 
Mar 2010

3716 Posts
Default

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!
Mr. Odd is offline   Reply With Quote
Old 2013-02-27, 20:05   #14
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13×257 Posts
Default

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!
bsquared is offline   Reply With Quote
Old 2013-02-28, 13:17   #15
WraithX
 
WraithX's Avatar
 
Mar 2006

23·59 Posts
Default

Quote:
Originally Posted by bsquared View Post
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:
Code:
 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!
WraithX is offline   Reply With Quote
Old 2013-02-28, 14:02   #16
Mr. Odd
 
Mar 2010

5·11 Posts
Default

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

13×257 Posts
Default

Quote:
Originally Posted by Mr. Odd View Post
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).

Last fiddled with by bsquared on 2013-02-28 at 15:00 Reason: 'y'
bsquared is offline   Reply With Quote
Old 2013-03-01, 03:42   #18
swellman
 
swellman's Avatar
 
Jun 2012

23×192 Posts
Default

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.
swellman is online now   Reply With Quote
Old 2013-03-01, 05:02   #19
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13·257 Posts
Default

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.
bsquared is offline   Reply With Quote
Old 2013-03-01, 06:22   #20
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22×23×97 Posts
Default

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...
LaurV is offline   Reply With Quote
Old 2013-03-01, 08:22   #21
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

112438 Posts
Default

Quote:
Originally Posted by LaurV View Post
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
ET_ is offline   Reply With Quote
Old 2013-03-01, 11:21   #22
swellman
 
swellman's Avatar
 
Jun 2012

23×192 Posts
Default

Quote:
Originally Posted by LaurV View Post
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]
swellman is online now   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 02:57.

Tue Nov 24 02:57:17 UTC 2020 up 75 days, 8 mins, 4 users, load averages: 3.02, 2.99, 2.97

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.