--- QSIEVE V3.02 --- COPYRIGHT --------- "Qsieve" was written by Thorsten Reinecke, version 3.02 was released 2007-11-07. Copyright 1998-2007 Thorsten Reinecke "Qsieve" is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) version 3. "Qsieve" is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with "Qsieve". If not, see . WHAT IS QSIEVE? --------------- "Qsieve" is a program for factoring numbers up to 120 decimal digits (and even more, if the number has moderate 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.) The main factorization algorithm implemented in Qsieve is a dynamic double large prime adaption of the multiple polynomial quadratic sieve (DPPMPQS). For finding small and moderate factors (and for partial factorization of very large numbers), various additional algorithms are implemented: - trial division - pollard rho - pollard phi (p-1) - fibonacci (p+-1) - elliptic curves Several continuations for these methods are available. The most sophisticated one is the fft-continuation. 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" is a suite of factorization programs and not a single algorithm. "Qsieve" is optimized for distributed factorization using several dozen clients in a trusted network environment. (Support for untrusted networks is planned.) "Qsieve" provides a PHP/XML interface to monitor ongoing factorizations. You can setup your own distributed factorization facility using Qsieve! "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.4.x or newer) under Linux or Cygwin, you should have no problems to compile it. - Software requirements: - GNU multiple precision library, (version 4.0 or above) -> http://gmplib.org/ - a recent C++ compiler (gcc-3.3.x or better) -> http://gcc.gnu.org - For compiling Qsieve under Windows, you need to install Cygwin -> http://www.cygwin.com/ Short version: -------------- Just type "./configure", then type "make && make install" for compiling the binaries. See "./configure --help" for additional options! Long version: ------------- Most problems are handled automatically by the configure script. But you may still be interested how to proceed manually. First of all, start the configure script: "./configure" This configure script produces two makefiles for you. The default makefile is generated by the GNU automake/autoconf tools. The second makefile is a crafted sample makefile for developers that prefer manual customization. Most of the options inside the sample makefile are well documented. - 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) For gmp-4.1.2 to gmp-4.2.2 you can also proceed as follows: 1. cp gmp.h gmp.h.orig 2. patch gmp.h < gmp.h.patch - If you have only an older version of gcc, you are on your own. The C++-STL for older gcc's is not ISO-compliant. - If you want to use the sample makefile: copy Makefile.sample Makefile This makefile contains several options; some of them are described now. Please refer the sample makefile, which is self-explanatory! - i386, x86-cmov, mmx/3DNow! and SSE/SSE2 inline assembler code optimization: inline assembler code is GCC and GAS (GNU assembler) specific. - 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, e.g.: trap "echo caught SIGUSR2" SIGUSR2 - "-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, e.g. 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 (e.g. 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) - validator (program for validating data files) - 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: 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.doxygen.org/) - 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... REQUIREMENTS (for factoring numbers >110 digits, server) -------------------------------------------------------- - you should have at least 1 GB main memory - you need about 2 GB free (temporary) disk space - a fast USB memory stick for the DynamicRelationsFile may improve performance (maximum performance if files are spread amoung drives.) - 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, e.g. F12 equals 34, L stands for Lucas number, e.g. L12 equals 322, P stands for Partition number, e.g. 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) - improve autoconf/configure stuff - improve performance - 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