Factoring projects algorithms - What is Aliqueit ?

[Romuald]

Hello,

I've, by the passed, opened 2 threads about factoring because I didn't understand some stuff about ggnfs, msieve, factmsieve, etc. I don't know anything else and all of this still seems not much clear to me.

Today I would like to compile on my PC an efficient tool to factorize numbers.

First I found this but it's old and outdated, moreover explanations are not complete:
http://gilchrist.ca/jeff/factoring/n...ers_guide.html

Then, I tried this http://www.mersenneforum.org/showthread.php?t=19881 but it doesn't seem to work and I still wonder why the links are not the official pages of projects.

So, today I'm abashed about the obvious lack of documentation - my original aim was to work msieve, ggnfs and factmsieve together because I had read somewhere that it was currently the actual best solution to factorize big numbers, above 100 digits.
I've been embarrassed by the different algorithms used in each of these tools.
A clarification on all this would be welcomed.

I get to the point.

I want to follow this
http://starreloaders.com/edhall/AliW...tLinstall.html
for which i can barely understand the title

Edh seems to have offered his link many times over throughout the forum.
But last update was 11 Dec 2012. Is it still up-to-date ?

And what is Aliqueit ? Antix ? Except for that, this tool seems to be exactly what i want because it includes most factoring tools i know.

Thanks for answers.

[LaurV]

Aliqueit is a tool, from a whole series, to factor aliquot sequences, about which you can read more on the wiki. Its strength is not about factoring, but more about organizing/managing those files (a lot of data).

The cmd line program is still actual, better, and faster; the windows interface (aliwin) is more like a wrap around if you don't like the command line thingies.

Aliqueit can be used to factor numbers (if you put them in a convenient way) but to be effective, it will call external tools, like yafu, msieve, ggnfs, ecm, etc.

The program you look for, i.e. factoring, effectively, set it and forget it, is not aliqueit, but yafu. You can use yafu with aliqueit, (command switch -y) to do the job for you, if you work on factoring aliquots; but you can also use yafu independent of aliqueit, to factor this or that number.

yafu includes (i.e. built into it) msieve (poly selection, making distinction between a GNFS and a SNFS poly) and includes the fastest available SIQS algorithms, and P-1/P+1 algorithms, but it will still use external ECM and external NFS sieving, therefore, to use it at its max you need to have GGNFS and GMP-ECM installed. Otherwise yafu will use its internals, which are slower.

yafu does all the trial factoring, pollard rho, p-1, p+1, ecm (with external ecm tool, or with internal one, which is not multithreaded, therefore is slower) and if your number still survives that, it will do either siqs (internal, fast) or snfs/gnfs (external, you need ggnfs installed) depending on the size of your number (or its remaining cofactor). All those thingies inside are implemented "state of the art". You don't need anything else to factor numbers to ~170 digits, beside of patience, and even with any other tools, and a lot of technical knowledge (like in using msieve, you need to know few things, is not for layman's use), you can't get "much" speed up compared with yafu.

[Romuald]

Thank you very much LaurV for this quick reply and explanations.

Indeed, I know YAFU. I downloaded the binaries for Windows and I installed & compiled it (though i don't remember how - I think it was the docs) on my linux.
I'm pretty satisfied of it (simple to use, fast, efficient) but as you said, to be better it needs to call external ECM & NFS i.e. GGNFS & GMP-ECM.

I know by VBCurtis who told me that QS was actually used for small candidates below or equal to 95 digits. Moreover, he also told me that YAFU's implementation was a little bit faster than msieve's.

That is why I want to use msieve, GGNFS and factmsieve.py together, the python script being coordinating the factorisation handling and involving each program for specific tasks.

I understood that all I need to have the best program ever to factorize is only YAFU with GGNFS & GMP-ECM, is that correct? I 've never heard about this assembly of programs working together.

And, in that case, what about the original assortment, with factmsieve.py, GGNFS & msieve?

So, to be precise and not to disgress, do you advise me to keep on using yafu or to use other ones such as factmsieve.py and the rest?
Considering I'm occasionnaly led to factorize big numbers, i.e. above 100 digits.

As I said, I've executed scrupulously this: http://www.mersenneforum.org/showpos...7&postcount=10 and though the good comment about it on the very last message of the thread, I got problems running it as written. Let me know if you want the return of the terminal.

[Dubslow]

msieve and ggnfs are the tools that do actual computation. (msieve does the first and last parts, ggnfs does the middle part which is most computationally intensive.)

Calling msieve and ggnfs directly, by yourself, is quite complicated with a variety of parameters needing to be set to make the whole thing work.

factmsieve.pl was the first time someone said "hey all these calls and parameter setting can be automated, so lets automate it!"

factmsieve.py is the Python translation of the original Perl script. They both equivalently serve as glue -- they are in charge of calling msieve and ggnfs at the right times, in the correct order and with (approximately) correct parameters. Most important to understand is that factmsieve.py only does the Number Field Sieve, NFS.

YAFU came along later. It's goal is to be "all in one": all you need to do is type "factor(number)" and YAFU will do all the rest without human intervention. The biggest thing that factmsieve.py doesn't include is that fact that, given a random large number, you *don't* start with NFS; first you look for small factors, primarily with ECM and P-1, before moving on to a "sieve method" which is independent of the size of the factors; QS is the correct for below ~95 digits (exact crossover depends on hardware and software), while NFS is correct above, but either requires a certain amount of ECM beforehand to make best use of your resources.

YAFU does all that automatically. Not only does it automate NFS exactly the same way factmsieve.py does, but it also does the "searching for small factors" step that is very important for top efficiency and in its own way nearly as complicated as NFS. (And of course YAFU also has the best known QS implementation, and uses QS or NFS as appropriate.)

I understood that all I need to have the best program ever to factorize is only YAFU with GGNFS & GMP-ECM, is that correct?

That is correct. To summarize, msieve and ggnfs are the tools that do the actual computation required for NFS; factmsieve.py is merely a wrapper, a glue, to use the actual tools in an automated way with minimal to no human intervention. yafu is like factmsieve.py, except that it also offers automation of all the stuff that comes before NFS. And in that sense, factmsieve.py is in some way "obsolete", though plenty of people around here still use it.

If you already have YAFU installed and working, then factmsieve.py is redundant and not very useful.

Edit: By the way LaurV, for NFS purposes, yafu does need to link against a separately-built copy of msieve, so in that sense it's not included. For QS purposes that isn't true and msieve is included, but YAFU's main utility these days is automating NFS.

[henryzz]

Originally Posted by Dubslow

factmsieve.pl was the first time someone said "hey all these calls and parameter setting can be automated, so lets automate it!"

For those interested there is a bit more history than that. Factmsieve.pl was an improvement of factlat.pl which used tools that are part of ggnfs in order to postprocess and select a polynomial. These tools had significant limitations as the size of numbers being factored increased and were replaced by msieve.

[LaurV]

Outstanding post Dubslow!


Small observation, however:

Originally Posted by Dubslow

Edit: By the way LaurV, for NFS purposes, yafu does need to link against a separately-built copy of msieve, so in that sense it's not included. For QS purposes that isn't true and msieve is included, but YAFU's main utility these days is automating NFS.

That is not exactly true, there is/was a yafu version* which needs separate access to msieve, but the one I use only needs ecm and ggnfs. I copied yafu folders from one computer to another many times, and never carried msieve folder, in fact I have msieve at home in only one computer, not in the other three, and there is no msieve in the (three) computers at job. I remember this discussion with BB where we requested separate access to msieve with the idea that we may use GPUs for poly selection (which yafu is not aware of, this in fact is its only drawback** against msieve, he is not aware of the existence of GPUs for poly selection), BB did whatever about it, but I didn't follow, because I never had the time/knowledge/guts/whatever to compile yafu, gmpecm, and/or ggnfs by myself, I always used ready-made exes from here around.

--------------
* there were many versions of yafu, one better than the other, they used to include also MPIR, GW-whatever, GMP-ECM, etc.
Edit:
** beside of missing "loops and screws" from the syntax sorry BB, I could not hold myself

[Dubslow]

I mean to compile. Msieve is statically linked into the yafu binary, so you can copy around the binary ad nauseum, but in order to compile yafu with NFS support, you need to have libmsieve.a floating around somewhere on your system.

Edit:

It's goal

Damn habit of adding an apostrophe got me in trouble here

[LaurV]

Oh, I understand now. That was an English problem (my problem, not yours). Sorry.

That is true, you need msieve at compiling time. I don't need to compile for that. As a programmer, I know that.

The msieve tool is included "in the exe", and used for poly selection (first stage of the NFS phase), and for LA (last phase of the NFS phase). You don't need msieve if you have the executable yafu running. At compilation time however, if you want to compile yafu by yourself, you will need msieve libraries, of course!

It would have been very stupid from BB to replicate the source code of msieve inside of yafu, I don't want to think about maintenance of such project when Jason decides to change things in the original msieve. The right way to go in this case is to link against msieve when you compile, and not to include/copy msieve sources there.

From this point of view, Dubslow is totally right.

[Dubslow]

Originally Posted by LaurV

At compilation time however, if you want to compile yafu by yourself, you will need msieve libraries, of course!

Which is not true for QS of course (as I tried to emphasize) For QS postprocessing, BB did indeed hard-copy some old msieve version that hasn't been updated since (but he says it doesn't need to be)

[Romuald]

Originally Posted by Dubslow

If you already have YAFU installed and working, then factmsieve.py is redundant and not very useful.

Voilà qui est clair ;)

Thus perhaps I'm going to drop factmsieve.py and continue to use YAFU.

However, I'm sorry for discussing that point again, but you're telling me YAFU is full automatic, well-done, perfectly built, including all we need, and paradoxically I need GGNFS and GMP-ECM to make it perfect.
What's the next step? What do I have to do with it? Compile it with which params? Idem for GGNFS etc.

I have this morning upgraded GMPlib and GMP-ECM, compiled them, and installed them.
I will do the same thing for GGNFS, but which one shuld I use? The one on GitHub on on SourceForge? I think the one on /radii has fixed some bugs (read that from http://www.mersenneforum.org/showpos...00&postcount=9).

Then I'm going to refer here to compile YAFU with both libraries i compiled as it is written on the readme file.

[xilman]

Originally Posted by Romuald

Voilà qui est clair ;)

Thus perhaps I'm going to drop factmsieve.py and continue to use YAFU.

However, I'm sorry for discussing that point again, but you're telling me YAFU is full automatic, well-done, perfectly built, including all we need, and paradoxically I need GGNFS and GMP-ECM to make it perfect.
What's the next step? What do I have to do with it? Compile it with which params? Idem for GGNFS etc.

I have this morning upgraded GMPlib and GMP-ECM, compiled them, and installed them.
I will do the same thing for GGNFS, but which one shuld I use? The one on GitHub on on SourceForge? I think the one on /radii has fixed some bugs (read that from http://www.mersenneforum.org/showpos...00&postcount=9).

Then I'm going to refer here to compile YAFU with both libraries i compiled as it is written on the readme file.

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

At least, that's my experience.