The Museum of HP Calculators

# Programmes for Number Theory for the HP-42S

This program is by Gerald Hillier and is used here by permission.

This program is supplied without representation or warranty of any kind. Gerald Hillier and The Museum of HP Calculators therefore assume no responsibility and shall have no liability, consequential or otherwise, of any kind arising from the use of this program material or any part thereof.

## Overview

All input x, y, m are integers.

Programmes using "HD", "SQM" and "PMOD" are correct for input < 500,000,000,000.

The programme "PRI?" requires about 50sec to test the largest numbers it can cope with.

Factorization using "SQFO" may result in rapid success or not…

(Text in typeface Times New Roman.)

 N.B. R´ represents rolldown X‹0? represents X not equal to zero XŠ0? represents X greater than or equal to zero XŠY? represents X greater than or equal to Y

## Listing

```00 { 38-Byte Prgm }
01†LBL "A&T"		Sub-programme of "?SPS".
02 -1
03 RCL 01
04 1
05 -
06 1
07†LBL 00
08 R´
09 2
10 ÷
11 1
12 STO+ ST Z
13 R´
14 ENTER
15 ENTER
16 2
17 MOD
18 X=0?
19 GTO 00
20 R´
21 STO 02
22 R´
23 STO 00
24 END

00 { 111-Byte Prgm }
01†LBL "BEZO"		Input x and y, output v and w
02 COMPLEX			such that
03 STO "X"			               v*x+w*y=GCD( x, y)
04 COMPLEX			Stack diag:
05 1						x	=>	GCD( x, y)
06 3						y		x+i*y
07 DIM "U"							v+i*w
08 DIM "V"
09 INDEX "U"
10 R´
11 R´
12 ¨
13 CLX
14 ¨
15 1
16 ¨
17 R´
18 INDEX "V"
19 ¨
20 1
21 ¨
22 CLX
23 ¨
24†LBL 00
25 INDEX "U"
26 RCL "V"
27 RCL "U"
28 RCLEL
29 RCL÷ ST T
30 IP
31 RCL× ST Z
32 -
33 STO "V"
34 R´
35 STO "U"
36 INDEX "V"
37 RCLEL
38 X‹0?
39 GTO 00
40 CLV "V"
41 INDEX "U"
42 RCLEL
43 RCL "X"
44 J+
45 RCLEL
46 J+
47 RCLEL
48 CLV "U"
49 COMPLEX
50 END

00 { 32-Byte Prgm }
01†LBL "FIB#"		For input n finds nth Fibonacci number.
02 0
03 1
04 1
05†LBL 01
06 R´
07 X<>Y
08 RCL+ ST Y
09 RCL ST Z
10 1
11 -
12 STO ST T
13 X>0?
14 GTO 01
15 RCL ST Z
16 END

00 { 17-Byte Prgm }
01†LBL "GCF"		Finds GCD for input x and y.
02†LBL 01
03 X<>Y
04 RCL ST Y
05 MOD
06 X‹0?
07 GTO 01
08 R´
09 ABS
10 END

00 { 58-Byte Prgm }
01†LBL "HD"			Sub-programme for "HEAD".
02 ENTER
03 ENTER
04 1E6
05 MOD
06 STO 03
07 -
08 STO 04
09 R´
10 1E6
11 MOD
12 STO ST Z
13 -
14 ENTER
15 RCL× 04
16 RCL 01
17 MOD
18 X<>Y
19 RCL× 03
20 RCL 01
21 MOD
22 +
23 RCL 01
24 MOD
25 RCL 04
26 RCL× ST Z
27 RCL 01
28 MOD
29 +
30 RCL 01
31 MOD
32 X<>Y
33 RCL× 03
34 RCL 01
35 MOD
36 +
37 RCL 01
38 MOD
39 END

00 { 17-Byte Prgm }
01†LBL "HEAD"		Input x ,y, m, output x*y mod m.
02 XEQ "XST"
03 XEQ "HD"
04 END

00 { 36-Byte Prgm }
01†LBL "INVM"		Finds multiplicative inverse of x modulo y.
02 XEQ "BEZO"
03 RCL ST Z
04 1
05 X‹Y?
06 GTO 02
07 R´
08 R´
09 COMPLEX
10 R´
11 X<>Y
12 COMPLEX
13 X<>Y
14 R´
15 MOD
16 RTN
17†LBL 02
18 0
19 END

00 { 222-Byte Prgm }
01†LBL "KRON"		Input x, y, output Kronecker symbol for
02 STO 02			(x,y), a generalisation of the Legendre symbol.
03 X<>Y
04 STO 01
05 X<>Y
06 COMPLEX
07 STO "C"
08 RCL 02
09 X=0?
10 GTO 01
11 RCL 01
12 2
13 MOD
14 RCL 02
15 2
16 MOD
17 +
18 X=0?
19 GTO 03
20 1
21 STO 03
22 0
23 STO 04
24†LBL 12
25 RCL 02
26 2
27 MOD
28 X>0?
29 GTO 04
30 0.5
31 STO× 02
32 1
33 STO+ 04
34 GTO 12
35†LBL 04
36 RCL 04
37 2
38 MOD
39 X=0?
40 GTO 05
41 RCL 01
42 8
43 MOD
44 4
45 -
46 ABS
47 1
48 X=Y?
49 GTO 05
50 -1
51 STO× 03
52†LBL 05
53 RCL 02
54 XŠ0?
55 GTO 06
56 ABS
57 STO 02
58 RCL 01
59 XŠ0?
60 GTO 06
61 -1
62 STO× 03
63†LBL 06
64 RCL 01
65 X=0?
66 GTO 07
67 0
68 STO 04
69†LBL 14
70 RCL 01
71 2
72 MOD
73 X‹0?
74 GTO 08
75 0.5
76 STO× 01
77 1
78 STO+ 04
79 GTO 14
80†LBL 08
81 RCL 04
82 2
83 MOD
84 X=0?
85 GTO 09
86 RCL 02
87 8
88 MOD
89 4
90 -
91 ABS
92 1
93 X‹Y?
94 GTO 09
95 -1
96 STO× 03
97†LBL 09
98 RCL 01
99 4
100 MOD
101 RCL 02
102 4
103 MOD
104 ×
105 9
106 X‹Y?
107 GTO 10
108 -1
109 STO× 03
110†LBL 10
111 RCL 01
112 ABS
113 RCL 02
114 RCL ST Y
115 MOD
116 STO 01
117 R´
118 STO 02
119 GTO 06
120†LBL 07
121 RCL 02
122 1
123 X=Y?
124 GTO 11
125 0
126 GTO 02
127†LBL 11
128 RCL 03
129 GTO 02
130†LBL 03
131 0
132 GTO 02
133†LBL 01
134 R´
135 ABS
136 1
137 X‹Y?
138 0
139†LBL 02
140 RCL "C"
141 X<>Y
142 END

00 { 18-Byte Prgm }
01†LBL "PMB"		Input x, y, m, output x^y mod m.
02 XEQ "XST"
03 XEQ "PMOD"
04 END

00 { 58-Byte Prgm }
01†LBL "PMOD"		Sub-programme for "PMB".
02 STO 13
03 R´
04 STO 14
05 1
06 STO 18
07†LBL 00
08 RCL 13
09 X=0?
10 GTO 01
11†LBL 02
12 RCL 13
13 2
14 MOD
15 X‹0?
16 GTO 03
17 2
18 STO÷ 13
19 RCL 14
20 XEQ "SQM"
21 STO 14
22 GTO 02
23†LBL 03
24 STO- 13
25 RCL 18
26 RCL 14
27 XEQ "HD"
28 STO 18
29 GTO 00
30†LBL 01
31 RCL 18
32 END

00 { 109-Byte Prgm }
01†LBL "PO"			Sub-programme for "POL".
02 1
03 STO 02
04†LBL 02
05 2
06 STO 13
07 STO 14
08 0.5
09 STO 15
10†LBL 06
11 0
12 STO 16
13†LBL 03
14 1
15 STO+ 16
16 RCL 14
17 XEQ "SQM"
18 RCL+ 02
19 STO 14
20 RCL- 13
21 RCL 01
22 XEQ "GCF"
23 1
24 X‹Y?
25 GTO 01
26 RCL 15
27 RCL 16
28 X<Y?
29 GTO 03
30 0
31 STO 16
32 2
33 STO× 15
34 RCL 14
35 STO 13
36†LBL 05
37 RCL 14
38 XEQ "SQM"
39 RCL+ 02
40 STO 14
41 1
42 STO+ 16
43 RCL 15
44 RCL 16
45 X<Y?
46 GTO 05
47 GTO 06
48†LBL 01
49 R´
50 RCL 01
51 X‹Y?
52 GTO 04
53 1
54 STO+ 02
55 GTO 02
56†LBL 04
57 R´
58 STO 06
59 TONE 3
60 END

00 { 25-Byte Prgm }
01†LBL "POL"		Tries to factorise input x using
02 XEQ "XST"		Pollard's rho factorisation method.
03 XEQ "PO"
04 RCL 01
05 X<>Y
06 RCL ST Y
07 RCL÷ ST Y
08 COMPLEX
09 END

00 { 35-Byte Prgm }
01†LBL "PREP"		For input x finds largest prime number
02 IP				smaller than x.
03 ENTER
04 ENTER
05 2
06 MOD
07 -
08 1
09 +
10 ENTER
11†LBL 01
12 R´
13 2
14 -
15 ENTER
16 XEQ "?PRI"
17 X=0?
18 GTO 01
19 R´
20 END

00 { 47-Byte Prgm }
01†LBL "?PRI"		Tests input x for primality. If prime 1,
02 XEQ "XST"		if composite 0.
03 XEQ "SMAF"
04 X=0?
05 GTO 01
06 RCL 01
07 11467
08 X>Y?
09 GTO 02
10 R´
11 XEQ "RABM"
12 GTO 01
13†LBL 02
14 1
15†LBL 01
16 RCL 01
17 X<>Y
18 END

00 { 35-Byte Prgm }
01†LBL "PRNX"		For input x finds smallest prime number
02 IP				greater than x.
03 ENTER
04 ENTER
05 2
06 MOD
07 +
08 1
09 -
10 ENTER
11†LBL 01
12 R´
13 2
14 +
15 ENTER
16 XEQ "?PRI"
17 X=0?
18 GTO 01
19 R´
20 END

00 { 26-Byte Prgm }
01†LBL "RABM"		Rabin's compositeness test to a random
02 ENTER			base. If composite 0, else 1.
03 ENTER
04 4
05 -
06 RAN
07 ×
08 IP
09 2
10 +
11 XEQ "?SPS"
12 END

00 { 39-Byte Prgm }
01†LBL "RND"		Produces a large random number.
02 RAN
03 707000
04 ×
05 IP
06 RAN
07 707000
08 ×
09 IP
10 ENTER
11 ENTER
12 2
13 MOD
14 +
15 1
16 +
17 ×
18 END

00 { 63-Byte Prgm }
01†LBL "SMAF"		Sub- programme, finds a small factor ( < 107).
02 RCL 01
03 3
04 X=Y?
05 GTO 03
06 1
07 -
08 STO 06
09 X=Y?
10 GTO 03
11 MOD
12 X=0?
13 RTN
14 RCL 01
15 SQRT
16 IP
17 107
18 XŠY?
19 X<>Y
20 1E3
21 ÷
22 3.00002
23 +
24 STO 06
25†LBL 02
26 RCL 01
27 RCL 06
28 IP
29 MOD
30 X=0?
31 RTN
32 ISG 06
33 GTO 02
34†LBL 03
35 1
36 END

00 { 39-Byte Prgm }
01†LBL "SPLIT"		Attempts to factorise input x into two
02 XEQ "XST"		parts, output
03 XEQ "SMAF"				g+i*h
04 X=0?				g and h the factors.
05 GTO 01
06 XEQ "PO"
07†LBL 01
08 RCL 06
09 IP
10 RCL 01
11 X<>Y
12 RCL ST Y
13 RCL÷ ST Y
14 COMPLEX
15 END

00 { 77-Byte Prgm }
01†LBL "SPS"		Sub-programme for "?SPS"
02 RCL 15
03 RCL 02
04 XEQ "PMOD"
05 STO 19
06 1
07 X=Y?
08 GTO 01
09 +
10 RCL 01
11 X=Y?
12 GTO 01
13 RCL 00
14 X=0?
15 GTO 04
16 1E3
17 ÷
18 1
19 +
20 STO 16
21†LBL 02
22 RCL 19
23 XEQ "SQM"
24 STO 19
25 -1
26 RCL+ 01
27 X=Y?
28 GTO 01
29 R´
30 1
31 X=Y?
32 GTO 04
33 ISG 16
34 GTO 02
35†LBL 04
36 0
37 RTN
38†LBL 01
39 1
40 END

00 { 27-Byte Prgm }
01†LBL "?SPS"		Tests input x for strong pseudo-primality to
02 STO 15			input base y. If yes 1, else 0.
03 R´
04 XEQ "XST"
05 XEQ "A&T"
06 XEQ "SPS"
07 RCL 01
08 X<>Y
09 END

00 { 193-Byte Prgm }
01†LBL "SQFO"		Attempts to factorise integer input, returns
02 STO 00			one factor if successful. This should be
03 ENTER			checked, as occasional false results occur.
04 SQRT				Should factorisation not succeed or the queue
05 IP				of rejectees stored in "QL" become too long, try
06 STO 01			factoring a small multiple of factoree, say 3*, 5*,
07 STO 02			7*…. And remove the small factor from the
08 X^2				result.
09 -				Generally much faster than programme "PO".
10 STO 03
11 X=0?
12 GTO 00
13 1
14 X=Y?
15 GTO 01
16 40
17 1
18 DIM "QL"
19 INDEX "QL"
20 SF 00
21 1
22 STO 07
23 8
24 RCL× 02
25 SQRT
26 IP
27 STO 05
28†LBL 03
29 FC?C 00
30 SF 00
31 RCL 02
32 ENTER
33 RCL+ 01
34 RCL 03
35 MOD
36 -
37 STO 01
38 RCL 00
39 X<>Y
40 X^2
41 -
42 RCL÷ 03
43 STO 03
44 ENTER
45 SQRT
46 IP
47 STO 06
48 FS? 00
49 GTO 04
50 X^2
51 X‹Y?
52 GTO 04
53 RCL 06
54 [FIND]	*****Hidden command to find an element in the indexed array. If
55 GTO 04		present, does next line & returns position as ROW and
56 GTO 05		COLUMN (via RCLIJ), else no stack change & skip next line.
57†LBL 04		Enter as:
58 RCL 05 				XEQ"[FIND]"
59 RCL 03
60 X>Y?
61 GTO 03
62 ENTER
63 ENTER
64 -2
65 MOD
66 2
67 +
68 ÷
69 RCL 07
70 1
71 STOIJ
72 RCL ST Z
73 STOEL
74 1
75 STO+ 07
76 GTO 03
77†LBL 05
78 RCL 02
79 RCL- 01
80 ENTER
81 ENTER
82 RCL 06
83 MOD
84 -
85 RCL+ 01
86 ENTER
87†LBL 07
88 R´
89 STO 01
90 RCL 00
91 X<>Y
92 X^2
93 -
94 RCL÷ 06
95 STO 06
96 RCL 02
97 ENTER
98 RCL+ 01
99 RCL ST Z
100 MOD
101 -
102 RCL 01
103 X‹Y?
104 GTO 07
105 RCL 06
106 ENTER
107 ENTER
108 -2
109 MOD
110 2
111 +
112 ÷
113 GTO 02
114†LBL 00
115 RCL 01
116 GTO 02
117†LBL 01
118 2
119 RCL× 00
120 XEQ "SQFO"
121†LBL 02
122 TONE 5
123 END

00 { 42-Byte Prgm }
01†LBL "SQM"		For input x and m calculates
02 ENTER					x^2 mod m.
03 ENTER
04 1E6
05 MOD
06 X<>Y
07 RCL- ST Y
08 ENTER
09 X^2
10 RCL 01
11 MOD
12 X<>Y
13 RCL× ST Z
14 RCL 01
15 MOD
16 ENTER
17 +
18 RCL 01
19 MOD
20 +
21 RCL 01
22 MOD
23 X<>Y
24 X^2
25 RCL 01
26 MOD
27 +
28 RCL 01
29 MOD
30 END

00 { 9-Byte Prgm }
01†LBL "XST"		Sub-programme.
02 STO 01
03 R´
04 END

```