Post Reply 
Solving a Single Congruence Equation
03-10-2019, 12:45 AM (This post was last modified: 03-12-2019 12:13 PM by Albert Chan.)
Post: #14
RE: Solving a Single Congruence Equation
Another way to do inverse is to force even coef., thus easily reduced.
(make sure mul/div factors co-prime to the modulo)

Same example, solve 12345 x ≡ 1 (mod 17789)

12345 x ≡ -5444 x ≡ 1 ≡ -17788 (mod 17789)
1361 x ≡ 4447 (mod 17789)

(12345 - 9*1361) x ≡ 1 - 9*4447 (mod 17789)

96 x ≡ -40022 ≡ -75600 (mod 17789)
2 x ≡ -1575 ≡ 16214 (mod 17789)
x ≡ 8107 (mod 17789)

If N is large, we can solve another, with smaller modulo:
x ≡ (4447 - 17789 k) / 1361 (mod 17789) → 17789 k ≡ 4447 (mod 1361)

96 k ≡ 4447 ≡ 5808 (mod 1361)
2 k ≡ 121 ≡ -1240 (mod 1361)
k ≡ -620 (mod 1361)

x ≡ (4447 - 17789 * -620) / 1361 ≡ 8107 (mod 17789)
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
RE: Solving a Single Congruence Equation - Albert Chan - 03-10-2019 12:45 AM



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