Threaded Mode | Linear Mode

Thomas Klemm · (This post was last modified: 06-15-2017 01:20 PM by Gene.)

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

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

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