Factoring projects algorithms - What is Aliqueit ?

[Romuald]

Originally Posted by xilman

Be careful. YAFU does not play well with GPU-enabled ECM.

At least, that's my experience.

What was your software & hardware setup ?

[Dubslow]

Lets examine the steps of a factorization.

1) Search for very small factors. Yafu has all the code for this as part of its codebase. Yafu does this itself.
2) Search for "small" factors, where the meaning depends on the size of the number -- in most cases factors up to ~4/13ths of the number size. This is done via ECM (*and P-1, but that's a distraction for this post, so we'll ignore it).

2a) Yafu doesn't implement ECM itself. The step 1 methods are fairly straightforward methods, nothing beyond high school level (not that Yafu's implementation isn't top tier professional quality). ECM is not so easy. It's less than 50 years old on a theoretical basis, and understanding it requires basically a math major in university at a bare minimum. Implementing an efficient ECM implementation in Yafu would take forever and a day, and is especially pointless since it's already implemented by GMP-ECM. So, in order to run step two, Yafu does nothing more than to coordinate how much ECM to run and the details of how to run it, but at the end of the day it has to call an external GMP-ECM executable to actually run the algorithm. So you need a GMP-ECM executable.

3) If ECM fails to find a sufficiently small factor, Yafu will switch to a sieve method, which will find the factors regardless of their size relative to the number. (One of the things Yafu automates is to decide what "sufficiently small" means.)

3 option a) If the number in question is less than ~95 digits, it will run the Quadratic Sieve. QS is also an advanced algorithm, possibly less so than ECM but still firmly in math major territory. Various implementations exist, but most of Yafu's *original* purpose was for its author to build the very best QS implementation that he could (he implements SIQS, to be specific). He has succeeded to the best of anyone's knowledge here. So YAFU has its own QS implementation, and that is that. No external help needed.

3 option b) Above the QS crossover point, the Number Field Sieve is faster (again, this point varies substantially based on your hardware and software). The Number Field Sieve gets into PhD level math (not that a dedicated undergraduate couldn't learn it, but it requires a substantial time investment). All known NFS implementations to date, with one key exception, were started by mathematicians who wrote NFS software for more research purposes than anything else -- to extend mathematical knowledge, not to break RSA or any monetary or other goal. (Msieve is the major exception -- as far as I know, jasonp is not an active research mathematician and wrote Msieve merely for shiggles, though obviously it takes very incredible mathematical and software engineering skills all the same.) The major extant software today is as follows:

3bI) GGNFS is an old and no longer maintained NFS suite (begun by research mathematicians for research purposes). Its first and third stages are limited and generally considered obsolete at this point, but its middle stage, which is the most computationally involved step in NFS, is still generally considered the best we have; among other things, it features inline x86 ASM for large speed gains on x86 hardware. (Yafu SIQS is also ASM enabled, as is GMP-ECM.)

3bII) msieve was started for shiggles, but as GGNFS started losing momentum and became unmaintained, msieve's first and third stages were its most actively developed and surpassed GGNFS. msieve has a "line sieve" implementation for the middle stage, but on theoretical/non-software-performance grounds, it's simply not competitive with GGNFS' "lattice siever" for speed.

This is the general state of things on this forum. We use Msieve for parts one and three, with old GGNFS code stuck in the middle. factmsieve.py requires external Msieve and GGNFS binaries to perform actual computation. Yafu is able to directly link against Msieve, and so does not require an Msieve executable at run time, but does require an Msieve executable (well, static library) at compile time. GGNFS lattice sievers have and basically will always be a standalone unit, a black box within which few dare meddle, and so Yafu, like factmsieve.py, does require a separate ggnfs-lasieve executable it can call.

[The author of Yafu has expressed interest in building a whole new lattice siever from scratch, but such a thing would be a massive investment of time and energy, even moreso than his QS implementation, and he says he doesn't have the time required in the current state of affairs. There is perhaps one other former member around here who had the mathematical chops to do such a thing, but as I said he's no longer around. (A couple other regulars might be able to do so as well, but they've never expressed any desire or at least drive.)]

3bIII) For completeness I should mention CADO-NFS, which is by far the most actively developed NFS implementation currently. Even Msieve has largely halted development in recent times with jasonp running out of time to put work into it, while CADO is once again created by research mathematicians for whom CADO is part of their work, not spare time like Yafu or Msieve (have I mentioned how incredible they are for being spare time hobbies? Seriously PhD level work being put out by these guys in their spare time.) [CADO is developed by the same group of people who develop GMP-ECM.] CADO is generally considered not competitive with msieve and ggnfs performance-wise, with the possible exception of its first stage; that said, since it is still actively developed, it is probably the future even for people around here, but it will take a while for us to change our ways.


So that's the nitty gritty of why Yafu needs what it does.

_____________________________________________________________________

Now as for actual acquisition:

You don't need to compile anything yourself. Floating around here in various places (I'm not sure exactly where, but somewhere) are precompiled executables of Yafu, GMP-ECM, and GGNFS, which are what you need.

That said, if you really want to compile it yourself, you will require the following, which I think can be largely found in the Yafu documentation:

1) Compile or otherwise obtain the development package for GMP. All modern computational software depends on GMP in some way -- Msieve, Yafu, GMP-ECM (duh), CADO, just about anything really depends on GMP.

2) Compile GMP-ECM or otherwise obtain an executable of it. (Yafu at compilation time doesn't depend on GMP-ECM, it only needs the executable at runtime.)

3) Compile Msieve. Yafu does depend on Msieve at compile time (at least for NFS, as I discussed with LaurV above). Yafu links against Msieve and does not require an Msieve executable (besides the static library, which isn't really an executable).

4) Acquire GGNFS from somewhere around this forum. Seriously, this is the one thing for which there is *absolutely zero* reason to compile it yourself. It is even a time honored tradition on this forum for someone to ask every few months where the latest ggnfs binaries are. (As for the link you mention, yes GGNFS development is dead in the water, on SF or GitHub or anywhere. It is just about dead as dead can be, but you can still find executables floating around here.)

5) Compile Yafu, which includes dependencies on GMP and Msieve, but not GMP-ECM. At runtime, it requires external access to executables of GGNFS and GMP-ECM in order to actually perform computation.

Running Yafu should hopefully be doable by reading the instructions, same as compiling.


Boy, I really wasted a lot of time on this post. At least I'll never have to again.

[Romuald]

Good ;)

That's a lot of informations at a time. Tank you.

But you know, unless a lot of other regular people on this forum I have 21 messages posted throughout this forum, I just discovered all these factoring projects 8 months ago when I was browsing the internet about arithmetic and prime numbers, and since I keep on searching without concluant result.
I'm not mathematician, even less computer scientist, I'm only a french student just about to pass "Baccalauréat" a lot more interested in computer science (linux in particular) and maths than many persons i know.

And I am just trying to understand a little bit more about all this horribly complex blend of thingies.

I hope U can understand that. But I really thought it was easier to understand and implement the "shared knowledge" existing on the web such as these public projects.

I'm going to try your steps (though i had at the moment already started), but damn it, nowadays i find that factorization on sb's own computer is intricate.

Just hearing from you that factmsieve and all its paraphernalia is obselete (i had suspicions in addition), is this page still usable (i only want to follow its compiling instructions)?

[xilman]

Originally Posted by Romuald

What was your software & hardware setup ?

Gentoo Linux, so essentially everything built from source. The only exception is the CUDA set-up which Nvidia distributes only as a binary package.

In particular, msieve, ECM-GMP and ggnfs are all built from recent repository code.

See http://www.mersenneforum.org/showthr...667#post437667 for my discovery that YAFU and GPU-enabled ECM do not play well together and Ben's response. I don't know if Ben has fixed it yet; I'm sure he'll let us know if he has.

Paul

[Dubslow]

That link should be mostly accurate. Not much has changed.

If you do get Yafu working, then factoring is not intricate. The setup is harder than the usage.

[xilman]

Originally Posted by Romuald

Just hearing from you that factmsieve and all its paraphernalia is obselete.

Some of us find it very far from obselete[sic]. We use it every day for non-trivial factorizations. I'm doing a c168 right now, for instance, under the control of factMsieve.pl

[Romuald]

Originally Posted by Dubslow

The setup is harder than the usage.

That is precisely what I mean. By making a full-automated program, why do not include all it needs from beggining?
That question doesn't expect any response.

OK so I'm trying to do all of this:

-GMP and MSIEVE for compiling
-GMP-ECM and GGNFS for executable

But I idn't see any topic giving binaries of GGNFS.
I search tomorrow and in days ahead.

Xilman, what instructions did you follow (if you did) for your factmsieve.pl?

[Dubslow]

Does anybody happen to recall where/what thread the most recent set of Linux GGNFS binaries are? Obviously there is a need for them here.

[xilman]

Originally Posted by Romuald

Xilman, what instructions did you follow (if you did) for your factmsieve.pl?

Use the source Luke.

In the code it's clear how to set up the number of threads, the locations of the sieiving programs, and stuff like that.

Standard usage is trivial. For tidiness sake I tend to run factorizations in a subdirectory of that which holds the msieve code. Put the integer to be factored in a file --- for the sake of example call it foo.n --- and then run ../factMsieve.pl foo.n. It churns for a while as it tries to find a gnfs polynomial. Of course, if you want to run SNFS this is pretty pointless but if you are a complete newbie it does show you the format of a polynomial file, which format you can use for the SNFS poynomial. If you let polynomial finding run to completion factMsieve will continue automagically. If you need to restart factMsieve.pl for whatever reason, including wanting to use a polynomial file found by alternative means, you run ../factMsieve.pl foo.poly

Anything non-trivial --- if I wanted to run in parallel on several machines for instance, or to tweak some of the sieving parameters --- again I'd read the source. It's very rare that I feel the need to do this.

Paul

[Romuald]

... I see.

The main difference between your installation and potentially mine is that I would use the python script (i have the bases of python but i am ignorant of PL/I).

Actually, I have a functional implementation with factmsieve.py, ggnfs, msieve, just following the thread "Build Instructions for Ubuntu 14.04", but whan I want to factorize, doesn't seem to work:

./factmsieve.py example
-> +--------------------------------------------------------------+
-> | Running factmsieve.py, a Python driver for MSIEVE with GGNFS |
-> | sieving support.   It is Copyright, 2010-2013, Brian Gladman |
-> | and is a conversion of factmsieve.pl that is Copyright, 2004 |
-> | Chris Monico.  This is version 0.77, 27th August 2013.       |
-> +--------------------------------------------------------------+
-> This is client 1 of 1
-> Running on 6 Cores with 2 hyper-threads per Core
-> Working with NAME = example
-> Selected default factorization parameters for 100 digit level.
-> Selected lattice siever: gnfs-lasieve4I12e
-> No parameter change detected, resuming... 
-> Running setup ...
-> Estimated minimum relations needed: 4.095e+06
-> resuming a block for q from 1000000 to 1100000
-> Running lattice siever ...
-> entering sieving loop
-> making sieve job for q = 1002719 in 1000000 .. 1008333 as file example.job.T0
-> making sieve job for q = 1011359 in 1008333 .. 1016666 as file example.job.T1
-> making sieve job for q = 1019801 in 1016666 .. 1024999 as file example.job.T2
-> making sieve job for q = 1028089 in 1024999 .. 1033332 as file example.job.T3
-> making sieve job for q = 1036531 in 1033332 .. 1041665 as file example.job.T4
-> making sieve job for q = 1044941 in 1041665 .. 1049998 as file example.job.T5
-> making sieve job for q = 1053467 in 1049998 .. 1058331 as file example.job.T6
-> making sieve job for q = 1061171 in 1058331 .. 1066664 as file example.job.T7
-> making sieve job for q = 1069349 in 1066664 .. 1074997 as file example.job.T8
-> making sieve job for q = 1077799 in 1074997 .. 1083330 as file example.job.T9
-> making sieve job for q = 1086331 in 1083330 .. 1091663 as file example.job.T10
-> making sieve job for q = 1094633 in 1091663 .. 1099996 as file example.job.T11
-> Lattice sieving algebraic q from 1000000 to 1100000.
-> gnfs-lasieve4I12e -k -o example.out.T0 -v -n0 -a example.job.T0
Traceback (most recent call last):
  File "./factmsieve.py", line 2017, in <module>
    run_siever(client_id, num_clients, SV_THREADS, fact_p, lats_p)
  File "./factmsieve.py", line 1648, in run_siever
    procs.append(run_exe(lats_p['siever'], args, wait = False))
  File "./factmsieve.py", line 350, in run_exe
    p = subprocess.Popen([ex] + args.split(' '), **al)
  File "/home/matthias/anaconda3/lib/python3.5/subprocess.py", line 947, in __init__
    restore_signals, start_new_session)
  File "/home/matthias/anaconda3/lib/python3.5/subprocess.py", line 1552, in _execute_child
    raise child_exception_type(err_msg)
subprocess.SubprocessError: Exception occurred in preexec_fn.

I'm not specialist... But As far as I can understand, it seems like there's an error with python... and anaconda.
I don't see why anaconda is causing trouble, I installed it recently to have maths libraries (sympy...).

[Romuald]

Right now, all is ready for YAFU, ecept, of course, ggnfs.
So, I've been looking for binaries on the forum, nothing.

I try to compile it myself:
'make x86_64'

It returns an error occured because of the 'x86_64'.
Tried with 'nocona', failed.

I realize this is particularly annoying to have this stubborn tool unobtainable, by compiling or downloading ready-to-serve binaries, whereas all other tools GMP, GMP-ECM, Msieve, are OK.