Solving a Single Congruence Equation

[Albert Chan]

(03-08-2019 07:16 PM)Albert Chan Wrote:  Example: solve 12345 x ≡ 1 (mod N), with N = 17789, for x

12345 ≡ -5444 (mod N)

For comparison, this build 17789/5444 continued fraction convergents P/Q

Code:

(next column) = CF * (current column) + (prev column)

CF   3   3   1   2   1   3   1   6    5    2
P 0  1   3  10  13  36  49 183 232 1572 8107 17789
Q 1  0   1   3   4  11  15  56  71  482 2481  5444

Q values are not needed here ...

12345 * 8107 ≡ 1 (mod N), thus x ≡ 1/12345 ≡ 8107 (mod N)

Edit: it might be cheaper to do Q row instead, since Q's < ½ P's

P's = round(Q's * fraction)