Prime check : Miller Rabin primality test (with bases)

Post Reply
Boub65
Posts: 231
Joined: Tue Sep 12, 2017 4:34 pm
Location: Rabat, Morocco

Prime check : Miller Rabin primality test (with bases)

Post by Boub65 »

Here is a DM41X program that checks if X register is a (big) prime number using the Miller-Rabin algorithm with a set of bases.
The algorithm works up to 5 EEX 09.

More on the Miller-Rabin primality test here : https://en.wikipedia.org/wiki/Miller%E2 ... ality_test

The program uses the following base : a = 2, 13, 23, and 1.662.803 the primality test is DETERMINISTIC up to 1.122.004.669.633 (> 1E10 the calculator limit on integers)

On the DM41X, the largest prime number that can be tested is in fact 5 EEX 09 = 1 EEX 10 / 2 due to a x2 operation that overflows.

4.938.271.579, is the biggest prime number that passes the test in 2 minutes and 03 seconds @80MHz CPU on USB.
5.027.672.681, the next prime number overflows the algorithm as expected.

In the program, you can also find two interesting routines :
- POW that calculates (Z**Y) mod X for big numbers
- AXB%MOD that calculates (Z x Y) mod X for big numbers

MillRab.raw
(500 Bytes) Downloaded 244 times

Code: Select all

LBL "MILLRAB"  ; Key: 11
STO 00
4
X<>Y
X=Y?
GTO 00
X<Y?
GTO 01
5.00001
STO 09
1662803
STO 01
23
STO 02
13
STO 03
2
STO 04
RCL 00
1
-
STO 10
LBL 03
RCL 10
2
MOD
X#0?
GTO 04
2
ST/ 10
GTO 03
LBL 04
DSE 09
GTO 05
GTO 01
LBL 05
RCL IND 09
RCL 10
RCL 00
XEQ "RBTEST"
X=0?
GTO 00
GTO 04
LBL 00
"NOT PRIME"
0
BEEP
RTN
LBL 01
"PRIME"
1
BEEP
RTN
LBL "RBTEST"
STO 11
RDN
STO 12
RDN
RCL 12
RCL 11
XEQ "POW"
STO 13
1
X=Y?
GTO 95
RDN
RCL 11
1
-
X=Y?
GTO 95
LBL 07
RCL 12
RCL 11
1
-
X=Y?
GTO 94
RCL 13
X^2
1 E10
X<=Y?
GTO 06
RDN
RCL 11
MOD
GTO 08
LBL 06
RCL 13
RCL 13
RCL 11
XEQ "AXB%MOD"
LBL 08
STO 13
2
ST* 12
RCL 12
1 E10
X<=Y?
GTO "OVFLOW"
1
RCL 13
X=Y?
GTO 94
RCL 11
1
-
X=Y?
GTO 95
GTO 07
LBL 94
0
RTN
LBL 95
1
RTN
LBL "POW"  ; Key: 12
STO 14
RDN
STO 15
RDN
STO 16
1
STO 17
RCL 16
RCL 14
MOD
STO 16
LBL 10
RCL 15
X<=0?
GTO 96
RCL 15
2
MOD
X=0?
GTO 11
RCL 17
RCL 16
*
1 E10
X<=Y?
GTO 12
RDN
RCL 14
MOD
GTO 13
LBL 12
RCL 17
RCL 16
RCL 14
XEQ "AXB%MOD"
LBL 13
STO 17
1
ST- 15
LBL 11
2
ST/ 15
RCL 16
RCL 16
*
1 E10
X<=Y?
GTO 14
RDN
RCL 14
MOD
GTO 15
LBL 14
RCL 16
RCL 16
RCL 14
XEQ "AXB%MOD"
LBL 15
STO 16
GTO 10
LBL 96
RCL 17
RTN
LBL "AXB%MOD"
STO 18
RDN
STO 19
RDN
STO 20
0
STO 21
LBL 20
RCL 20
X=0?
GTO 97
2
MOD
X=0?
GTO 21
RCL 21
RCL 19
+
1 E10
X<=Y?
GTO "OVFLOW"
RDN
RCL 18
MOD
STO 21
1
ST- 20
LBL 21
2
STO/ 20
RCL 19
2
*
1 E10
X<=Y?
GTO "OVFLOW"
RDN
RCL 18
MOD
STO 19
GTO 20
LBL 97
RCL 21
RTN
LBL "OVFLOW"
"OVERFLOW"
X<>Y
BEEP
STOP
END 
Sincèrement, Sincerely, 73,
Boubker

DM15L, DM41L, DM42 #00855 (domes upgraded), DM41X #00707
HP48SX (with dark screen), HP42s, HP32SII (1990 with fraction bug), HP41C/CV
TI-89 titanium, CASIO fx-cg50 and Numworks (to play with micropython)
User avatar
Walter
Posts: 3070
Joined: Tue May 02, 2017 11:13 am
Location: On a mission close to DRS, Germany

Re: Prime check : Miller Rabin primality test (with bases)

Post by Walter »

This test is hard-wired in the WP43S. Feel free to check PRIME?. Just FYI.
WP43 SN00000, 34S, and 31S for obvious reasons; HP-35, 45, ..., 35S, 15CE, DM16L S/N# 00093, DM42β SN:00041
Post Reply