WP 34S Programme to solve Cornacchia's equation

[Gerald H]

The programme COR finds integer solutions for x & y given D & P in Cornacchia’s equation
x^2 + D*y^2 = P
P a prime number, D<P, or returns 0 when there is no integer solution.
Input stack level y: D
stack level x: P
Returns stack level y: x
stack level x: y
Cor uses one sub-programme, MSR (see below), to find the square root modulo a prime.
1 LBL 'COR'
2 STO 01
3 √
4 IP
5 STO 11
6 R↓
7 STO 12
8 +/-
9 RCL 01
10 XEQ 'MSR'
11 x=0?
12 RTN
13 RCL 01
14 STO Z
15 RCL- Y
16 x>? Y
17 x<>Y
18 R↓
19 LBL 01
20 RCL 11
21 x≥? Y
22 GTO 02
23 R↓
24 x<>Y
25 RCL Y
26 MOD
27 GTO 01
28 LBL 02
29 R↓
30 STO Y
31 x^2
32 RCL 01
33 x<>Y
34 -
35 RCL/ 12
36 √
37 ENTER
38 FP
39 x≠0?
40 GTO 02
41 R↓
42 RTN
43 LBL 02
44 CLx
45 END

The programme MSR finds the square root modulo a prime or returns 0 if there is none. So for
s^2 = t modulo p
Input stack level y: t
stack level x: p
Returns stack level x: s
MSR uses one sub-programme, KRN (see below), to find the quadratic nature of t relative to p.
1 LBL 'MSR'
2 DECM
3 STO 01
4 MOD
5 STO Y
6 √
7 ENTER
8 FP
9 x≠0?
10 GTO 07
11 R↓
12 RTN
13 LBL 07
14 RCL Z
15 STO 06
16 RCL 01
17 XEQ 'KRN'
18 1
19 +
20 x=0?
21 RTN
22 RCL 01
23 4
24 MOD
25 1
26 -
27 x=0?
28 GTO 08
29 RCL 06
30 RCL 01
31 1
32 +
33 4
34 /
35 RCL 01
36 BASE 10
37 ^MOD
38 DECM
39 RTN
40 LBL 08
41 STO 07
42 RCL 01
43 DSE X
44 LBL 00
45 STO Y
46 2
47 MOD
48 x≠0?
49 GTO 01
50 R↓
51 RCL/ L
52 INC 07
53 GTO 00
54 LBL 01
55 R↓
56 STO 08
57 1
58 STO 09
59 LBL 02
60 1
61 STO+ 09
62 RCL 09
63 RCL 01
64 XEQ 'KRN'
65 1
66 +/-
67 x≠? Y
68 GTO 02
69 RCL 09
70 RCL 08
71 RCL 01
72 BASE 10
73 ^MOD
74 DECM
75 STO 10
76 RCL 07
77 STO 09
78 RCL 06
79 1
80 +/-
81 RCL+ 08
82 2
83 /
84 RCL 01
85 BASE 10
86 ^MOD
87 DECM
88 STO 05
89 RCL 06
90 RCL 01
91 BASE 10
92 *MOD
93 DECM
94 STO Y
95 x<> 05
96 RCL 01
97 BASE 10
98 *MOD
99 DECM
100 LBL 04
101 STO 06
102 1
103 x=? Y
104 GTO 05
105 STO 07
106 R↓
107 LBL 06
108 ENTER
109 ENTER
110 RCL 01
111 BASE 10
112 *MOD
113 DECM
114 1
115 x=? Y
116 GTO 03
117 STO+ 07
118 R↓
119 GTO 06
120 LBL 03
121 RCL 10
122 2
123 RCL 09
124 RCL- 07
125 1
126 -
127 y^x
128 RCL 01
129 BASE 10
130 ^MOD
131 DECM
132 STO 04
133 ENTER
134 ENTER
135 RCL 01
136 BASE 10
137 *MOD
138 DECM
139 STO 10
140 RCL 07
141 STO 09
142 RCL 05
143 RCL 04
144 RCL 01
145 BASE 10
146 *MOD
147 DECM
148 STO 05
149 RCL 06
150 RCL 10
151 RCL 01
152 BASE 10
153 *MOD
154 DECM
155 GTO 04
156 LBL 05
157 RCL 05
158 END

The programme KRN finds the Kronecker symbol, K(a,b), for two integers; K(a,b) is a generalization of the Jacobi symbol, itself a generalization of the Legendre symbol, & for our purposes returns whether the "a” in question is a quadratic residue modulo prime "b”, resulting in 1 for a quadratic residue, -1 for a non residue & 0 if the numbers have a common factor > 1.
Input stack level y: a
stack level x: b
Returns stack level x: 1 or 0 or -1
1 LBL 'KRN'
2 x=0?
3 GTO 00
4 STO 04
5 x<>Y
6 STO 02
7 2
8 MOD
9 x<>Y
10 RCL L
11 MOD
12 +
13 x=0?
14 RTN
15 SIGN
16 STO 03
17 CLx
18 XEQ 01
19 RCL 02
20 x<> 04
21 STO 02
22 x≥0?
23 GTO 03
24 ABS
25 STO 02
26 RCL 04
27 SIGN
28 x=0?
29 INC X
30 STO* 03
31 LBL 03
32 RCL 04
33 x=0?
34 GTO 04
35 CLx
36 XEQ 01
37 RCL 04
38 4
39 MOD
40 RCL 02
41 RCL L
42 MOD
43 *
44 9
45 x=? Y
46 +/-
47 SIGN
48 STO* 03
49 RCL 04
50 ABS
51 ENTER
52 x<> 02
53 x<>Y
54 MOD
55 STO 04
56 GTO 03
57 LBL 01
58 RCL 04
59 2
60 MOD
61 x≠0?
62 GTO 02
63 # 1/2
64 STO* 04
65 RCL+ Z
66 GTO 01
67 LBL 02
68 R↓
69 FP
70 x=0?
71 RTN
72 RCL 02
73 8
74 MOD
75 4
76 -
77 ABS
78 1
79 x=? Y
80 +/-
81 STO* 03
82 RTN
83 LBL 04
84 RCL 02
85 1
86 x≠? Y
87 CLx
88 RCL* 03
89 RTN
90 LBL 00
91 R↓
92 ABS
93 1
94 x≠? Y
95 CLx
96 END


I would be grateful for concrete suggestions for improvements & reports of any defects.

[Gerald H]

Sorry, there were 2 typing errors in the programme KRN.

Line 45 had "≠", corrected to "=" & line 86 had "=" corrected to "≠", these corrections having now been applied to the original post.