+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: HP Prime Software Library (/forum-15.html)
+--- Thread: Solving a Single Congruence Equation (/thread-446.html)
Solving a Single Congruence Equation - Eddie W. Shore - 01-16-2014 03:14 AM
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:
EXPORT CONG( )
BEGIN
LOCAL A,B,N,I;
// 2014-01-15 EWS
INPUT({A,B,N}, "Ax = B mod N",
{"A","B","N"}, { }, {0, 0, 0} );
// safe guard if the user does not enter integers (optional line)
A:=IP(A); B:=IP(B); N:=IP(N);
// Algorithm
FOR I FROM 1 TO N-1 DO
IF FP((A*I-B)/N) == 0 THEN
MSGBOX("x ="+STRING(I));
RETURN I;
KILL;
END;
END;
RETURN "No Solution";
END;RE: Solving a Single Congruence Equation - Thomas Klemm - 04-12-2014 07:22 AM
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?
RE: Solving a Single Congruence Equation - rprosperi - 04-12-2014 11:00 PM
(04-12-2014 07:22 AM)Thomas Klemm Wrote: 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?
Returns answer of 2 instantly on an actual Prime. I guess faster than instantly on the emulator.
RE: Solving a Single Congruence Equation - Thomas Klemm - 04-15-2014 01:48 PM
(04-12-2014 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
RE: Solving a Single Congruence Equation - Han - 04-15-2014 11:31 PM
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 (i-q) -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().
RE: Solving a Single Congruence Equation - Thomas Klemm - 04-16-2014 04:00 AM
(04-15-2014 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.
RE: Solving a Single Congruence Equation - Han - 04-16-2014 04:23 AM
Even simpler :-) Very nice!
RE: Solving a Single Congruence Equation - Thomas Klemm - 04-16-2014 07:48 AM
This program shouldn't result in an overflow:
Code:
#!/usr/bin/python
def add(a, b, n):
result = a + b
return result if result < n else (a - n) + b
def minus(a, b, n):
result = a - b
return result if 0 <= result else result + n
def double(a, n):
return add(a, a, n)
def times(a, b, n):
result = 0
while a > 0:
if a % 2:
result = add(result, b, n)
a /= 2
b = double(b, n)
return result
def inverse(a, n):
p, q = n, a
u, v = 0, 1
while q > 0:
r = p / q
u, v = v, minus(u, times(r, v, n), n)
p, q = q, p - r * q
return u
a, b, n = 5, 3, 17
print times(inverse(a, n), b, n)
a, b, n = 999999999998, 1, 999999999999
print times(inverse(a, n), b, n)Cheers
Thomas
RE: Solving a Single Congruence Equation - salvomic - 02-07-2015 03:12 PM
(01-16-2014 03:14 AM)Eddie W. Shore Wrote: The program solves for x in the equation:
A * x = B mod N
I was searching a program like this
Thank you, Eddie!
Salvo
RE: Solving a Single Congruence Equation - Albert Chan - 03-08-2019 03:24 AM
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)
RE: Solving a Single Congruence Equation - Albert Chan - 03-08-2019 07:16 PM
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 co-prime to the modulo.
RE: Solving a Single Congruence Equation - Albert Chan - 03-08-2019 11:34 PM
(03-08-2019 07:16 PM)Albert Chan Wrote: Example: solve 12345 x ≡ 1 (mod N), with N = 17789, for x
12345 ≡ -5444 (mod N)
For comparison, this build 17789/5444 continued fraction convergents P/Q
Code:
(next column) = CF * (current column) + (prev column)
CF 3 3 1 2 1 3 1 6 5 2
P 0 1 3 10 13 36 49 183 232 1572 8107 17789
Q 1 0 1 3 4 11 15 56 71 482 2481 5444Q 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)
RE: Solving a Single Congruence Equation - Albert Chan - 03-09-2019 02:10 PM
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 1778912345 * 8107 ≡ 1 (mod 17789)
x ≡ 1/12345 ≡ 8107 (mod 17789)
RE: Solving a Single Congruence Equation - Albert Chan - 03-10-2019 12:45 AM
Another way to do inverse is to force even coef., thus easily reduced.
(make sure mul/div factors co-prime 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)
RE: Solving a Single Congruence Equation - Albert Chan - 03-12-2019 03:46 AM
(03-10-2019 12:45 AM)Albert Chan Wrote: If N is large, we can solve another, with smaller modulo:
x ≡ (4447 - 17789 k) / 1361 (mod 17789) → 17789 k ≡ 4447 (mod 1361)
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 next-row)
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
RE: Solving a Single Congruence Equation - Albert Chan - 03-12-2019 09:03 PM
(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)