Factorizing with MSIEVE, GGNFS & Factmsieve.py

[VBCurtis]

For candidates smaller than 90-95 digits (the exact cutoff can be determined by using the -tune parameter in YAFU, which tests your actual machine/environment to see where the optimal swtichover is), the quadratic sieve is used by both msieve and YAFU. Yafu's implementation is a bit faster than msieve's.

For candidates above the cutoff, GNFS is used for numbers without any special form. The first step in that process is polynomial selection, which produces much screen output.

[Romuald]

Yes, I had installed Python on Windows and on Ubuntu, by default.

For candidates smaller than 90-95 digits (the exact cutoff can be determined by using the -tune parameter in YAFU, which tests your actual machine/environment to see where the optimal swtichover is), the quadratic sieve is used by both msieve and YAFU. Yafu's implementation is a bit faster than msieve's.

For candidates above the cutoff, GNFS is used for numbers without any special form. The first step in that process is polynomial selection, which produces much screen output.

I don't understand. So MSIEVE with GGNFS and Factmsieve.py have to be used for more than 95 digits and YAFU for less than 95 ?

What is the -tune parameter in YAFU ? I tried and it gives me almost the same thing than without the option. And xhat is the cutoff ?

[swellman]

Originally Posted by Romuald

Yes, I had installed Python on Windows and on Ubuntu, by default.

I don't understand. So MSIEVE with GGNFS and Factmsieve.py have to be used for more than 95 digits and YAFU for less than 95 ?

What is the -tune parameter in YAFU ? I tried and it gives me almost the same thing than without the option. And xhat is the cutoff ?

Yafu can do all size composites. And the parameter is "-tune()". It factors a series of numbers of increasing size on your local machine using both QS and NFS, and determines the length at which NFS is the most efficient choice. Yafu then writes this value into the Yafu.ini file for later reference. This can prove useful if one frequently uses the "factor(n)" command, with n being the composite to be factored.

There is much more information in the Yafu subforum.

[VBCurtis]

Originally Posted by Romuald

Yes, I had installed Python on Windows and on Ubuntu, by default.

I don't understand. So MSIEVE with GGNFS and Factmsieve.py have to be used for more than 95 digits and YAFU for less than 95 ?

What is the -tune parameter in YAFU ? I tried and it gives me almost the same thing than without the option. And xhat is the cutoff ?

You asked what algorithm is used. I explained the quadratic sieve is the algorithm used for small numbers (below roughly 95 digits), while the number field sieve is used for candidates above 95 digits.

YAFU and msieve and GGNFS are software packages, not algorithms. YAFU has the quadratic sieve algorithm built-in, and needs to call nothing else for composites small enough for QS to work. Msieve also has the QS implemented built-in, so msieve can also be used without any other software to run the quadratic sieve.

For numbers bigger than the QS can handle, the GGNFS siever must be used (this is NFS). This may be called by YAFU, or by the python script factmsieve.py. Either one will call msieve to do the first step (polynomial selection), GGNFS for the second step (sieving), and msieve for the 3rd step (solving the matrix and finding the sqrt). You may think of YAFU and factmsieve.py as two options to achieve the same result (calling the proper other programs to do large factorizations).

[Romuald]

Originally Posted by VBCurtis

You asked what algorithm is used. I explained the quadratic sieve is the algorithm used for small numbers (below roughly 95 digits), while the number field sieve is used for candidates above 95 digits.

YAFU and msieve and GGNFS are software packages, not algorithms. YAFU has the quadratic sieve algorithm built-in, and needs to call nothing else for composites small enough for QS to work. Msieve also has the QS implemented built-in, so msieve can also be used without any other software to run the quadratic sieve.

For numbers bigger than the QS can handle, the GGNFS siever must be used (this is NFS). This may be called by YAFU, or by the python script factmsieve.py. Either one will call msieve to do the first step (polynomial selection), GGNFS for the second step (sieving), and msieve for the 3rd step (solving the matrix and finding the sqrt). You may think of YAFU and factmsieve.py as two options to achieve the same result (calling the proper other programs to do large factorizations).

You're telling me MSIEVE and YAFU have both the QS algorithm implemented in. So, when I use YAFU to factorize a 25 digits number by example, it will give me the solution very fast because QS is very efficient alone for less than 95. OK, I understand.
But when I use the factmsieve.py, you say it will call first msieve. So why doesn't find it the solution instantly as YAFU does ? Both contain the QS all the same ?

By the way, is there any posts or any instructions to build and run YAFU on Linux, I searched on the forum, without any conclusive outcome.

If you know some documents about GGNFS, MSIEVE, YAFU and factmsieve.py, and the algorithms they use, please tell me, I didn't found any detailed documentation about it on the internet, neither english nor french.

[VBCurtis]

factmsieve.py is a routine for doing NFS algorithm. It does call msieve, but it tells msieve specifically "do the first stage of NFS for me, please." The python script is NOT used for small factorizations.

[Romuald]

That's a clear fact.

[EdH]

Originally Posted by Romuald

...
By the way, is there any posts or any instructions to build and run YAFU on Linux, I searched on the forum, without any conclusive outcome.
...

I offered a link...

[LaurV]

Originally Posted by VBCurtis

factmsieve.py is a routine for doing NFS algorithm. It does call msieve, but it tells msieve specifically "do the first stage of NFS for me, please." The python script is NOT used for small factorizations.

To add to it, when you use yafu to factor a 25 digit number, there are very high chances that it doesn't reach the SIQS stage, 99.9% of such composites succumb much-much faster, at earlier stages (TF, P-1, P+1, Pollard-Rho, ECM, other tricks yafu does). To see what QS does, try 80-90 digits composites.

Also, to correct, yafu does not "call" msieve, in the sense that it has internal copies of msieve code (libraries) and it does not need external copy of msieve to work. However, yafu needs external copies of GGNFS to work (it won't do NFS without it!), which is called when sieving step is done during NFS algorithm. Also, if you do ECM for large composites, yafu can use external ECM tools - but doesn't need them, the internal ECM implementation is slower because is single-threaded, but it can handle very well al kind of numbers. However, for fast, multithreaded ECM (i.e. use all cores of your CPU) an external tool like GMP-ECM can be used.

All this discussion could be avoided if the OP could read the readme files comming with the two tools (this is polite version of RTFM )

[Romuald]

Also, to correct, yafu does not "call" msieve

I said no such thing.

, in the sense that it has internal copies of msieve code (libraries) and it does not need external copy of msieve to work

VBCurtis was saying the same.

All this discussion could be avoided if the OP could read the readme files comming with the two tools (this is polite version of RTFM

If everybody think as you think, we wouldn't even need forums to chat, exchange and solve problems of each.

The problem is, as i said (but maybe did you not read ? ;) ), that french documentation is not plentiful. So, I look to english websites or forum like mersenneforum.org to talk to people which usually does that kind of work. And the readme files are not explaining how to build and use the programe, and some informations/instructions aren't written anywhere except for some on this forum. That's the case about building instructions of msieve and ggnfs on Ubuntu. But nobody answered me: is it up-to-date ? The script gets sources from other sites than the official (factmsieve).
So, presumably all of you don't know a lot of sites that might help me and make me do not ask some of my questions, so I searched and I found some documents about Integer Factorization:

http://www.connellybarnes.com/documents/factoring.pdf
http://cr.yp.to/2006-aws/notes-20060309.pdf
http://www.cs.columbia.edu/~rjaiswal...ing-survey.pdf

and some others...

So, next time, admittedly, I'm going to investigate by myself before asking, and I'm sorry if I caused some trouble.
But I'm afraid I have to tell you my question was legitimate because there is nearly no internet's page talking about msieve on Ubuntu.

[Dubslow]

For what it's worth, il y a des personnes sur ce forum qui parlent français.