+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (32SII) Solving a Single Congruence Equation for the HP 32Sii (/thread-447.html)
(32SII) Solving a Single Congruence Equation for the HP 32Sii - Eddie W. Shore - 01-16-2014 03:16 AM
The program solves for x in the equation:
A * x = B mod N
Examples:
4 * x = 6 mod 7
A = 4, B = 6, N = 7
Solution: 5
5 * x = 3 mod 17
A = 5, B = 3, N = 17
Solution: 4
11 * x = 3 mod 16
A = 11, B = 3, N = 16
Solution: 9
Main Routine: Label C
Subroutines: D, E
No pre-storing any variables required. If there is no solution, an error is produced.
To Run: XEQ C
Code:
C01 LBL C
C02 INPUT A
C03 INPUT B
C04 INPUT N
C05 1
C06 STO I
D01 LBL D
D02 RCL I
D03 RCL × A
D04 RCL - B
D05 RCL ÷ N
D06 FP
D07 x ≠ 0?
D08 GTO E
D09 RCL I
D010 RTN
E01 LBL E
E02 1
E03 STO + I
E04 RCL I
E05 RCL N
E06 x > y?
E07 GTO D
E08 0
E09 1/x
E10 RTNRE: Solving a Single Congruence Equation for the HP 32Sii - Thomas Klemm - 01-16-2014 05:58 AM
Instead of brute force the Chinese remainder theorem could be used. This program for the HP-11C can easily be translated to the HP-32Sii or most other HP calculators.
001 LBL A
002 STO 1
003 STO 5
004 R↓
005 STO 6
006 R↓
007 STO 2
008 0
009 STO 3
010 1
011 STO 4
012 LBL 0
013 RCL 1
014 RCL 2
015 /
016 INT
017 STO 0
018 RCL 3
019 RCL 4
020 STO 3
021 RCL 0
022 *
023 -
024 STO 4
025 RCL 1
026 RCL 2
027 STO 1
028 RCL 0
029 *
030 -
031 STO 2
032 X≠0
033 GTO 0
034 RCL 5
035 RCL 3
036 X<0
037 +
038 RCL 6
039 *
040 ENTER
041 ENTER
042 RCL 5
043 /
044 INT
045 RCL 5
046 *
047 -
048 RTN
Usage:
A ENTER
B ENTER
N
GSB A
Example:
5 * x = 3 mod 17
5 ENTER
3 ENTER
17
GSB A
4
Restriction:
gcd(A, N) = 1
RE: Solving a Single Congruence Equation for the HP 32Sii - Thomas Klemm - 01-17-2014 09:04 PM
This is the correspoding Python code:
Code:
def solve(a, b, n):
p, q, m = 0, 1, n
while a != 0:
d = n // a
p, q = q, p - d*q
n, a = a, n - d*a
x = p * b % m
return x if x > 0 else x + m
print(solve(5, 3, 17))Visualize Execution
Now how cool is that? Imagine you write the program for your calculator and view the stack and registers? Single-step forward and back through the program?
Cheers
Thomas
RE: (32SII) Solving a Single Congruence Equation for the HP 32Sii - Albert Chan - 03-06-2019 04:50 AM
This version handle cases when a (mod n) has no inverse
Code:
def LC(a,b,n):
'if a x = b (mod n), solve for x'
p, q, m = 0, 1, n
while a != 0:
d = n // a
p, q = q, p-d*q
n, a = a, n-d*a
d = b // n
m = abs(m//n)
return (p * d % m, m) if b == d*n else ()>>> LC(5, 3, 17) # 1 solution
(4, 17)
>>> LC(123,320,777) # no solution
()
>>> LC(123,321,777) # 3 solutions (mod 777)
(110, 259)
>>> [ 123*x % 777 for x in range(110,777,259)]
[321, 321, 321]
RE: (32SII) Solving a Single Congruence Equation for the HP 32Sii - Albert Chan - 03-10-2019 07:41 PM
With post #4 LC(), for solving A x ≡ B (mod N), we can do Simultaneuous Linear Congruence
Code:
def SLC(eqn1, eqn2):
'Simultaneous Linear Congreuence Solver'
try:
(x1, m1), (x2, m2) = eqn1, eqn2
(x3, m3) = LC(m1, x2-x1, m2)
except ValueError: return () # no solution
x3 = x1 + m1 * x3
m3 = m1 * m3
return (x3 % m3, m3)Example: x≡3 (mod 7) AND x≡105 (mod 143) AND x≡27 (mod 312) AND x≡248 (mod 715)
>>> reduce(SLC, [(3,7), (105, 143), (27, 312), (248, 715)])
(35283, 120120)
>>> # Second congruence is covered by the fourth, and safe to eliminate
...
>>> reduce(SLC, [(3,7), (27, 312), (248, 715)])
(35283, 120120)