Back to index

Miller-Rabin Primality Test for the HP-42S

By Erik Ehrling (Sweden) with a fix by J F Garnier. Any comments or suggestions are very welcome!

This is an implementation of the Miller-Rabin primality test for the HP42S. Given an integer as input it returns whether it s a prime number or a composite of several factors.


Using PRM? is simple, just enter an integer 1 to 999 999 999 999 and run PRM?. Depending on the size of the integer the running time can be anything from a few seconds up to five minutes for a very large primes. The program goes through a number of "rounds" in which the number is tested for primality. If a test fails then all the following rounds are skipped, on the other hand a prime is not claimed a prime until it has passed all rounds. For a small integer one round is sufficient, while larger integers require up to five rounds.

When the test is finished the result (Composite or Prime) will be displayed in the upper area of the LCD and can also be found in the alpha register.

Note that the stack, all numbered registers and user flags are left unaltered by the program. It is therefore possible to run PRM? in the middle of a calculation and then continue after it has run.



Technical notes:

For a good description of the Miller-Rabin algorithm see Menezes et al., "Handbook of Applied Cryptography", p 71 [paragraph 2.143] and p 139f [paragraph 2.4].

Binary files for emulators:
Raw binary: prm.raw  Binary for HP-42X: prm.42x

Revision History:
1.01 - Fixed errors which caused unreliable results for large n. Thanks to J F Garnier for both pointing out and providing the fix for this problem!

Generated by 42s2html - 19 September 2004, 17:21