Tells if large integers (up to about 2E13) are prime.
Uses the Miller test for strong pseudo-primality.



This program tests to see if integers input by the user
are prime or not.  It works for integers up to about 2E13,
using the Miller test for strong psuedo-primality.  

The program uses the included subroutine SuMult, which
multiplies X and Y (mod N) for numbers where X*Y is too
large for the calculator to store without losing the
less-significant digits.  SuMult uses Head's algorithm.

"Miller" requires the list PrimList to contain the first
100 primes or so.  The included program PrimGen will
generate the list of primes up to 521 and store them in
PrimList.

"Miller" works by testing the input "N" to see if it
passes the strong pseudoprime test to base "B",
where B is chosen from the list PrimList of consecutive
primes.  If N fails this test for some B, N is composite
and this is displayed.  If N passes the test for B up to
2(ln(N))^2, then [assuming the Extended Riemann Hypo-
thesis, as do most number theorists], N is prime, and this
is reported.  A display shows the current base B being 
tested and the last B that need be tested.

Note that the program is very conservative, since few
non-primes pass the strong pseudoprime test for any base.
In fact, if N passes the test for only B=2, and N<2047, 
then N is prime.  Here's some more:

If	N < this #   and the program has tested through
				B = this #,
	  2047			2
       1373653			3
      25326001			5
    3215031751			7

...then N is prime and you can halt the program 
(press <ON>,<QUIT>).

Finally, if N is pseudoprime (but not strongly so) to
one of the bases tested, sometimes the program will
find an actual factor.  Also, if N is small, say N<500,
a trial-division program will probably be faster.

Programs written by Prof. Mark Janeba, Dept. of Math,
Willamette Univ, Salem, OR 97301  
(internet: mjaneba@willamette.edu)

Reference:  _Primes and Programming, An Introduction
  to Number Theory with Computing_, by Peter Giblin,
  Cambridge University Press, 1993.