(Comp.sys.handhelds)
Item: 1375 by kskalb at faui1f.informatik.uni-erlangen.de
Author: [Klaus Kalb]
  Subj: HP48: primality testing
  Date: Fri Dec 07 1990 07:56 

This program for the HP48 tests numbers for being prime.
It is written as a user defined function, so you can include
it into algebraics.

Start it with a number (binary or real) in level 1 and it will answer:
 0 if the number is composite
 1 if the number is prime
 2 if it can't do the job 

The last case occurs only if the number is greater than 25*10^9.
Even if this occurs, you can be quite sure that the given number
is a prime, since the numbers that give a 2 on this test and are
composite are very rare --- but they do exist.
(they are indeed so rare that I don't know an example ;-)

This test is fast --- testing a prime near 10^9 will take about 7000 ticks.
This is less then one second --- not so bad for a small machine.

Of course this is accomplished using mcode. You need ASC\-> to get it
into your machine.  [already ASC'd; you don't need to.  -jkh-]

------------------------------------------------------------------------------

MORE ABOUT THE IMPLEMENTATION:

  This program implements the test proposed by Pomerance, Selfridge and
  Wagstaff in _The_Pseudoprimes_to_25*10^9_ in math.comp.35 (1980)

  Some special effort is made to recognize small primes and numbers with
  small factors on an early stage.

  It will recognize all primes below 25*10^9.

  It runs the strong pseudoprime test with the bases 2,3,5,7, so that
  a number passing this test with result 2 is at least a strong pseudoprime
  to these bases.

  There are two subroutines written in mcode:

    BGCD     calculates the greatest common divisor of two binary integers.
             It uses the binary algorithm that can be found in Knuth's
              _The_Art_of_Computer_Programming.

    MILRAB   performs a strong pseudoprime test on the number N in level 2
             to the base B in level 1. It will accept any combination of
             binary integers and reals. The output is 1 if N is a
             strong base-B pseudoprime and 0 if not.

  Both routines perform argument checking and give decent error messages.

[The primality testing function itself is called 'PRIME?'.  -jkh-]

------------------------------------------------------------------------------

DISCLAIMER: (that's one I've found on the net ;-)

     This program makes use of undocumented low-level features of
     the HP48SX calculator, and may or may not cause loss of data,
     excessive battery drainage, and/or damage to the calculator
     hardware.  The Author takes no responsibility whatsoever for 
     any damage caused by the use of this program.

     This software is provided "as is" and WITHOUT ANY EXPRESS OR
     IMPLIED WARRANTIES, including, but not limited to, THE IMPLIED
     WARRANTIES OF MERCHANTABILITY and FITNESS FOR A PARTICULAR PURPOSE.

------------------------------------------------------------------------------
   Klaus Kalb    | mail :  IMMD1 / Martenstr. 3 / W-8520 Erlangen / Germany   
                 | email:  kskalb@immd1.informatik.uni-erlangen.de   
------------------------------------------------------------------------------