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
 Albert Chan Senior Member Posts: 1,894 Joined: Jul 2018
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)
 « Next Oldest | Next Newest »

 Messages In This Thread Solving a Single Congruence Equation - Eddie W. Shore - 01-16-2014, 03:14 AM RE: Solving a Single Congruence Equation - Thomas Klemm - 04-12-2014, 07:22 AM RE: Solving a Single Congruence Equation - rprosperi - 04-12-2014, 11:00 PM RE: Solving a Single Congruence Equation - Thomas Klemm - 04-15-2014, 01:48 PM RE: Solving a Single Congruence Equation - Han - 04-15-2014, 11:31 PM RE: Solving a Single Congruence Equation - Thomas Klemm - 04-16-2014, 04:00 AM RE: Solving a Single Congruence Equation - Han - 04-16-2014, 04:23 AM RE: Solving a Single Congruence Equation - Thomas Klemm - 04-16-2014, 07:48 AM RE: Solving a Single Congruence Equation - salvomic - 02-07-2015, 03:12 PM RE: Solving a Single Congruence Equation - Albert Chan - 03-08-2019, 03:24 AM RE: Solving a Single Congruence Equation - Albert Chan - 03-08-2019, 07:16 PM RE: Solving a Single Congruence Equation - Albert Chan - 03-08-2019, 11:34 PM RE: Solving a Single Congruence Equation - Albert Chan - 03-09-2019, 02:10 PM RE: Solving a Single Congruence Equation - Albert Chan - 03-10-2019, 12:45 AM RE: Solving a Single Congruence Equation - Albert Chan - 03-12-2019, 03:46 AM RE: Solving a Single Congruence Equation - Albert Chan - 03-12-2019 09:03 PM

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