======== PPSIQS Ver 1.1 manual ======== ======== Copyright(C) Satoshi Tomabechi 2001 ======== ======== e-mail address : mint@fa2.so-net.ne.jp ======== PPSIQS is a prime factorization program by method of PPSIQS i.e. the double large primes procedure variation of the self-intializing quadratic sieve. In general, PPSIQS is faster than PPMPQS. * Environment OS : Linux CPU : 80386(with FPU),80486(with FPU),Pentium,Pentium Pro,Pentium II,... ** Usage 1 Execute PPSIQS 2 Input a number to be factored. 3 The result of factorization is written to the file "siqs.log" in current folder. This program is able to factor the numbers up to 120 digits. However the program has not been tested for over 100 digits. ** You can stop sieving and restart sieving many times. It takes many hours to factor the numbers of over 80 digits. You can stop sieving and restart sieving. Stop sieving: Press Ctrl+Pause , then the result of sieving is saved. Restart sieving: Execute PPSIQS and input the same number. If an input number is not as same as previous one, factorization is started from the beginning. ** Factoring many composite numbers you should make a file (e.g. ppsiqs.in) in which compisite numbers are written. execute as follows PPSIQS < ppsiqs.in ** Primality test This program first tests primality of input number by Rabin-Miller method and APR-CL method. After factorization this program tests primality of factors by APR-CL method. ** Input number may be represented by expression. Available operators: + addition low - subtraction | * multiplication | / Euclidean division | priority % remainder | - negation | ! factorial | # primorial | ^ power high Builtin functions gcd(a1,a2,...) number of arguments must be >=2 Kro(p,q) quadratic residue symbol (p/q) cyc(d,N) cyclotomic number i.e \Phi_d(N), \Phi_d is a cyclotomic polynomial. Sometimes the parser does not well for wrong expressions. C++ like comment is admitted. e.g. (10^38-1)/9/11 // this is a comment ** program option The speed of sieving process mainly depends on the size of sieving array (SieveUnit). You can specify the array size by option. PPSIQS n n is one of 32,64,128,256. ( n Kbytes will be used as sieving array) The default value is 128. ** Notice The small factors have to be removed by other methods before using PPSIQS. Beacause about 30-digit factors may easily found by ECM, PPSIQS is espensive for the numbers with such factors. ** References Scott Contini "Factoring integers with the self-initializing quadratic sieve" Masters thesis, University of Georgia,1997 http://www.crypto-world.com Richard Crandall and Carl Pomerance "Prime Numbers A Computational Perspective" Springer Verlag, 2001 In my implementation, 1/a mod p and 2*B_j/a mod p for all j,p are computed at the initializing stage. ** changes Ver 1.1 1. APR-CL test failed for some primes. The routine calculating the absolute least residue was wrong for small numbers. (I thank Jack Brennen and Ronny Edler, who informed me.) 2. check whether the input number is a complete square number. check whether the input number is a power of prime. (I thank Andrey Kulsha, who gave me suggestions.) 3. make it possible to factor the numbers that are less than 10^40 or greater than 10^100. (I thank Alexander Kruppa, who informed me.)