======== 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.)