Post Reply 
Solving a Single Congruence Equation
03-09-2019, 02:10 PM (This post was last modified: 03-14-2019 12:42 AM by Albert Chan.)
Post: #13
RE: Solving a Single Congruence Equation
Since we only need 2nd best convergents (to get inverse), we can skip some intermediates.
Build CF coef with rounded of number, not the integer part.

Coefficients are not really continued fraction coefficients, but it is OK
The list is likely shorter, and easily built with calculator FIX-0 mode:

17789/5444 = ; show 3
1/(Ans - Rnd(Ans = ; show 4
1/(Ans - Rnd(Ans = ; show -4
...

Code:
Coef 3 4 -4   5   -7   -5    -2
P 0  1 3 13 -49 -232 1575 -8107 17789

12345 * 8107 ≡ 1 (mod 17789)
x ≡ 1/12345 ≡ 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-09-2019 02:10 PM



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