算法总结之求解模线性方程组

2019-04-13 12:20发布

站内文章 / 模拟电子
11403 0 1685
转自链接：Enumz 1）求解模线性方程 ax = b(mod n) 　　方程ax = b(mod n) -> ax = b + ny ->ax - ny = b 　　-> ax + n (-y) =b 其中a,n,b已知。 可用扩展欧几里得来求解该方程的一组特解。 　　这里给出下列几个定理用来求解方程： 　　1.当且仅当d|b时，方程ax = b(mod n)有解。d=gcd(a,n) 　　2.ax = b(mod n) 或者有d个不同解，或者无解。 　　3.令d=gcd(a,n) 假定对整数x', y', 有d = ax' + ny'， 如果d | b, 则方程ax = b(mod n)有一个解的值为x0, 满足： 　　　　x0=x‘(b/d)(mod n) 　　4.假设方程ax = b(mod n)有解， x0是方程的任意一个解， 则方程对模n恰有d个不同的解， 分别为: 　　　　xi = x0 + i * (n / d), 其中 i = 1,2,3......d - 1 　　根据这4个定理，运用扩展欧几里得算法就能轻易的求出模线性方程的所有解了。 伪代码如下:
MODULAR_LINEAR_EQUATION_SOLVER(a,b,n) (d,x',y')=EXTENDED_EUCLID(a,n) if (d|b) x0=x'(b/d) mod n for i=0 to d-1 print (x0+i(n/d)) mod n else print "no solutions"
2)求解模线性方程组 　　x = a1(mod m1) 　　x = a2(mod m2) 　　x = a3(mod m3) 　　 　　先求解方程组前两项。 x=m1*k1+a1=m2*k2+a2 　-> m1*k1+m2*(-k2)=a2-a1
 　　这个方程可以通过欧几里得求解出最小正整数的k1 则x=m1*k1+a1 显然x为两个方程的最小正整数解。
 　　则这两个方程的通解为 X=x+k*LCM(m1,m2) -> X=x(mod LCM(m1,m2)) 就转换成了一个形式相同方程了
 　　在通过这个方程和后面的其他方程求解。最终的结果就出来了。

热门文章