[DM15/DM15L] Prime check : Miller-Rabin algorithm (with bases)
Posted: Fri Aug 13, 2021 12:55 pm
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
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