* PRESENTATION QS consists in several programs, which together are quite general a tool to factorize integers. - T (Java) performs a few simple factorisation attempts, (trial division, pollard rho, look for powers). If nothing works, T produces a set of congruence, following the (simple) quadratic sieve technique. - reduce (Objective Caml), is an optional step that can be used to reduce the number of congruences outputed by T - Gauss (Java), Performs guaussian elimitation and finally yield a factorisation. - zyva (bash shell script) acts as a driver for the previous three programs. Code is not as clean as I would have wished, but it does factorize numbers up to 50 digits in a decent time. USAGE * Basic usage is simply by running T and then Gauss, for instance : % java T 340282366920938463463374607431768211457 > congs.txt % java Gauss < congs.txt 5704689200685129054721 * 59649589127497217 (Some diagnostic messages are not shown) The file congs.txt will hold enough congruence so as to factorize n : % head -3 cong.txt 340282366920938463463374607431768211457 22520 18446744073709565175: 2 2 2 2 17 17 19 31 67 3001 5821 9419 16661 18446744073709609353: 2 2 2 2 13 17 61 223 503 1279 1321 2843 18329 You can also use the shell script 'zyva' to combine the steps : % sh zyva 340282366920938463463374607431768211457 59649589127497217 * 5704689200685129054721 zyva should work even when quadratic sieve does not apply : % sh zyva 3558073483079234201643166342745089 n is a power 59649589127497217 * 59649589127497217 * More advanced usage means using the options to T, which enable some control over the factorisation algorithms used (mostly pollard's method) and sieving parameters. BUILD A Makefile is provided, an Objective Caml compiler is required to compile 'reduce'. If you have none, you still can compile T and Gauss (javac T ; javac Gauss); and combine 'java T' and 'java Gauss' by hand. For Objective Caml, see LICENCE QS is licensed under the terms of a slighty modified Q license, see the LICENSE file.