(34S) Solving a Single Congruence Equation

[rprosperi]

(08-04-2015 06:02 AM)Thomas Klemm Wrote:  Problem:

Solve the equation:

\(a\cdot x\equiv b \mod n\)


Algorithm:

With the definition \(d=\left\lfloor\frac{n}{a}\right\rfloor\) iterate the following until \(a{'}\) is 0:

\(
\begin{bmatrix}
0 & 1 \\
1 & -d
\end{bmatrix}\cdot\begin{bmatrix}
p & n \\
q & a
\end{bmatrix}=\begin{bmatrix}
p{'} & n{'} \\
q{'} & a{'}
\end{bmatrix}=\begin{bmatrix}
q & a \\
p-dq & n-da
\end{bmatrix}
\)

Then \(p{'}\equiv a^{-1}\mod n\). Multiply this by b to get the solution.

It's possible to use the same matrix for the result of a multiplication:

\(
\begin{bmatrix}
00 & 01 \\
02 & 03
\end{bmatrix}\cdot\begin{bmatrix}
04 & 05 \\
06 & 07
\end{bmatrix}=\begin{bmatrix}
04 & 05 \\
06 & 07
\end{bmatrix}
\)

Program:

Code:

LBL'SCE'                           ;   a    b    n
STO 05  STO 09                     ;   a    b    n
R↓  STO 08                         ;   a    b
R↓  STO 07                         ;   a
# 000  STO 00  STO 04              ;   0
# 001  STO 01  STO 02  STO 06      ;   1
# 202  SDR 004                     ;   0.0202
# 004  +                           ;   4.0202
                                   ;   
RCL 05  RCL 07                     ;   4.0202    n    a
X=0?  SKIP 010                     ;   4.0202    n    a
/  IP  ±  STO 03                   ;   4.0202    -d
R↓                                 ;   4.0202
FP                                 ;   0.0202
RCL L                              ;   0.0202    4.0202
ENTER↑                             ;   0.0202    4.0202    4.0202
M×                                 ;   4.0202
BACK 013                           ;   4.0202
                                   ;   
RCL 04                             ;   a⁻¹
RCL× 08                            ;   b/a
RCL 09                             ;   b/a    n
MOD                                ;   b/a % n = x
END                                ;   x

Examples:

\(5\cdot x\equiv 3 \mod 17\)

5 ENTER↑
3 ENTER↑
7 XEQ'SCE'

4

\(999,999,999,989\cdot x\equiv 1 \mod 999,999,999,999\)

999,999,999,989 ENTER↑
1 ENTER↑
999,999,999,999 XEQ'SCE'

899,999,999,999

Thomas - FYI, small typo - in example 1, both should be either 7 or 17.