Solving a Single Congruence Equation

01162014, 03:14 AM
Post: #1




Solving a Single Congruence Equation
The program solves for x in the equation:
A * x = B mod N Examples: 4 * x = 6 mod 7 A = 4, B = 6, N = 7 Solution: 5 5 * x = 3 mod 17 A = 5, B = 3, N = 17 Solution: 4 11 * x = 3 mod 16 A = 11, B = 3, N = 16 Solution: 9 HP Prime Program: CONG Code:


04122014, 07:22 AM
Post: #2




RE: Solving a Single Congruence Equation
How long does it take to solve:
999999999998 * x = 1 mod 999999999999 Or maybe just: 999998 * x = 1 mod 999999 Kind regards Thomas PS: Ever heard of the Chinese remainder theorem? 

04122014, 11:00 PM
Post: #3




RE: Solving a Single Congruence Equation
(04122014 07:22 AM)Thomas Klemm Wrote: How long does it take to solve: Returns answer of 2 instantly on an actual Prime. I guess faster than instantly on the emulator. Bob Prosperi 

04152014, 01:48 PM
Post: #4




RE: Solving a Single Congruence Equation
(04122014 11:00 PM)rprosperi Wrote: Returns answer of 2 instantly on an actual Prime. I guess faster than instantly on the emulator. Is that the answer to: 999999999998 * x = 1 mod 999999999999 ? Because that's wrong. 999999999998 * 2 = 999999999997 mod 999999999999 But that's probably due to a rounding error: \(\frac{999999999998 \times 2  1}{999999999999} = 1.9999999999969999999999969999999999969999999999969999...\) This will be rounded to 2.00000000000. The correct answer is of course: x = 999999999998 = 1 mod 999999999999 The 2nd example shouldn't suffer from these kind of problems though I didn't test it. Cheers Thomas 

04152014, 11:31 PM
(This post was last modified: 04152014 11:31 PM by Han.)
Post: #5




RE: Solving a Single Congruence Equation
In keeping the algorithm fairly simple, I was thinking of the following adjustment. If \(A > B\) then compute \( (q,r) \in \mathbb{Z}^2 \) such that \( A = qB + r\). Then
\[ Ai  B \equiv (qB+r)i  B \equiv B (qi 1) + ri \] and let \( i \) run from \( N/2 \) to \( N/2 \) (adjusting for even/odd \( N \) of course). Similarly, if \( B = qA + r \) then \[ Ai  B \equiv Ai  (qA+r) \equiv A (iq) r \] We still run into overflow issues, but I think this approach might handle a few more cases than the original approach. Also, I wonder if the MOD command would work better than division inside FP(). Graph 3D  QPI  SolveSys 

04162014, 04:00 AM
Post: #6




RE: Solving a Single Congruence Equation
(04152014 11:31 PM)Han Wrote: In keeping the algorithm fairly simple Euklid's algorithm to calculate the greatest common divisor isn't that complicated. You just keep track of the multiples of A and N. ([u v] is short for: u*N + v*A) Example: 5 * x = 3 mod 17 Calculate gcd(17, 5): [1 0] 17 [0 1] 5 [1 3] 2 = 17  3 * 5 [2 7] 1 = 5  2 * 2 Thus gcd(17, 5) = 1 = 2 * 17 + 7 * 5 Therefore: 5 * 7 = 1 mod 17 5 * 7 * 3 = 3 mod 17 5 * 21 = 3 mod 17 5 * 4 = 3 mod 17 Cheers Thomas PS: You can ignore u. Just keep track of v. 

04162014, 04:23 AM
Post: #7




RE: Solving a Single Congruence Equation
Even simpler :) Very nice!
Graph 3D  QPI  SolveSys 

04162014, 07:48 AM
Post: #8




RE: Solving a Single Congruence Equation
This program shouldn't result in an overflow:
Code: #!/usr/bin/python Cheers Thomas 

02072015, 03:12 PM
Post: #9




RE: Solving a Single Congruence Equation
(01162014 03:14 AM)Eddie W. Shore Wrote: The program solves for x in the equation: I was searching a program like this Thank you, Eddie! Salvo ∫aL√0mic (IT9CLU) :: HP Prime 50g 41CX 71b 42s 39s 35s 12C 15C  DM42, DM41X  WP34s Prime Soft. Lib 

03082019, 03:24 AM
Post: #10




RE: Solving a Single Congruence Equation
It may be easier to solve A x ≡ B (mod N) problem using continued fraction.
It is the same as Euclid extended gcd method, without tracking multiples for A and N Example 5 x ≡ 3 (mod 17) 17/5 = 3 + 1/(2 + 1/2) Drop the last term, we get 3 + 1/2 = 7/2 > 7*5  2*17 = 1, so 7 ≡ 1/5 (mod 17) x ≡ 3/5 ≡ 3*7 ≡ 4 (mod 17) 

03082019, 07:16 PM
(This post was last modified: 03112019 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 coprime to the modulo. 

03082019, 11:34 PM
(This post was last modified: 03092019 02:11 PM by Albert Chan.)
Post: #12




RE: Solving a Single Congruence Equation
(03082019 07:16 PM)Albert Chan Wrote: Example: solve 12345 x ≡ 1 (mod N), with N = 17789, for x For comparison, this build 17789/5444 continued fraction convergents P/Q Code: (next column) = CF * (current column) + (prev column) Q values are not needed here ... 12345 * 8107 ≡ 1 (mod N), thus x ≡ 1/12345 ≡ 8107 (mod N) Edit: it might be cheaper to do Q row instead, since Q's < ½ P's P's = round(Q's * fraction) 

03092019, 02:10 PM
(This post was last modified: 03142019 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 FIX0 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 12345 * 8107 ≡ 1 (mod 17789) x ≡ 1/12345 ≡ 8107 (mod 17789) 

03102019, 12:45 AM
(This post was last modified: 03122019 12:13 PM by Albert Chan.)
Post: #14




RE: Solving a Single Congruence Equation
Another way to do inverse is to force even coef., thus easily reduced.
(make sure mul/div factors coprime to the modulo) Same example, solve 12345 x ≡ 1 (mod 17789) 12345 x ≡ 5444 x ≡ 1 ≡ 17788 (mod 17789) 1361 x ≡ 4447 (mod 17789) (12345  9*1361) x ≡ 1  9*4447 (mod 17789) 96 x ≡ 40022 ≡ 75600 (mod 17789) 2 x ≡ 1575 ≡ 16214 (mod 17789) x ≡ 8107 (mod 17789) If N is large, we can solve another, with smaller modulo: x ≡ (4447  17789 k) / 1361 (mod 17789) → 17789 k ≡ 4447 (mod 1361) 96 k ≡ 4447 ≡ 5808 (mod 1361) 2 k ≡ 121 ≡ 1240 (mod 1361) k ≡ 620 (mod 1361) x ≡ (4447  17789 * 620) / 1361 ≡ 8107 (mod 17789) 

03122019, 03:46 AM
(This post was last modified: 08252020 11:51 PM by Albert Chan.)
Post: #15




RE: Solving a Single Congruence Equation
(03102019 12:45 AM)Albert Chan Wrote: If N is large, we can solve another, with smaller modulo: Example, solve 1223334444 x ≡ 1 (mod 9988776655) List Euclid GCD intermedates, build inverses in reverse order. Start from last pair, 1 x ≡ 1 (mod 3), scale it up. Euclid Inverse(row) (modulo nextrow) 1 → 1 3 → floor(1/3 * 19) = 6 19 → floor(6/19 * 22) = 7 22 → floor(7/22 * 63) = 20 63 → floor(20/63 * 211) = 67 211 → 87 274 → 850 2677 → 8587 27044 → 26611 83809 → 88420 278471 → 115031 362280 → 548544 1727591 → 2857751 9000235 → 3406295 10727826 → 64171061 202101103 → 388432661 1223334444 → 3171632349 9988776655 We have 1/1223334444 (mod 9988776655) ≡ 3171632349 More specifically, [1223334444 , 9988776655] • [3171632349, 388432661] = 1 

03122019, 09:03 PM
(This post was last modified: 08252019 03:50 PM by Albert Chan.)
Post: #16




RE: Solving a Single Congruence Equation
(03122019 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 nextrow) 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)