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.

Usage:

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.

Examples:

Technical notes:
• The program is implemented using a repeated square-and-multiply algorithm for exponentiation. To handle a * b mod n for large a,b,n the program uses a partial implementation of addition and multiplication of double precision integers which are represented internally as complex numbers.
• Slightly updated wrapper for program encapsulation now also supports complex registers (REGS) when running PRM?
• The variables X_PRM, Y_PRM, Z_PRM, T_PRM, L_PRM, R_PRM are used for storing stack and register contents and should be considered reserved variables

References:

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