HP Forums
(34S) Solving a Single Congruence Equation - Printable Version

+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (34S) Solving a Single Congruence Equation (/thread-4477.html)



(34S) Solving a Single Congruence Equation - Thomas Klemm - 08-04-2015 06:02 AM

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↑
17 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



RE: (WP-34S) Solving a Single Congruence Equation - rprosperi - 08-04-2015 01:59 PM

(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.


RE: (WP-34S) Solving a Single Congruence Equation - Thomas Klemm - 08-04-2015 03:29 PM

(08-04-2015 01:59 PM)rprosperi Wrote:  small typo - in example 1, both should be either 7 or 17.

Thanks for the hint: it's fixed now.

Cheers
Thomas