第三次作业

计算机数学

---

1.GCD迭代版

#欧几里得算法
#迭代
def gcd(a,b):
    while b!=0:
        y=b
        b=a%b
        a=y
    return a

---

2.验证EGCD算法正确性

def egcd(a,b):
    r0,r1,s0,s1=1,0,0,1
    while b:
        q,a,b=a//b,b,a%b
        r0,r1=r1,r0-q*r1
        s0,s1=s1,s0-q*s1
    return a,r0,s0

证：

返回值a是a与b最大公倍数，r0，s0分别为等式 $a*r0+b*s0=gcd(a,b)$ 的系数,
根据欧几里得算法有
$gcd(a,b)=gcd(b,a\%b)=gcd(a\%b,a\%b\%b)=......=gcd(a\%b\%...\%b,0)$
得
上述代码运算过程为：

$$\begin{bmatrix} r0 & s0 & a \\ r1 & s1 & b \\ \end{bmatrix} = \begin{bmatrix} r1 & s1 & b \\ r2 & s2 & a\%b \\ \end{bmatrix} =......= \begin{bmatrix} rn & sn & a\%b\%...\%b \\ r(n+1) & s(n+1) & 0 \\ \end{bmatrix}$$
由矩阵运算法则得 (这个我真不会算)
$$\begin{cases} r2=r0-q*r1 (q=a/b) \\ s2=s0-q*s1 (q=a/b) \end{cases}$$

......

$$\begin{cases} r(n+1)=r(n-1)-q*rn \\ s(n+1)=s(n-1)-q*sn \end{cases}$$
以此循环，当b=0时停止。
得到a为gcd的值，r0，s0为方程 $a*r0+b*s0=gcd(a,b)$ 的一组解。

---

3.编程实现同余式的求解。给定同余式 ax = b (mod N)，即给定整数a、b和N，求x。如果无解，也要给出“无解”的提示。

#a*x=N*y1+p(p是余数) ①；b=N*y2+p(p是余数) ②
#有p=b-N*y2;带入①式a*x=N*y1+b-N*y2;得：a*x-(y1+y2)*N=b,即a*x+y*N=b;
#b必为gcd(a,N)的倍数，否则，等式同除以gcd(a,N),则等式右边不为整数。
#故若b不是gcd(a,N)的倍数，则无解
#将上述等式化为a*x'+N*y'=gcd(a,N);则x=x'*(b/gcd(a,N))
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
def f(a,b,N):
    if b%gcd(a,N)!=0:
        print("NO SOLUTION!")
        return 0
    else:
        r0,r1,s0,s1=1,0,0,1
        while N:
            q,a,N=a//N,N,a%N
            r0,r1=r1,r0-q*r1
            s0,s1=s1,s0-q*s1
        return r0*(b/gcd(a,N))

---

4. 编程实现求乘法逆元。给定同余式 ax = (1 mod N)，即给定整数a和N，求x。如果无解，也要给出“无解”的提示。

#由上题可知，ax=(1 mod N)可写为：ax+yN=1。
#条件：a与N互质。
#否则，若a与N不互质，则必存在不为1的整数c为a与N的最大公约数。
#那么，提取c,移至等式右边，得1/c,不为整数，无解。故a与N需互质。
#由于a与N互质，则gcd(a,N)=1;故ax+yN=1=gcd(a,N),求x
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
def f(a,N):
    if gcd(a,N)!=1:
        print("NO SOLUTION!")
        return 0
    else:
        r0,r1,s0,s1=1,0,0,1
        while N:
            q,a,N=a//N,N,a%N
            r0,r1=r1,r0-q*r1
            s0,s1=s1,s0-q*s1
        return r0