CINTA_03

CINTA作业二

7、手动计算一下模\(m\)下\(a\)的乘法逆元。\((a)m=11,a=5;(b)m=121,a=13;(c)m=1021,a=131\)。

---

解：

(a)由题目得,先算出\(gcd(11,5)\)的\(Bezout\)系数：

\(\begin{pmatrix}1&0&11\\0&1&5\end{pmatrix}\to\begin{pmatrix}0&1&5\\1&-2&1\end{pmatrix}\)，可得\(11+(-2)*5=1\),可得\((-2)*5\equiv1\ (mod\ 11)\),所以模\(11\)下\(5\)的乘法逆元是-2.

(b)先算出\(gcd(121,13)\)的\(Bezout\)系数：

\(\begin{pmatrix}1&0&121\\0&1&13\end{pmatrix}\to\begin{pmatrix}0&1&13\\1&-9&4\end{pmatrix}\to\begin{pmatrix}1&-9&4\\-3&28&1\end{pmatrix}\)，可得\(28*12\equiv1\ (mod\ 121)\)，所以模\(121\)下\(13\)的乘法逆元是28。

(c)先算出\(gcd(1021,131)\)的\(Bezout\)系数：

\(\begin{pmatrix}1&0&1021\\0&1&131\end{pmatrix}\to\begin{pmatrix}0&1&131\\1&-7&104\end{pmatrix}\to\begin{pmatrix}1&-7&104\\-1&8&27\end{pmatrix}\to\begin{pmatrix}-1&8&27\\4&-31&23\end{pmatrix}\to\)

\(\begin{pmatrix}4&-31&23\\-5&39&4\end{pmatrix}\to\begin{pmatrix}-5&39&4\\29&-226&3\end{pmatrix}\to\begin{pmatrix}29&-226&3\\-34&265&1\end{pmatrix}\),可得\(265*131\equiv1\ (mod\ 1021)\)，所以模1021下131的的乘法逆元是265.

---

8、编写C语言程序完成模指数运算，即给定整数\(x,y\)和\(m\)为输入，计算并返回值\(x^y\ mod\ m\)。

---

#include <iostream>
using namespace std;

int mod_exp(int x, int y, int m){
    int result = 1;
    while(y > 0){
        if((y & 1) == 1)
            result = (result * x) % m;
        y /= 2;
        x = (x * x) % m;
    }
    return result;
}

---

9、定义 \(Fibonacci\) 数列如下： \(F ( 0 ) = 0 , F ( 1 ) = 1 F(0)=0,F(1)=1 F(0)=0,F(1)=1\)，且对于 \(n \le 2 , F ( n ) = F ( n − 1 ) + F ( n − 2 )\) 。所以，该数列是： \(0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , . .\) 。如何能快速地求出 \(F(n)\) 呢？很幸运，我们有以下等式： \[\begin{bmatrix}1&1\\1&0\end{bmatrix}^n=\begin{bmatrix}F(n+1)&F(n)\\F(n)&F(n-1)\end{bmatrix}\]

虽然，看上去改算法需要一次矩阵的指数运算，但是借助快速指数运算的方法，这里可以产生一个快速求解\(F(n)\)的算法。请给出算法，并编程实现，C语言或者Python都可以。

---

解：可得出一下算法：

\[\begin{bmatrix}1&1\\1&0\end{bmatrix}^n=\begin{cases}\left(\begin{bmatrix}1&1\\1&0\end{bmatrix}^\frac{n}{2}\right)^2\ \ \ n等于偶数\\\begin{bmatrix}1&1\\1&0\end{bmatrix}\left(\begin{bmatrix}1&1\\1&0\end{bmatrix}^\frac{n}{2}\right)^2\ \ \ \ n等于奇数\end{cases}\]

Python程序：

def matrix_multi(m1, m2):  # 计算两个矩阵的乘积
    res = [m1[0] * m2[0] + m1[1] * m2[2], m1[0] * m2[1] + m1[1] * m2[3], m1[2] * m2[0] + m1[3] * m2[2],
           m1[2] * m2[1] + m1[3] * m2[3]]
    return res  #返回为list


def Fibonacci(n):  #返回值为list，要求的Fibonacci数为list[2]
    base = [1, 1, 1, 0]
    if n == 0:  # 第0个Fibonacci数的矩阵是单位矩阵
        return [1, 0, 0, 1]
    if n == 1:
        return base
    if n & 1 == 1:  # n为奇数
        return matrix_multi(base, matrix_multi(Fibonacci(int(n / 2)), Fibonacci(int(n / 2))))
    if n & 1 == 0:  # n为偶数
        return matrix_multi(Fibonacci(int(n / 2)), Fibonacci(int(n / 2)))

---

10、给定互素的正整数\(c\)和\(m\)，请证明在\(mod\ m\)的意义上存在唯一确定的整数值 \(c^{-1}\)，它使得 \(c c^{-1}\equiv(mod\ m)\)。

---

解：由题可得\(gcd(c,m)=1\)，由\(Bezout\)定理可得，一定存在整数\(r，s\)使得\(gcd(c,m)=cr+ms\)，所以一定存在\(cr+ms=1\)，即\(cc^{-1}\equiv1\ (mod\ m)\)一定存在；若\(c^{-1}\)不唯一，任取乘法逆元\(c^{'}、c^{''}\)两个数且设\(|c^{'}-c^{''}|=k\)，所以有\(\begin{cases}cc^{’}\equiv1\ (mod\ m)\\cc^{''}\equiv1\ (mod\ m)\end{cases}\ \to c(c^{'}-c^{''})\equiv0\ (mod\ m)\)，即\(ck\equiv0\ (mod\ m)\)，因为\(c\ne0\)，所以\(k\equiv0\ (mod\ m)\)，可以认为\(c^{'}\)与\(c^{''}\)相等，矛盾，所以乘法逆元\(c^{-1}\)唯一。

---

11、编程题：编写一个 Python 程序计算乘法逆元，即输入互素的正整数 c 和 m，返回 c ，使得 cc−1 ≡ (mod m)。要求:只返回为正整数的 c−1。

---

def congruence(c, m):
    r0, r1, s0, s1 = 1, 0, 0, 1
    while m:
        q, c, m = int(c / m), m, c % m
        r0, r1 = r1, r0 - q * r1
        s0, s1 = s1, s0 - q * s1
    return r0

---