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
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