--- QSIEVE V2.99.11 --- COPYRIGHT "Qsieve" was written by Thorsten Reinecke, (this version 2005-02) 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 120 decimal digits and even more, if the number has "smooth" factors. (Numbers up to 65 digits are factored in less than 60 seconds; and 84 digits need less than 1 hour computing time on an ATHLON-64 3000+ (32bit mode), but this may *strongly* depend on the numbers and the system(s) you use.) On a small network (using some Athlon and P4 computers) one should accomplish a factorization of a "hard" 107 digit decimal number in less than two days... This version, Qsieve V2.99.11, is a snapshot release, but considered to run stable. It contains minor bugfixes and some new (but also experimental) features. Using Version 2.99 in a small distributed network, a 116-digit number was factorized in about 60 days. V2.99.11 is expected to be much faster. "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 (p-1) and fibonacci (p+-1) is used. Elliptic curves can be tried, too... Several continuations for these methods have been implemented. The most sophisticated one is the fft-continuation (improved standard continuation or fast polynomial evaluation schemes using karatsuba and/or fft can be selected). If the remaining number doesn't pass a strong-pseudo-prime test, it will be split into factors by using a dynamic double large prime adaption of the multipolynomial-quadratic-sieve method (DPPMPQS). 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. Some factorization methods split up compound factors. In these rare cases simply restart Qsieve with these factors. Although "Qsieve" is not (yet) 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. Qsieve also provides a PHP/XML interface to monitor ongoing factorizations. You can setup your own distributed factorization facility using Qsieve! Recently there were some rumors about Qsieve being very slow. Please consider, that Qsieve is a suite of factorization programs and not a single algorithm. Qsieve is optimized for distributed factoring numbers using several dozens clients in a trusted network environment. (Support for untrusted networks is planned.) Qsieve is Open Source Software. If you are a software developer, you are encouraged to contribute suggestions and code. 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. ** However, please activate inline assembler options manually, since cmov, mmx, 3DNow! and SSE/SSE2 will not be activated by using this method! ** - i386, x86-cmov, mmx/3DNow! and SSE/SSE2 inline assembler code optimization: inline assembler code is GCC and GAS (GNU assembler) specific. If your machine doesn't run i386-assembler code or isn't using GCC and/or GAS, you should disable the "-DASM_386" 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!) - "-DSAFEMODE" Protect against various type of errors, forgery, attacks, etc. If the program is running in an untrusted environment (eg. Internet), then defective relations could be sent to the server. This define adds some protection and detection, but it is far from perfect and reduces performance for the sake of integrity. - 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 64 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: ---------------------------- - provide public factorization service and discussion board on www.qsieve.net! - fix bugs... - improve user interface (XML/XSL/HTML-interface) - add autoconf/configure stuff - use stringstreams/internal buffers instead of files - improve performance - adding more inline assembler code for time-critical parts, maybe more MMX/3DNow!/SSE/SSE2 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, providing access to various hardware & software platforms and writing additional documentation. Thanks to Jason Papadopoulos (author of msieve) for discussing ideas how to speed-up MPQS implementations. 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