mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2016-08-05, 07:41   #1
Romuald
 
Romuald's Avatar
 
Oct 2015
France

32×7 Posts
Default Factoring projects algorithms - What is Aliqueit ?

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.

Last fiddled with by Romuald on 2016-08-05 at 07:44
Romuald is offline   Reply With Quote
Old 2016-08-05, 08:06   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

213448 Posts
Default

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.

Last fiddled with by LaurV on 2016-08-05 at 08:15
LaurV is offline   Reply With Quote
Old 2016-08-05, 20:52   #3
Romuald
 
Romuald's Avatar
 
Oct 2015
France

32×7 Posts
Default

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.

Last fiddled with by Romuald on 2016-08-05 at 20:55
Romuald is offline   Reply With Quote
Old 2016-08-05, 21:25   #4
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

1C1D16 Posts
Default

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.)

Quote:
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.

Last fiddled with by Dubslow on 2016-08-05 at 21:28
Dubslow is offline   Reply With Quote
Old 2016-08-05, 21:47   #5
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

22×3×479 Posts
Default

Quote:
Originally Posted by Dubslow View Post
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.
henryzz is online now   Reply With Quote
Old 2016-08-06, 02:44   #6
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

213448 Posts
Default

Outstanding post Dubslow!


Small observation, however:
Quote:
Originally Posted by Dubslow View Post
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

Last fiddled with by LaurV on 2016-08-06 at 02:53
LaurV is offline   Reply With Quote
Old 2016-08-06, 03:05   #7
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×2,399 Posts
Default

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:
Quote:
It's goal
Damn habit of adding an apostrophe got me in trouble here

Last fiddled with by Dubslow on 2016-08-06 at 03:06
Dubslow is offline   Reply With Quote
Old 2016-08-06, 03:21   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22×7×11×29 Posts
Default

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.

Last fiddled with by LaurV on 2016-08-06 at 03:24
LaurV is offline   Reply With Quote
Old 2016-08-06, 03:29   #9
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×2,399 Posts
Default

Quote:
Originally Posted by LaurV View Post
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)
Dubslow is offline   Reply With Quote
Old 2016-08-06, 08:45   #10
Romuald
 
Romuald's Avatar
 
Oct 2015
France

778 Posts
Default

Quote:
Originally Posted by Dubslow View Post
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.
Romuald is offline   Reply With Quote
Old 2016-08-06, 09:29   #11
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2·3·1,699 Posts
Default

Quote:
Originally Posted by Romuald View Post
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.
xilman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Links to Factoring Projects rogue Factoring 20 2014-11-19 01:08
Implementing Factoring Algorithms Raman Hobbies 45 2009-05-11 05:11
Overview of Factoring Algorithms ThiloHarich Factoring 0 2007-09-02 20:32
design factoring algorithms koders333 Factoring 14 2006-01-25 14:08
factoring algorithms are patented? koders333 Factoring 1 2006-01-19 20:04

All times are UTC. The time now is 09:50.

Fri Nov 27 09:50:41 UTC 2020 up 78 days, 7:01, 4 users, load averages: 1.33, 1.40, 1.24

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.