� >Lucas1
:
=� Primality checking of integers (2^p)-1, via Lucas' test
(*� This determines the Mersenne primes.
2:
<,� NB Lucas test requires p%>2 and prime.
F?� Doing arithmetic below using 32-bit words requires p%<16.
PB� This renders algorithm suitable only for 5 trivial cases ...
Z>� 3,5,7,11,13 - it therefore has no practical application,
d9� however it does demonstrate the prinicpals involved
n?� via showing (2^p)-1 is prime for 3,5,7,13 but not for 11.
x:
�;� For practical applications need own routine to handle
�>� very large integer arithmetic - suggest a custom routine
�8� to perform the (l*l-2) mod k combined calculation.
�:
��
�8 � "Enter prime p% {2<p%<16, ie 3,5,7,11 or 13} ";p%
�B � "Checking primality of (2^";p%;")-1, via Lucas' test . . ."
� :
� k%=(1<<p%)-1
� l%=4 : � l(0)
� � q%=1 � p%-2
�  l%=(l%*l%-2)�k% : � l(q%)
� �

 :

 � if l(p%-2)=0 ...


 � l%=0 �

"  � �k%;" is prime"'

, �

6  � �k%;" is not prime"'

@ �

J� �
�

00000000  0d 00 0a 0d f4 20 3e 4c  75 63 61 73 31 0d 00 14  |..... >Lucas1...|
00000010  05 3a 0d 00 1e 3d f4 20  50 72 69 6d 61 6c 69 74  |.:...=. Primalit|
00000020  79 20 63 68 65 63 6b 69  6e 67 20 6f 66 20 69 6e  |y checking of in|
00000030  74 65 67 65 72 73 20 28  32 5e 70 29 2d 31 2c 20  |tegers (2^p)-1, |
00000040  76 69 61 20 4c 75 63 61  73 27 20 74 65 73 74 0d  |via Lucas' test.|
00000050  00 28 2a f4 20 54 68 69  73 20 64 65 74 65 72 6d  |.(*. This determ|
00000060  69 6e 65 73 20 74 68 65  20 4d 65 72 73 65 6e 6e  |ines the Mersenn|
00000070  65 20 70 72 69 6d 65 73  2e 0d 00 32 05 3a 0d 00  |e primes...2.:..|
00000080  3c 2c f4 20 4e 42 20 4c  75 63 61 73 20 74 65 73  |<,. NB Lucas tes|
00000090  74 20 72 65 71 75 69 72  65 73 20 70 25 3e 32 20  |t requires p%>2 |
000000a0  61 6e 64 20 70 72 69 6d  65 2e 0d 00 46 3f f4 20  |and prime...F?. |
000000b0  44 6f 69 6e 67 20 61 72  69 74 68 6d 65 74 69 63  |Doing arithmetic|
000000c0  20 62 65 6c 6f 77 20 75  73 69 6e 67 20 33 32 2d  | below using 32-|
000000d0  62 69 74 20 77 6f 72 64  73 20 72 65 71 75 69 72  |bit words requir|
000000e0  65 73 20 70 25 3c 31 36  2e 0d 00 50 42 f4 20 54  |es p%<16...PB. T|
000000f0  68 69 73 20 72 65 6e 64  65 72 73 20 61 6c 67 6f  |his renders algo|
00000100  72 69 74 68 6d 20 73 75  69 74 61 62 6c 65 20 6f  |rithm suitable o|
00000110  6e 6c 79 20 66 6f 72 20  35 20 74 72 69 76 69 61  |nly for 5 trivia|
00000120  6c 20 63 61 73 65 73 20  2e 2e 2e 0d 00 5a 3e f4  |l cases .....Z>.|
00000130  20 33 2c 35 2c 37 2c 31  31 2c 31 33 20 2d 20 69  | 3,5,7,11,13 - i|
00000140  74 20 74 68 65 72 65 66  6f 72 65 20 68 61 73 20  |t therefore has |
00000150  6e 6f 20 70 72 61 63 74  69 63 61 6c 20 61 70 70  |no practical app|
00000160  6c 69 63 61 74 69 6f 6e  2c 0d 00 64 39 f4 20 68  |lication,..d9. h|
00000170  6f 77 65 76 65 72 20 69  74 20 64 6f 65 73 20 64  |owever it does d|
00000180  65 6d 6f 6e 73 74 72 61  74 65 20 74 68 65 20 70  |emonstrate the p|
00000190  72 69 6e 69 63 70 61 6c  73 20 69 6e 76 6f 6c 76  |rinicpals involv|
000001a0  65 64 0d 00 6e 3f f4 20  76 69 61 20 73 68 6f 77  |ed..n?. via show|
000001b0  69 6e 67 20 28 32 5e 70  29 2d 31 20 69 73 20 70  |ing (2^p)-1 is p|
000001c0  72 69 6d 65 20 66 6f 72  20 33 2c 35 2c 37 2c 31  |rime for 3,5,7,1|
000001d0  33 20 62 75 74 20 6e 6f  74 20 66 6f 72 20 31 31  |3 but not for 11|
000001e0  2e 0d 00 78 05 3a 0d 00  82 3b f4 20 46 6f 72 20  |...x.:...;. For |
000001f0  70 72 61 63 74 69 63 61  6c 20 61 70 70 6c 69 63  |practical applic|
00000200  61 74 69 6f 6e 73 20 6e  65 65 64 20 6f 77 6e 20  |ations need own |
00000210  72 6f 75 74 69 6e 65 20  74 6f 20 68 61 6e 64 6c  |routine to handl|
00000220  65 0d 00 8c 3e f4 20 76  65 72 79 20 6c 61 72 67  |e...>. very larg|
00000230  65 20 69 6e 74 65 67 65  72 20 61 72 69 74 68 6d  |e integer arithm|
00000240  65 74 69 63 20 2d 20 73  75 67 67 65 73 74 20 61  |etic - suggest a|
00000250  20 63 75 73 74 6f 6d 20  72 6f 75 74 69 6e 65 0d  | custom routine.|
00000260  00 96 38 f4 20 74 6f 20  70 65 72 66 6f 72 6d 20  |..8. to perform |
00000270  74 68 65 20 28 6c 2a 6c  2d 32 29 20 6d 6f 64 20  |the (l*l-2) mod |
00000280  6b 20 63 6f 6d 62 69 6e  65 64 20 63 61 6c 63 75  |k combined calcu|
00000290  6c 61 74 69 6f 6e 2e 0d  00 a0 05 3a 0d 00 aa 05  |lation.....:....|
000002a0  f5 0d 00 b4 38 20 e8 20  22 45 6e 74 65 72 20 70  |....8 . "Enter p|
000002b0  72 69 6d 65 20 70 25 20  7b 32 3c 70 25 3c 31 36  |rime p% {2<p%<16|
000002c0  2c 20 69 65 20 33 2c 35  2c 37 2c 31 31 20 6f 72  |, ie 3,5,7,11 or|
000002d0  20 31 33 7d 20 22 3b 70  25 0d 00 be 42 20 f1 20  | 13} ";p%...B . |
000002e0  22 43 68 65 63 6b 69 6e  67 20 70 72 69 6d 61 6c  |"Checking primal|
000002f0  69 74 79 20 6f 66 20 28  32 5e 22 3b 70 25 3b 22  |ity of (2^";p%;"|
00000300  29 2d 31 2c 20 76 69 61  20 4c 75 63 61 73 27 20  |)-1, via Lucas' |
00000310  74 65 73 74 20 2e 20 2e  20 2e 22 0d 00 c8 06 20  |test . . .".... |
00000320  3a 0d 00 d2 11 20 6b 25  3d 28 31 3c 3c 70 25 29  |:.... k%=(1<<p%)|
00000330  2d 31 0d 00 dc 12 20 6c  25 3d 34 20 3a 20 f4 20  |-1.... l%=4 : . |
00000340  6c 28 30 29 0d 00 e6 12  20 e3 20 71 25 3d 31 20  |l(0).... . q%=1 |
00000350  b8 20 70 25 2d 32 0d 00  f0 1f 20 20 6c 25 3d 28  |. p%-2....  l%=(|
00000360  6c 25 2a 6c 25 2d 32 29  83 6b 25 20 3a 20 f4 20  |l%*l%-2).k% : . |
00000370  6c 28 71 25 29 0d 00 fa  06 20 ed 0d 01 04 06 20  |l(q%).... ..... |
00000380  3a 0d 01 0e 17 20 f4 20  69 66 20 6c 28 70 25 2d  |:.... . if l(p%-|
00000390  32 29 3d 30 20 2e 2e 2e  0d 01 18 0d 20 e7 20 6c  |2)=0 ....... . l|
000003a0  25 3d 30 20 8c 0d 01 22  18 20 20 f1 20 c3 6b 25  |%=0 ...".  . .k%|
000003b0  3b 22 20 69 73 20 70 72  69 6d 65 22 27 0d 01 2c  |;" is prime"'..,|
000003c0  06 20 cc 0d 01 36 1c 20  20 f1 20 c3 6b 25 3b 22  |. ...6.  . .k%;"|
000003d0  20 69 73 20 6e 6f 74 20  70 72 69 6d 65 22 27 0d  | is not prime"'.|
000003e0  01 40 06 20 cd 0d 01 4a  07 fd 20 a3 0d ff        |.@. ...J.. ...|
000003ee