Modular Arithmetic for the HP-41
Overview
1°) Addition, Subtraction modulo m
2°) Multiplication modulo m
3°) Square modulo m
4°) Power modulo m
5°) Inverse modulo m
6°) Square Root modulo m
Many of these programs result from fruitful e-mails that I exchanged
with Gerald Hillier some time ago.
1°) Addition, Subtraction modulo m
In these 2 short routines - like in all the following ones - one
must perform the calculations so that all the arguments remain < 1010
Data Registers: /
Flags: /
Subroutines: /
| 01 LBL "M+"
02 - 03 ST+ Y 04 X<> L 05 MOD 06 END |
( 15 bytes / SIZE 000 )
| 01 LBL "M-"
02 RDN 03 - 04 R^ 05 MOD 06 END |
( 13 bytes / SIZE 000 )
| STACK | INPUTS | OUTPUTS |
| Z | x | / |
| Y | y | / |
| X | m | x ± y mod m |
| L | / | m |
2°) Multiplication modulo m
Data Registers: /
Flags: /
Subroutines: /
| 01 LBL "M*"
02 STO N 03 RDN 04 STO Z 05 E5 06 MOD 07 ST- Z 08 STO M 09 X<>Y |
10 STO Y
11 LASTX 12 MOD 13 ST- Y 14 ST* T 15 X<> M 16 ST* M 17 X<>Y 18 ST* Z |
19 *
20 RCL N 21 MOD 22 X<>Y 23 LASTX 24 CHS 25 MOD 26 + 27 RCL N |
28 MOD
29 X<>Y 30 LASTX 31 CHS 32 MOD 33 + 34 RCL N 35 MOD 36 RCL M |
37 LASTX
38 CHS 39 MOD 40 + 41 RCL N 42 MOD 43 CLA 44 END |
( 67 bytes / SIZE 000 )
| STACK | INPUTS | OUTPUTS |
| Z | x | / |
| Y | y | / |
| X | m | x y mod m |
| L | / | m |
Example:
1234567899 ENTER^
9876541203 ENTER^
7897897897 XEQ "M*" >>>>
7124235881
3°) Square modulo m
-One can of course use "M*" but the following routine is faster.
Data Registers: /
Flags: /
Subroutines: /
| 01 LBL "SQM"
02 RCL Y 03 E5 04 MOD 05 ST- Z 06 STO T 07 X^2 |
08 X<>Y
09 MOD 10 X<>Y 11 ST* Z 12 ST* X 13 LASTX 14 CHS |
15 MOD
16 ST+ Y 17 X<> L 18 CHS 19 MOD 20 X<>Y 21 LASTX |
22 MOD
23 RCL X 24 LASTX 25 - 26 ST+ Y 27 X<> L 28 CHS |
29 MOD
30 ST+ Y 31 X<> L 32 CHS 33 MOD 34 END |
( 55 bytes / SIZE 000 )
| STACK | INPUTS | OUTPUTS |
| Y | x | / |
| X | m | x2 mod m |
| L | / | m |
Example:
1234567899 ENTER^
7897897897 XEQ "SQM" >>>> 7714853288
4°) Power modulo m
Given a positive integer n, "M^" computes xn
mod m
Data Registers: R00 thru R02: temp
Flags: /
Subroutines: "SQM" "M*"
| 01 LBL "M^"
02 SIGN 03 STO 00 04 RDN 05 STO 02 06 X<>Y 07 STO 01 |
08 GTO 03
09 LBL 01 10 2 11 MOD 12 X#0? 13 GTO 02 14 LASTX |
15 ST/ 02
16 RCL 01 17 R^ 18 XEQ "SQM" 19 STO 01 20 GTO 03 21 LBL 02 |
22 ST- 02
23 RCL 00 24 RCL 01 25 R^ 26 XEQ "M*" 27 STO 00 28 LBL 03 |
29 LASTX
30 RCL 02 31 X#0? 32 GTO 01 33 RCL 00 34 END |
( 54 bytes / SIZE 003 )
| STACK | INPUTS | OUTPUTS |
| Z | x | |
| Y | n | / |
| X | m | xn mod m |
| L | / | m |
Example:
1234567899 ENTER^
12345
ENTER^
7897897897 XEQ "M^" >>>>
3260410960 --- Execution
time = 32s ---
5°) Inverse modulo m
-An element x in Z/mZ doesn't always have a reciprocal x -1
-When x -1 doesn't exist, the HP-41 displays "DATA EROR"
Data Registers: R00 tru R04 are used by "UV"
Flags: /
Subroutine: "UV" ( cf "GCD ,
LCM and Bezout's Identity for the HP-41" )
| 01 LBL "1/M"
02 1 03 XEQ "UV" 04 STO Z 05 FRC 06 X#0? 07 GTO 00 08 RDN 09 FRC 10 X=0? 11 GTO 01 12 LBL 00 13 CLX 14 LN 15 LBL 01 16 CLX 17 RCL 02 18 ABS 19 MOD 20 END |
( 34 bytes / SIZE 005 )
| STACK | INPUTS | OUTPUTS |
| Y | x | / |
| X | m | x -1 mod m |
| L | / | m |
Examples:
1234567899 ENTER^
7897897897 XEQ "1/M" >>>> 1249132933
64529
ENTER^
7897897897 R/S
>>>> "DATA ERROR"
6°) Square Root modulo m
-Given 2 integers a and m, this routine tests all the integers from
m to 1 to find all the solutions to the equation x2
= a mod m
-So, it's only useful for small m-values ( anyway, m < 10001 ).
Data Registers: R00 temp
R01 = x1 ............... Rnn = xn
Flags: /
Subroutines: /
| 01 LBL "SQRTM"
02 STO Z 03 MOD 04 0 05 STO 00 06 LBL 01 07 CLX 08 RCL Z 09 ST* X 10 LASTX 11 MOD 12 X#Y? 13 GTO 02 14 X<> T 15 ISG 00 16 CLX 17 STO IND 00 18 LBL 02 19 DSE Z 20 GTO 01 21 RCL 00 22 E3 23 / 24 X#0? 25 + 26 END |
( 46 bytes / SIZE nnn+1 )
| STACK | INPUTS | OUTPUTS |
| Y | a | / |
| X | m | 1.nnn or 0 |
where 1.nnn
= control number of the solutions
m < 10001
X-output = 0 when there is no solution
Example:
Solve x2 = 41 in Z/128Z
41 ENTER^
128 XEQ "SQRTM" >>>> 1.004
--- Execution time = 33 s ---
{ R01 R02 R03 R04 } = { 115 77
51 13 }
Thus, this equation has 4 solutions: 13 51
77 115 ( In fact, 115 =
-13 and 77 = -51 )
-Since -x is solution when x is a solution, the execution time
can be divided by 2 if we test the x-values from INT((m-1)/2) to 0:
Data Registers: R00 temp
R01 = ± x1 ............... Rnn = ± xn
Flag: F10
Subroutines: /
-Lines 10-26-27 are only useful if a = 0
| 01 LBL "SQRTM"
02 STO Z 03 2 04 / 05 INT 06 X<> Z 07 MOD |
08 0
09 STO 00 10 SF 10 11 LBL 01 12 CLX 13 RCL Z 14 ST* X |
15 LASTX
16 MOD 17 X#Y? 18 GTO 02 19 X<> T 20 ISG 00 21 CLX |
22 STO IND 00
23 LBL 02 24 DSE Z 25 GTO 01 26 FS?C 10 27 GTO 01 28 RCL 00 |
29 E3
30 / 31 X#0? 32 ISG X 33 END |
( 58 bytes / SIZE nnn+1 )
| STACK | INPUTS | OUTPUTS |
| Y | a | / |
| X | m | 1.nnn or 0 |
where 1.nnn
= control number of the solutions
m < 20001
X-output = 0 when there is no solution
Example: Solve x2 = 41 in Z/128Z
41 ENTER^
128 XEQ "SQRTM" >>>> 1.002
--- Execution time = 17s ---
{ R01 R02 } = { 51 13 } which is
to be read { ±51 ±13 }
So the 4 solutions are 51 -51 13 -13