COPYRIGHT
---------
Copyright (c) 2003
Center for Information Security and Cryptography (CISC)
Department of Computer Science and Information Systems
The University of Hong Kong



INTRODUCTION
------------
This program implements a probabilistic primality test on integers.
The testable range of numbers is (0, 2^2048). The complete source
code in standard C is provided. 



RUNNING THE TEST
----------------

The program primality_test.c shows how to conduct the primality test. 
In the main(), a large number is read from the file "number" and its
primality is then tested. The result is written to the screen. 

The win32 executable of the program is stored in primality_test.exe. 

To test the primality of a different number, just replace the number in the
file "number" and run primality_test.exe. (A re-compilation is needed
if the platform is different from win32.)

To conduct the primality test in an application program, call
	short prime_test( const char str[] , unsigned short base )

str is the char string representing the number being tested and the parameter
'base' is the base of the number.
The function returns 1 if the number is a prime, 0 if not a prime, and -1 if
the number is out of the testable range (0, 2^2048). An example of
the usage can be found in the main() of primality_test.c.  


DOCUMENTARY
-----------
Algorithm P (Probabilistic primality test)
* Described in page 395 section 4.5.4 Factoring into Primes, The Art of 
computer programming volume 2, third edition by Donald E. Knuth.

Let n = 1 + (2^k) q
P1. Let x be a random integer in the range 1 < x < n
P2. Set j <- 0 and y <- (x^q) mod n.
P3. If j = 0 and y = 1, or if y = n - 1, terminate the algorithm and
    say "n is probably prime." If j > 0 and y = 1, go to step P5
P4. Increase j by 1. If j < k, set y <- (y^2) mode n and return to stop P3.
P5. Terminate the algorithm and say that "n is definitely not prime"

The prime_test() of this program applies the above algorithm to test
a number t times. t is computed according to the specification in
IEEE P1363/D8 Annex A.

The following shows the calling sequences of the major functions 
in the program. Macro are quoted in double quote.


rng_prime_test
  |
  | ---> rng_number
  |       |
  |       | ---> rng_sha
  |       | ---> rng_fibon
  |       | ---> rng_congr
  |
  | ---> mpa_compare
  |
  | --- mpa_copy
  |       |
  |       | ---> "ResetErrorCode"
  |       | ---> "CheckPara1"
  |       | ---> "CheckResult1"
  |
  | ---> mpa_mult
  |       |
  |       | ---> "ResetErrorCode"
  |       | ---> "CheckPara1"
  |       | ---> "CheckPara2"
  |       | ---> mpa_suppress_zero
  |       | ---> CheckResult1
  |
  | ---> mpa_divide
  |       |
  |       | ---> "ResetErrorCode"
  |       | ---> "CheckPara1"
  |       | ---> "CheckPara2"
  |       | ---> mpa_compare
  |       | ---> mpa_copy
  |       | ---> mpa_num2str
  |       | ---> mpa_suppress_zero
  |       | ---> mpa_mult
  |       | ---> mpa_add
  |
  | ---> mpa_divide_digit
  |       |
  |       | ---> "ResetErrorCode"
  |       | ---> "CheckPara1"
  |       | ---> "CheckPara2"
  |       | ---> "CheckResult1"
  |       | ---> mpa_compare
  |       | ---> SetError
  |       | ---> mpa_copy
  |       | ---> mpa_mult
  |       | ---> Error
  |
  | ---> mpa_power_mod
          |
          | ---> "ResetErrorCode"
          | ---> "CheckPara1"
          | ---> "CheckPara2"
          | ---> "CheckResult1"
          | ---> SetError
          | ---> mpa_compare
          | ---> mpa_mult
          | ---> mpa_divide



FILES
-----
The following files are included.

primality_test.c	// Primality test
primality_test.exe	// Executable
number				// Contains a number to be tested
README				// This readme file



LINKS
-----
http://www.csis.hku.hk/cisc