Solving a Single Congruence Equation
01-16-2014, 03:14 AM
Post: #1
 Eddie W. Shore Senior Member Posts: 1,606 Joined: Dec 2013
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:
 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;
04-12-2014, 07:22 AM
Post: #2
 Thomas Klemm Senior Member Posts: 2,141 Joined: Dec 2013
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?
04-12-2014, 11:00 PM
Post: #3
 rprosperi Super Moderator Posts: 6,485 Joined: Dec 2013
RE: Solving a Single Congruence Equation
(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.

--Bob Prosperi
04-15-2014, 01:48 PM
Post: #4
 Thomas Klemm Senior Member Posts: 2,141 Joined: Dec 2013
RE: Solving a Single Congruence Equation
(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
04-15-2014, 11:31 PM (This post was last modified: 04-15-2014 11:31 PM by Han.)
Post: #5
 Han Senior Member Posts: 1,882 Joined: Dec 2013
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 (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().

Graph 3D | QPI | SolveSys
04-16-2014, 04:00 AM
Post: #6
 Thomas Klemm Senior Member Posts: 2,141 Joined: Dec 2013
RE: Solving a Single Congruence Equation
(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.
04-16-2014, 04:23 AM
Post: #7
 Han Senior Member Posts: 1,882 Joined: Dec 2013
RE: Solving a Single Congruence Equation
Even simpler :-) Very nice!

Graph 3D | QPI | SolveSys
04-16-2014, 07:48 AM
Post: #8
 Thomas Klemm Senior Member Posts: 2,141 Joined: Dec 2013
RE: Solving a Single Congruence Equation
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)
Maybe somebody feels like translating that for the Prime?

Cheers
Thomas
02-07-2015, 03:12 PM
Post: #9
 salvomic Senior Member Posts: 1,396 Joined: Jan 2015
RE: Solving a Single Congruence Equation
(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

∫aL√0mic (IT9CLU) :: HP Prime 50g 41CX 71b 42s 39s 35s 12C 15C - DM42, DM41X - WP34s Prime Soft. Lib
03-08-2019, 03:24 AM
Post: #10
 Albert Chan Senior Member Posts: 2,699 Joined: Jul 2018
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)
03-08-2019, 07:16 PM (This post was last modified: 03-11-2019 02:58 PM by Albert Chan.)
Post: #11
 Albert Chan Senior Member Posts: 2,699 Joined: Jul 2018
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 co-prime to the modulo.
03-08-2019, 11:34 PM (This post was last modified: 03-09-2019 02:11 PM by Albert Chan.)
Post: #12
 Albert Chan Senior Member Posts: 2,699 Joined: Jul 2018
RE: Solving a Single Congruence Equation
(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  5444

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)
03-09-2019, 02:10 PM (This post was last modified: 03-14-2019 12:42 AM by Albert Chan.)
Post: #13
 Albert Chan Senior Member Posts: 2,699 Joined: Jul 2018
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 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 17789

12345 * 8107 ≡ 1 (mod 17789)
x ≡ 1/12345 ≡ 8107 (mod 17789)
03-10-2019, 12:45 AM (This post was last modified: 03-12-2019 12:13 PM by Albert Chan.)
Post: #14
 Albert Chan Senior Member Posts: 2,699 Joined: Jul 2018
RE: Solving a Single Congruence Equation
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)
03-12-2019, 03:46 AM (This post was last modified: 10-02-2022 03:12 PM by Albert Chan.)
Post: #15
 Albert Chan Senior Member Posts: 2,699 Joined: Jul 2018
RE: Solving a Single Congruence Equation
(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 intermediates, build inverses in reverse order.

9988776655 → 3171632349
1223334444 → -388432661
202101103 → 64171061
10727826 → -3406295
9000235 → 2857751
1727591 → -548544
362280 → 115031
278471 → -88420
83809 → 26611
27044 → -8587
2677 → 850
274 → -87
211 → -floor(-20/63 * 211) = 67
63 → -floor(7/22 * 63) = -20
22 → -floor(-6/19 * 22) = 7
19 → -floor(1/3 * 19) = -6
3  → 1 ; 1-1 ≡ 1 (mod 3)
1 = gcd

9988776655 * -388432661 + 1223334444 * 3171632349 = 1

→ 1/9988776655 ≡ -388432661 (mod 1223334444)
→ 1/1223334444 ≡ 3171632349 (mod 9988776655)
03-12-2019, 09:03 PM (This post was last modified: 10-02-2022 02:21 PM by Albert Chan.)
Post: #16
 Albert Chan Senior Member Posts: 2,699 Joined: Jul 2018
RE: Solving a Single Congruence Equation
There is no need to walk the whole chain of inverses.

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

1/3 ≡ -6 (mod 19)    → x ≈ |floor(−6/19 * 9988776655)| = 3154350523
1/19 ≡ +7 (mod 22) → x ≈ |floor(+7/22 * 9988776655)| = 3178247117

x is between above limits.
We can extrapolation in smaller steps, to scale to correct inverses.

$$\displaystyle \left|{6 \over 19} - {7 \over 22}\right| = {1 \over 19×22} = {1 \over 418} < {1 \over 274}$$

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

Redo previous example, skipping unneeded calculations.

9988776655 → (-1)^6 floor(115031/362280 * 9988776655) = 3171632349
1223334444
202101103
10727826
9000235
1727591
362280 → (-1)^5 floor(-87/274 * 362280) = 115031 ; 362280*1727591 ≈ 626e9
278471
83809
27044
2677
274 → (-1)^3 floor(7/22 * 274) = -87 ; 274*2677=733498
211
63
22 → (-1)^2 floor(1/3 * 22) = 7 ; 22*63=1386
19
3 → 1 ; 3*19=57
1 = gcd

4th scalings gives: 1/1223334444 ≡ 3171632349 (mod 9988776655)
10-01-2022, 03:48 PM (This post was last modified: 10-02-2022 03:43 PM by Albert Chan.)
Post: #17
 Albert Chan Senior Member Posts: 2,699 Joined: Jul 2018
RE: Solving a Single Congruence Equation
CAS> c := dfc(9988776655/1223334444)      → [8,6,18,1,5,4,1,3,3,10,9,1,3,2,1,6,3]
CAS> dfc2f( reverse(c) )                               → 9988776655 / 3171632349

Building of inverses are equivalent to convergents of reversed continued fraction coefficients.
(with alternative signs, starting from 1-1 ≡ +1 (mod m))

9988776655  8 *388432661+64171061 = 3171632349
1223334444  6 *64171061+3406295 = 388432661 -
202101103  18 *3406295+2857751 = 64171061
10727826    1 *2857751+548544 = 3406295 -
9000235     5 *548544+115031 = 2857751
1727591     4 *115031+88420 = 548544 -
362280      1 *88420+26611 = 115031
278471      3 *26611+8587 = 88420 -
83809       3 *8587+850 = 26611
27044      10 *850+87 = 8587 -
2677        9 *87+67 = 850
274         1 *67+20 = 87 -
211         3 *20+7 = 67
63          2 *7+6 = 20 -
22          1 *6+1 = 7
19          6 *1+0 = 6 -
3                    1
1 = gcd
 « Next Oldest | Next Newest »

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