[DM15/DM15L] Prime check : Miller-Rabin algorithm (with bases)

Contributed software for the DM10, DM11, DM12, DM15 and DM16 goes here.

Please prefix the subject of your post with the model of the calculator that your program is for.
Post Reply
Boub65
Posts: 231
Joined: Tue Sep 12, 2017 4:34 pm
Location: Rabat, Morocco

[DM15/DM15L] Prime check : Miller-Rabin algorithm (with bases)

Post by Boub65 »

Here is a DM15/DM15L 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

Usage :
The prime to be checked must be keyed in X register, program (LBL A) output is :
- 1, if number in X is prime
- 0, if number in X is composite
- 9999, if program got an "OVERFLOW" during calcultation

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 DM15/DM15L, 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 19 minutes and 19 seconds @48MHz CPU.
5.027.672.681, the next prime number overflows the algorithm as expected.

In the program, you can also find two interesting routines :
- LBL C that calculates (Z**Y) mod X for big numbers
- LBL D that calculates (Z x Y) mod X for big numbers

Code: Select all

DM15_M1B
04  000000fffff000  00000000000008  0000000000000c  00000000000eae
08  00000000000000  2faf8befbe2280  00000000000000  00000000000000
14  00000000000000  1b2d2d2d2d2d2d  000000000002cd  00000000000000
18  00000000000000  0000000000007f  00000000a00000  00000000000000
cc  00000000000000  0000000000b2c2  f9f9f9f902b2f1  01b2f000b2570e
d0  15ff65fbfc58eb  fd6854c1c1c412  edf0f1c6f1fcf2  55f6dff206ffb6
d4  dff167fbfc58eb  fd6854c1c1c412  edf0f1c6f1fa55  5716ffecfbfcf2
d8  ebfdf2c1c11eec  5605ff67f066c4  65c4640db25307  ff196204ff2d50
dc  525203ff14fffb  fc58ebfd6850c1  c1c413ffedf0f1  c6f1fc5252f1df
e0  f200ffb1dff163  02ff2d50525301  ff12fffbfc58eb  fd6850c1c1c411
e4  ffedf0f1c6f1fc  525310ffecfbfc  f2ebfdf2c1c151  17ff74510962fb
e8  fc58ebfd6850c1  c15263f162c461  c4600cb2f109ff  b2f008ff1719ff
ec  75fbf13718ff75  39f112edf0f1c6  f138c8dff24908  2d3739390618fb
f0  fc58ebfd6837c1  c1c416edf0f1c6  f1ba3918ff75fb  f137380719ff75
f4  fbf137c419ff75  f1492c3738c448  c4470b1410ec2b  30368697350511
f8  1575ef0413e6df  f21470fbfcf2eb  fdf2c1c1360346  fbf13044f243f3
fc  f142f3f241f3f0  f8f2f6f6f145f1  f0f0f0f0c0f511  781075c5f4400a
A: 000000fffff000  B: 000000fffffeae  C: 00000000000eae
S: 00000000000000
M: 395033178ff000  N: 00000000000000  G: 04

Code: Select all

001  LBL A        | 42,21,11
002  STO 0        |    44  0
003  4            |        4
004  x<>y         |       34
005  TEST 5       | 43,30, 5
006  GTO 0        |    22  0
007  TEST 8       | 43,30, 8
008  GTO 1        |    22  1
009  5            |        5
010  .            |       48
011  0            |        0
012  0            |        0
013  0            |        0
014  0            |        0
015  1            |        1
016  STO 5        |    44  5
017  1            |        1
018  6            |        6
019  6            |        6
020  2            |        2
021  8            |        8
022  0            |        0
023  3            |        3
024  STO 1        |    44  1
025  2            |        2
026  3            |        3
027  STO 2        |    44  2
028  1            |        1
029  3            |        3
030  STO 3        |    44  3
031  2            |        2
032  STO 4        |    44  4
033  RCL 0        |    45  0
034  1            |        1
035  -            |       30
036  STO 6        |    44  6
037  LBL 3        | 42,21, 3
038  RCL 6        |    45  6
039  ENTER        |       36
040  ENTER        |       36
041  2            |        2
042  /            |       10
043  INT          |   43  44
044  2            |        2
045  *            |       20
046  -            |       30
047  TEST 0       | 43,30, 0
048  GTO 4        |    22  4
049  2            |        2
050  STO/6        | 44,10, 6
051  GTO 3        |    22  3
052  LBL 4        | 42,21, 4
053  DSE 5        | 42, 5, 5
054  GTO 5        |    22  5
055  GTO 1        |    22  1
056  LBL 5        | 42,21, 5
057  RCL 5        |    45  5
058  STO I        |   44  25
059  RCL (i)      |   45  24
060  RCL 6        |    45  6
061  RCL 0        |    45  0
062  GSB B        |   32  12
063  x=0          |   43  20
064  GTO 0        |    22  0
065  GTO 4        |    22  4
066  LBL B        | 42,21,12
067  STO 7        |    44  7
068  R_down       |       33
069  STO 8        |    44  8
070  R_down       |       33
071  RCL 8        |    45  8
072  RCL 7        |    45  7
073  GSB C        |   32  13
074  STO 9        |    44  9
075  1            |        1
076  TEST 5       | 43,30, 5
077  GTO .9       |    22 .9
078  R_down       |       33
079  RCL 7        |    45  7
080  1            |        1
081  -            |       30
082  TEST 5       | 43,30, 5
083  GTO .9       |    22 .9
084  LBL 7        | 42,21, 7
085  RCL 8        |    45  8
086  RCL 7        |    45  7
087  1            |        1
088  -            |       30
089  TEST 5       | 43,30, 5
090  GTO .8       |    22 .8
091  RCL 9        |    45  9
092  x^2          |   43  11
093  1            |        1
094  EEX          |       26
095  1            |        1
096  0            |        0
097  x<=y         |   43  10
098  GTO 6        |    22  6
099  R_down       |       33
100  ENTER        |       36
101  ENTER        |       36
102  RCL 7        |    45  7
103  STO .8       |    44 .8
104  /            |       10
105  INT          |   43  44
106  RCL .8       |    45 .8
107  *            |       20
108  -            |       30
109  GTO 8        |    22  8
110  LBL 6        | 42,21, 6
111  RCL 9        |    45  9
112  RCL 9        |    45  9
113  RCL 7        |    45  7
114  GSB D        |   32  14
115  LBL 8        | 42,21, 8
116  STO 9        |    44  9
117  2            |        2
118  STO*8        | 44,20, 8
119  RCL 8        |    45  8
120  1            |        1
121  EEX          |       26
122  1            |        1
123  0            |        0
124  x<=y         |   43  10
125  GTO 2        |    22  2
126  1            |        1
127  RCL 9        |    45  9
128  TEST 5       | 43,30, 5
129  GTO .8       |    22 .8
130  RCL 7        |    45  7
131  1            |        1
132  -            |       30
133  TEST 5       | 43,30, 5
134  GTO .9       |    22 .9
135  GTO 7        |    22  7
136  LBL .8       | 42,21,.8
137  0            |        0
138  RTN          |   43  32
139  LBL .9       | 42,21,.9
140  1            |        1
141  RTN          |   43  32
142  LBL C        | 42,21,13
143  STO .0       |    44 .0
144  R_down       |       33
145  STO .1       |    44 .1
146  R_down       |       33
147  STO .2       |    44 .2
148  1            |        1
149  STO .3       |    44 .3
150  RCL .2       |    45 .2
151  ENTER        |       36
152  ENTER        |       36
153  RCL .0       |    45 .0
154  STO .8       |    44 .8
155  /            |       10
156  INT          |   43  44
157  RCL .8       |    45 .8
158  *            |       20
159  -            |       30
160  STO .2       |    44 .2
161  LBL 9        | 42,21, 9
162  RCL .1       |    45 .1
163  TEST 4       | 43,30, 4
164  GTO .7       |    22 .7
165  RCL .1       |    45 .1
166  ENTER        |       36
167  ENTER        |       36
168  2            |        2
169  /            |       10
170  INT          |   43  44
171  2            |        2
172  *            |       20
173  -            |       30
174  x=0          |   43  20
175  GTO .0       |    22 .0
176  RCL .3       |    45 .3
177  RCL .2       |    45 .2
178  *            |       20
179  1            |        1
180  EEX          |       26
181  1            |        1
182  0            |        0
183  x<=y         |   43  10
184  GTO .1       |    22 .1
185  R_down       |       33
186  ENTER        |       36
187  ENTER        |       36
188  RCL .0       |    45 .0
189  STO .8       |    44 .8
190  /            |       10
191  INT          |   43  44
192  RCL .8       |    45 .8
193  *            |       20
194  -            |       30
195  GTO .2       |    22 .2
196  LBL .1       | 42,21,.1
197  RCL .3       |    45 .3
198  RCL .2       |    45 .2
199  RCL .0       |    45 .0
200  GSB D        |   32  14
201  LBL .2       | 42,21,.2
202  STO .3       |    44 .3
203  1            |        1
204  STO-.1       | 44,30,.1
205  LBL .0       | 42,21,.0
206  2            |        2
207  STO/.1       | 44,10,.1
208  RCL .2       |    45 .2
209  RCL .2       |    45 .2
210  *            |       20
211  1            |        1
212  EEX          |       26
213  1            |        1
214  0            |        0
215  x<=y         |   43  10
216  GTO .3       |    22 .3
217  R_down       |       33
218  ENTER        |       36
219  ENTER        |       36
220  RCL .0       |    45 .0
221  STO .8       |    44 .8
222  /            |       10
223  INT          |   43  44
224  RCL .8       |    45 .8
225  *            |       20
226  -            |       30
227  GTO .4       |    22 .4
228  LBL .3       | 42,21,.3
229  RCL .2       |    45 .2
230  RCL .2       |    45 .2
231  RCL .0       |    45 .0
232  GSB D        |   32  14
233  LBL .4       | 42,21,.4
234  STO .2       |    44 .2
235  GTO 9        |    22  9
236  LBL .7       | 42,21,.7
237  RCL .3       |    45 .3
238  RTN          |   43  32
239  LBL D        | 42,21,14
240  STO .4       |    44 .4
241  R_down       |       33
242  STO .5       |    44 .5
243  R_down       |       33
244  STO .6       |    44 .6
245  0            |        0
246  STO .7       |    44 .7
247  LBL .5       | 42,21,.5
248  RCL .6       |    45 .6
249  x=0          |   43  20
250  GTO E        |   22  15
251  ENTER        |       36
252  ENTER        |       36
253  2            |        2
254  /            |       10
255  INT          |   43  44
256  2            |        2
257  *            |       20
258  -            |       30
259  x=0          |   43  20
260  GTO .6       |    22 .6
261  RCL .7       |    45 .7
262  RCL .5       |    45 .5
263  +            |       40
264  1            |        1
265  EEX          |       26
266  1            |        1
267  0            |        0
268  x<=y         |   43  10
269  GTO 2        |    22  2
270  R_down       |       33
271  ENTER        |       36
272  ENTER        |       36
273  RCL .4       |    45 .4
274  STO .8       |    44 .8
275  /            |       10
276  INT          |   43  44
277  RCL .8       |    45 .8
278  *            |       20
279  -            |       30
280  STO .7       |    44 .7
281  1            |        1
282  STO-.6       | 44,30,.6
283  LBL .6       | 42,21,.6
284  2            |        2
285  STO/.6       | 44,10,.6
286  RCL .5       |    45 .5
287  2            |        2
288  *            |       20
289  1            |        1
290  EEX          |       26
291  1            |        1
292  0            |        0
293  x<=y         |   43  10
294  GTO 2        |    22  2
295  R_down       |       33
296  ENTER        |       36
297  ENTER        |       36
298  RCL .4       |    45 .4
299  STO .8       |    44 .8
300  /            |       10
301  INT          |   43  44
302  RCL .8       |    45 .8
303  *            |       20
304  -            |       30
305  STO .5       |    44 .5
306  GTO .5       |    22 .5
307  LBL E        | 42,21,15
308  RCL .7       |    45 .7
309  RTN          |   43  32
310  LBL 0        | 42,21, 0
311  0            |        0
312  RTN          |   43  32
313  LBL 1        | 42,21, 1
314  1            |        1
315  RTN          |   43  32
316  LBL 2        | 42,21, 2
317  9            |        9
318  9            |        9
319  9            |        9
320  9            |        9
321  R/S          |       31
322  RTN          |   43  32
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)
Post Reply