(32SII) Solving a Single Congruence Equation for the HP 32Sii

[Eddie W. Shore]

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 RTN

[Thomas Klemm]

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

[Thomas Klemm]

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

[Albert Chan]

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]

[Albert Chan]

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)