Post Reply 
Solving a Single Congruence Equation
03-08-2019, 07:16 PM (This post was last modified: 03-11-2019 02:58 PM by Albert Chan.)
Post: #11
RE: Solving a Single Congruence Equation
Getting to the "2nd best" convergents might be messy, we can do guesses.
You get to the same result even if the guesses were off.

Example: With modulo N=17789, solve 12345 x ≡ 1

12345 ≡ -5444

N/5444 ≈ 3.2676 ≈ 13/4, 13*(12345 x ≡ 1) → (384 x ≡ 13)

N/384 ≈ 46.3255 ≈ 139/3, 139*(384 x ≡ 13) → (9 x ≡ 1807)

N/9 ≈ 1976.5555 ≈ 3953/2, 3953*(9 x ≡ 1807) → (-x ≡ 9682) → (x ≡ 8107)

Warning: make sure guess scaling is co-prime to the modulo.
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-08-2019 07:16 PM



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