YAFU with GNFS support

[bsquared]

I know that there are several utilities out there which enable GNFS factorizations using msieve and ggnfs, but in keeping with my program's name, I've just created yet another.

I just committed code updates which incorporate a completely automated, resumable, multi-threaded, GNFS implementation by using msieve library functions and external ggnfs lattice sievers. SNFS factorizations are also supported, but these are not 100% automated. See the docfile for details.

Right now this is only available for linux, although I hope windows isn't far behind (just need time to put the pieces together). I've updated the gcc build instructions in the readme file... basically you just need a current msieve build (producing libmsieve.a) and ggnfs lasieve binaries. Then just add NFS=1 to the make command. Let me know if anyone has problems building.

This is very much a work in progress. But everything appears to work with the minimal amount of testing I've done - if something doesn't work out of the box, let me know.

linkage:
http://sourceforge.net/projects/yafu/

[CRGreathouse]

I gave it a shot, but no luck yet. It gave an error with -lmsieve, so I decided to recompile msieve in case that was a problem. It wouldn't compile -- it gave an ecm error. I tried to compile ecm, then, and it failed because I upgraded GMP to version 5. I hacked the files to solve the problem, but then I saw that the latest version fixed the problem so I upgraded, compiled, and installed. Then I downloaded the latest msieve and compiled it similarly.

That didn't help, so I saw that the Makefile assumes that msieve is at ../msieve/, which isn't true on my system. So I changed the Makefile, which replaced that problem with a whole slew of unefined basic GMP references; not sure what's up with that, considering that I have a dozen GMP-using programs here.

Sample errors:

gmp_ecm.c:(.text+0x68): undefined reference to `__gmpz_tdiv_qr'
gmp_ecm.c:(.text+0x7b): undefined reference to `__gmpz_clear'
gmp_ecm.c:(.text+0x88): undefined reference to `__gmpz_clear'
. . .
root_sieve_deg6_line.c:(.text+0xa15): undefined reference to `__gmpz_tdiv_ui'
root_sieve_deg6_line.c:(.text+0xa2f): undefined reference to `__gmpz_fdiv_ui'
root_sieve_deg6_line.c:(.text+0xa45): undefined reference to `__gmpz_fdiv_ui'

[bsquared]

Originally Posted by CRGreathouse

I gave it a shot, but no luck yet. It gave an error with -lmsieve, so I decided to recompile msieve in case that was a problem. It wouldn't compile -- it gave an ecm error. I tried to compile ecm, then, and it failed because I upgraded GMP to version 5. I hacked the files to solve the problem, but then I saw that the latest version fixed the problem so I upgraded, compiled, and installed. Then I downloaded the latest msieve and compiled it similarly.

That didn't help, so I saw that the Makefile assumes that msieve is at ../msieve/, which isn't true on my system. So I changed the Makefile, which replaced that problem with a whole slew of unefined basic GMP references; not sure what's up with that, considering that I have a dozen GMP-using programs here.

Sample errors:

gmp_ecm.c:(.text+0x68): undefined reference to `__gmpz_tdiv_qr'
gmp_ecm.c:(.text+0x7b): undefined reference to `__gmpz_clear'
gmp_ecm.c:(.text+0x88): undefined reference to `__gmpz_clear'
. . .
root_sieve_deg6_line.c:(.text+0xa15): undefined reference to `__gmpz_tdiv_ui'
root_sieve_deg6_line.c:(.text+0xa2f): undefined reference to `__gmpz_fdiv_ui'
root_sieve_deg6_line.c:(.text+0xa45): undefined reference to `__gmpz_fdiv_ui'

Are you West Coast? You must have been up late, regardless!

Try building yafu with both GMPECM=1 and NFS=1 specified. I got build errors similar to your sample when I omitted GMPECM=1. My default action is to include it, so I never tested what would happen without it. I'll edit the makefile and documentation to protect against this.

Thanks,
- ben.

[bsquared]

I just committed changes to enable building with MSVC. Win32 binaries are also now available.

Brian, I rearranged the filters a bit in the yafu projects, and added a few files. I believe the build.vc10 solution is ok since I was able to build Win32 binaries with it. But I won't be able to try a x64 build for another 12hrs or so.

[Brian Gladman]

Hi Ben,

The x64 build fails at the moment with undefined symbols:

1>nfs.obj : error LNK2001: unresolved external symbol nfs_filter_relations
1>nfs.obj : error LNK2001: unresolved external symbol nfs_find_factors
1>nfs.obj : error LNK2001: unresolved external symbol nfs_solve_linear_system
1>nfs.obj : error LNK2001: unresolved external symbol factor_gnfs
1>winsupport.obj : error LNK2001: unresolved external symbol mp_divrem
1>winsupport.obj : error LNK2001: unresolved external symbol savefile_init
1>winsupport.obj : error LNK2001: unresolved external symbol mp_gcd
1>winsupport.obj : error LNK2001: unresolved external symbol mp_bits
1>winsupport.obj : error LNK2001: unresolved external symbol savefile_free
1>winsupport.obj : error LNK2001: unresolved external symbol mp_is_prime

Brian

[bsquared]

Thanks Brian.

I see now that I didn't modify the x64 project properties with the additional dependencies needed...
Additional dependencies should be:
..\..\..\msieve\build.vc10\x64\Release\gnfs.lib;..\..\..\msieve\build.vc10\x64\Release\common.lib

And, not sure if this is needed or not, but I added it to the Win32 project properties under Linker->General->Additional Library Directories:
..\..\..\msieve\build.vc10\Win32\Release\

[Brian Gladman]

Hi Ben,

I just found the issues and put them right. I've updated the x64 Windows binaries accordingly.

Brian

[bsquared]

@ Brian: Great, thanks!

Unfortunately I've now done some more testing with the windows binaries (at least, the Win32 ones) and found something that's broken.

When adding free relations during filtering, a whole bunch of lines of the form

16776289,0:

are added to the data file.

Things proceed through finding cycles and building the matrix just fine, but the matrix solve fails with a bunch of these messages:

Wed Dec 29 11:38:51 2010  commencing Lanczos iteration
Wed Dec 29 11:38:51 2010  memory use: 20.7 MB
Wed Dec 29 11:38:51 2010  lanczos error: submatrix is not invertible
Wed Dec 29 11:38:51 2010  lanczos halted after 3 iterations (dim = 127)
Wed Dec 29 11:38:51 2010  linear algebra failed; retrying...

Apparently the bogus lines added during filtering are hosing the matrix. This only happens with windows builds... I'll see if I can find out what's going on. Jason, any ideas?

[edit]
Are those lines actually the free relations? I guess I never knew what they actually looked like. If they aren't bogus, then something else is going wrong.

[axn]

Originally Posted by bsquared

When adding free relations during filtering, a whole bunch of lines of the form

16776289,0:

are added to the data file.

Those _are_ the free relations.

[bsquared]

Originally Posted by axn

Those _are_ the free relations.

I just realized that... see the above edit.

[bsquared]

Originally Posted by bsquared

I'll see if I can find out what's going on...

It appears there is a problem with my local msieve build which is related to mpir. This isn't my normal windows development platform, so the mpir library I'm using is suspect.

So, I think the windows code as is should produce binaries which work, but I'm unable to test this for another 6-7 hours until I get a chance to build everything at home.

If in the meantime anyone else builds windows binaries and finds that they work, let me know.