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. 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 »
|
User(s) browsing this thread: 1 Guest(s)