(34S) Solving a Single Congruence Equation
08-04-2015, 06:02 AM (This post was last modified: 06-15-2017 01:20 PM by Gene.)
Post: #1
 Thomas Klemm Senior Member Posts: 1,447 Joined: Dec 2013
(34S) Solving a Single Congruence Equation
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
08-04-2015, 01:59 PM
Post: #2
 rprosperi Senior Member Posts: 3,914 Joined: Dec 2013
RE: (WP-34S) Solving a Single Congruence Equation
(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.

--Bob Prosperi
08-04-2015, 03:29 PM
Post: #3
 Thomas Klemm Senior Member Posts: 1,447 Joined: Dec 2013
RE: (WP-34S) Solving a Single Congruence Equation
(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
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)