Post Reply 
Solving a Single Congruence Equation
03-12-2019, 09:03 PM (This post was last modified: 08-25-2019 03:50 PM by Albert Chan.)
Post: #16
RE: Solving a Single Congruence Equation
(03-12-2019 03:46 AM)Albert Chan Wrote:  List Euclid GCD intermedates, build inverses in reverse order.
Start from last pair, 1 x ≡ 1 (mod 3), scale it up.

There is no need to walk the whole chain.

For x ≡ 1/1223334444 (mod 9988776655), gcd intermediates are even, final inverse is positive.
We can guess where it should end up.

1st entry is -6 (mod 19) → x ≈ |floor(−6/19 * 9988776655)| = 3154350523
2nd entry is 7 (mod 22) → x ≈ |floor(+7/22 * 9988776655)| = 3178247117

Extrapolation from -6 (mod 19) is too much. The big inverse had not converged yet.
So, scale the inverse in steps, each time guaranteed convergence.

\(\frac{1}{|6/19 - 7/22|}\) = 19*22 = 418 > 274, we can safely skip to mod 274 inverses.

1/211 (mod 274) = (-1)4 floor(-6/19 * 274) = -87

Redo previous example, skipping unneeded calculations:

Euclid Inverse(row) (modulo next-row)
1 → 1 ; 3*19=57
3
19 → (-1)^2 floor(1/3 * 22) = 7 ; 22*63=1386
22
63
211 → (-1)^3 floor(7/22 * 274) = -87 ; 274*2677=733498
274
2677
27044
83809
278471 → (-1)^5 floor(-87/274 * 362280) = 115031 ; 362280*1727591 > 6e11
362280
1727591
9000235
10727826
202101103
1223334444 → (-1)^6 floor(115031/362280 * 9988776655) = 3171632349
9988776655

Thus, with only 4 scalings, 1/1223334444 ≡ 3171632349 (mod 9988776655)
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-12-2019 09:03 PM



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