--- QSIEVE V2.99 --- COPYRIGHT "qsieve" was written by Thorsten Reinecke, (this version 2004-11) The program is copyrighted under the terms of the GNU General Public License. See the file COPYING for more details. WHAT IS QSIEVE? --------------- "qsieve" is a program for factoring numbers up to 110 decimal digits and even more, if the number has "smooth" factors. (Numbers up to 50 digits are factored in a few seconds and 75 digits need less than 1 hour computing time on an ATHLON 1.2 GHz, but this may *strongly* depend on the numbers and the system(s) you use.) On a small network (using some 1.5GHz computers) one should accomplish a factorization of a "hard" 100 digit decimal number in about three days... "qsieve" implements various algorithms to accomplish this goal. First, it takes some trial divisions. If the remaining number is still composite, the Pollard-rho-algorithm and a variation of the Pollard-phi-method is used. Some elliptic curves are tried, too... If the remaining number doesn't pass a strong-pseudo-prime test, it will be split into factors by using a double large prime adaption of the multipolynomial-quadratic-sieve method (MPQS). Also, a fermat-like algorithm has been implemented, but it is only used optionally, because it is not very efficient. Nevertheless "fermat" can save much time, if the number is "constructed" in some special way. It is not the goal to factor every number completely into its prime-factors, so if you want a complete factorization, you sometimes have to call the program with remaining co-factors. Although "qsieve" is *not* using state-of-the-art methods for factoring large numbers, such as the number field sieve or modern (highly optimized) versions of elliptic curves, it has enough power to achieve many factorizations. COMPILING QSIEVE ---------------- "qsieve" is written in C++. If you use gcc (version 3.x or newer) under Linux, you should have no problems to compile it. If you use Windows, you're a bit on your own, but you can install Cygwin (see http://www.cygwin.com/) to compile qsieve or try to get a binary version. The compiled version will run without Cygwin, but you need Cygwin to compile it. In addition to the following instructions you have to enable "DEFINES += -DCYGWIN_COMPAT" in the Makefile. - You need the gmp-library (GNU multiple precision library). Get it and install it, if you don't have already done so. (It can be found at http://www.swox.com/gmp/) Newer versions of GMP have already C++-support. You may need to modify the "gmp.h" header file to allow QSIEVE to use its own I/O-functions. The std::ostream& operator<< declarations must be deactivated; simply replace the following line (near the operator<< declarations) #ifdef __cplusplus by #if defined(__cplusplus) && !defined(USER_GMP_WRAP) and everyone is happy again... For gmp-4.1.2 to gmp-4.1.4 you can also proceed as follows: 1. cp gmp.h gmp.h.orig 2. patch gmp.h < gmp.h.patch - Modify the the qsieve-Makefile: There are now two Makefiles: One in the main directory (for configuring most of the options) and one in the src-directory (which only should be modified by developers). Set the appropriate values for GMP_inc_dir, GMP_lib_dir and CFLAGS. - autodetection (only gnu-compiler) If the "-DAUTODETECTION" option is enabled, the compiler will set appropriate values for most of the following options. - i386, x86-cmov, mmx/3DNow! inline assembler code optimization: inline assembler code is GCC and GAS (GNU assembler) specific. If you your machine doesn't run i386-assembler code, or isn't using GCC and/or GAS you should disable the "-DASM386" flag. - trigger autostart clients: notify parent If you want the server to raise signals to the parent process, you should enable this option. If the server is compiled with this define, it will send "SIGUSR1" when it's ready to accept clients and "SIGUSR2" whenever it finds a new factor. Be aware that you must install a signalhandler if you activate this option!! In bash you may use "trap" to catch signals, eg.: trap "echo catched SIGUSR2" SIGUSR2 - If you have only an older version of gcc, you are on your own (you should probably use an older version of qsieve). The C++-STL for older gcc's is not ISO-conformant. Older gcc are incompatible with my system, so I cannot provide any support... - "-DCONTINUATION_METHOD=0|1|2" For elliptic-curve-method (ecm), phi and fibonacci methods, you can choose between three continuation methods: 0: improved standard continuation 1: fast polynomial evaluation method (using karatsuba) 2: fast polynomial evaluation method (using fast fourier transform) The improved standard continuation should be faster in finding factors up to 25 decimal digits. If you want to factorize large numbers using lots of elliptic curves you may find it useful to switch to fft-continuation. The fft-continuation is asymptotically faster than the improved standard continuation since it takes advantage of fast polynomial evaluation schemes. If you run low on memory or if you want to use qsieve as background-process, it may be better to use improved standard continuation. - Enable/disable programs to compile in the Makefile, eg. PROGRAMS +=server ,if you want to compile a server #PROGRAMS +=server ,if you don't want to compile a server - verbosity of output You can control the verbosity of output by setting various defines. The verbosity can only be defined at compile time and NOT at run time. It is assumed that qsieve is mostly used for long-term runs, so that compiling carries no weight. Moreover, the compiler is given a better chance to optimize the code by removing unwanted verbosity. "-DVERBOSE_WARN" : print warnings "-DVERBOSE_NOTICE" : print (interesting) notices "-DVERBOSE_INFO" : print (additional) infos "-DVERBOSE" : be verbose (many infos) "-DDEBUG" : very verbose + additional debugging code (slow!) - If everything fits, simply type "make" and wait a few seconds... ;) - After compiling, you should have the following programs: - qsieve (standalone-version for your system) - server (online, UNIX and Cygwin) - net-client (online, UNIX and Cygwin only) - file-client (offline client with file-based communication) - transfer-client (interface between file-client and server, UNIX and Cygwin) - If you are a experienced C-programmer, you can also "play" with the source code by altering some parameters (sieve-size, size of factorbase, parameters of some factoring methods). - Hint: First you should take a look to "qsieve.cfg". There you can modify the main sieving parameters. The lines are structured in the following way: digits of number to factor:rho,phi1,phi2,elcu1,elcu2,nrcu,Primbasis_size:Factor_Threshold:M where easy-factor-parameters: - rho : Number of rounds spend in Pollard-rho-algorithm - phi1 : Highest (prime) number for Pollard-phi-(p-1)-algorithm - phi2 : Highest (prime) number for phi-continuation-algorithm - elcu1 : Highest (prime) number for elliptic curves - elcu2 : Highest (prime) number for elliptic curves (continuation) - nrcu : Number of elliptic curves sieving-parameters: - Primbasis_size is the size of the factorbase, - Factor_Threshold is the exponent of the biggest prime in the static factorbase to allow "dynamic factors" to take place in the dynamic factorbase. - M is the sieve-interval for each polynomial. But be careful not to modify the file-structure! - You can specify a different configuration file by setting QSIEVE_CFG in your shell environment. example (bash): export QSIEVE_CFG="~/my_config.qsieve" result: "~/my_config.qsieve" will be used instead of "qsieve.cfg" CREATING REFERENCE MANUALS -------------------------- - You need doxygen to create reference manuals for qsieve. (http://www.stack.nl/~dimitri/doxygen/) - type "make doc" to create a general reference manual (html & latex) - type "make refman-net-client", "make refman-qsieve", "make refman-server" for specialized versions. REQUIREMENTS (for factoring numbers of about 75 digits) ------------------------------------------------------- - you should have at least 32 MB main memory - you need about 200 MB free (temporary) disk space - the larger the number, the more memory you will need for factorization... RUNNING QSIEVE -------------- qsieve - number_to_factor can also be given as a numerical term consisting of digits and the symbols ()^*:/+- and/or FLP, where F stands for Fibonacci number, eg. F12 equals 34, L stands for Lucas number, eg. L12 equals 322, P stands for Partition number, eg. P12 equals 77. Sometimes it may be required to set the term in quotes. Example: qsieve "10^10+2^(2*3+1)*5-1" will be equivalent to qsieve 10000000639 - If no arguments are given, qsieve tries to continue the latest aborted factorization (if data is still stored on disk). - Results are appended to a file called "factorizations.txt". This file will not be deleted by qsieve (but you can do so eventually). RECOVERY (continuation of an aborted factorization) - Simply restart qsieve (or server) without further parameters. - WARNING: If you start a new factorization, the stored data for continuation of an aborted factorization will be destroyed! Starting qsieve with an old number will start a new factorization! DISTRIBUTED SIEVING ------------------- ONLINE (only under UNIX/Linux and Cygwin) - start the server: server - wait until the server is ready for connection of clients (The server will try an easy-factorization and calculate some parameters. This can take some time...) - start the client(s): net-client - The clients will now receive parameters for doing their job. Their memory-usage will be low, so clients are perfect background-processes. The only requirement is an online connection to the server. Server and client may be running on the same host. - Distributed sieving is only effective to factor LARGE numbers. For numbers up to 65 digits you should run the standalone version instead. - It is possible to continue a standalone factorization with the client-server version and vice versa. Simply restart the program without parameters. - If possible, the "dynamic_relations"-file should be located on a ramdisk, because qsieve has to do a lot of seeking on this file. On a slow device this does not only slow down the factorization, but also the responsiveness of the whole system is affected! (Take a look at the config file to see how to specify this.) OFFLINE (server only under UNIX/Linux and Cygwin) - prepare data for client (only under UNIX/Linux and Cygwin) ----------------------------------------------- - start the server: server - start transfer-client: transfer-client -g -f - do the sieving -------------- - copy data () to client-system - start file-client: file-client - transfer data to server (only under UNIX/Linux and Cygwin) ----------------------------------------------- - copy .out to server-system - start transfer-client: transfer-client -p -f .out - delete transfered data KNOWN BUGS: ----------- - sieving is done twice for primes dividing the multiplier of n (but this is considered harmless because filtering this primes out takes probably more time anyway...) TODO-LIST for next releases: ---------------------------- - fix bugs... - improve user interface (XML/XSL/HTML-interface) - add autoconf/configure stuff - improve performance - adding more inline assembler code for time-critical parts, maybe more MMX or 3DNow! code? - Maybe support other hardware? - implement new methods: - number field sieve - Wiedemann-algorithm and/or - lazy evaluation of multi-large-prime-relations - and finally: factor some heavy 150 digit-numbers ;) HOW TO GET QSIEVE? ------------------ Well, you should know already... For further information and latest release see "www.thorstenreinecke.de/" - "www.thorstenreinecke/downloads/" contains latest release and some (German) texts about factorization ACKNOWLEDGEMENTS ---------------- Thanks to Frank Heyder (heyder@heydernet.de), who has implemented some of the tcp-client-server stuff. Thanks to Bernd Edler and Frank Heyder for beta-testing, suggestions for improvements and their help in debugging earlier versions of qsieve. Thanks to Sven Anders for providing hints to improve the webinterface. Thanks to Alexis Michon for contributing patches and writing additional documentation. Special thanks to everybody who had done theoretical work on factorization methods used in qsieve. Without their work, qsieve would not have been possible. Have fun, Thorsten Reinecke e-mail: reinecke@thorstenreinecke.de