Mod Arithm

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 < 10¹⁰

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	x² mod m
L	/	m

Example:

1234567899 ENTER^
7897897897 XEQ "SQM" >>>> 7714853288

4°) Power modulo m

Given a positive integer n, "M^" computes xⁿ 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	xⁿ 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 x² = a mod m
-So, it's only useful for small m-values ( anyway, m < 10001 ).

Data Registers: R00 temp R01 = x₁ ............... Rnn = x_n
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 x² = 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 = ± x₁ ............... Rnn = ± x_n
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 x² = 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

hp41programs

Modular Arithmetic for the HP-41