ppsiqs11.txt

这是一个比较流行的大数分解的工具

========  PPSIQS Ver 1.1 manual                             ========
========  Copyright(C) Satoshi Tomabechi 2001               ========
========             e-mail address : [e-mail] ========

  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     : Windows 95
           Windows 98
           Windows NT4.0
           Windows 2000 

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