---
title: 離散 part2
---
{%hackmd @NTNUCSIE112/DM_card %}

# Modular arithmetic 模運算
Ch.4 Number Theory and Cryptography
Reading assigned: 4.1, 4.3, 4.4, 4.6
### 基礎模運算
#### 【Defination】
定義：給兩個正整數 $a,b$ 和一個正整數 $m$ ，當 $(a-b)|m$時，我們說 $a$ 和 $b$ 對模 $m$ 同餘 ( $a$ is congruent to $b$ modulo $m$ )

記成：$a\equiv b(mod\ m)$（$\rightarrow$ $a$ 同餘 $b$ 模 $m$）
#### 【Proposition】
命題：設 $a,b\in Z$ 和 $m\in N$ ，
$a\equiv b(mod\ m),c\equiv d(mod\ m)\implies(a+c)\equiv(b+d)(mod\ m)$
證明：
$(a-b)|m,(c-d)|m$
$\implies (a-b)\equiv k_1m ,(c-d)\equiv k_2m ,k_1,k_2 \in Z$
$\implies(a-b)+(c-d)=(k_1+k_2)m$
$\implies m|(a+c)-(b+d)$
#### 【Proposition】
命題：設 $a,b\in Z$ 和 $m\in N$，
$a\equiv b(mod\ m),c\equiv d(mod\ m)\implies ac \equiv bd(mod\ m)$
證明：
$\begin{aligned}
(a-b)\equiv k_1m &\rightarrow a = b + k_1m\\
(c-d)\equiv k_2m &\rightarrow c = d + k_2m\\
&\rightarrow ac = bd + m \cdot (k_1d + k_2b + k_1k_2m)\\
&\rightarrow m | (ac-bd)
\end{aligned}$
$ac \equiv bd(mod\ m)$ 得證
### Arithmetic Modulo $m$
### RSA cryptography system
Ronald **R**ivet | Adi **S**hamir | Leonard **A**dleman
過程
1. 選兩個很大的質數 $p$ 和 $q$，設$n=p\times q,r=(p-1)\times (q-1)$
2. 適當得選擇一個數字 $e$ （加密金鑰 the encrytion）
3. 找一個數字 $d$ (解密金鑰 the decryption key), 使得 $d\cdot e \equiv 1(\mod r)$

然後，Bob 傳送 $(n,e)$ 給 Alice
$c\equiv m^e(\mod n)$ $\xrightarrow{c}$ $c^d\equiv m(\mod n)$
( $m$ 是要傳送的訊息)

【Q1】 給定 $r$ 跟 $e$ 使得 $\gcd(r,e)=1$，如何找到 $d$ 滿足 $d\cdot e \equiv 1(\mod r)$？ $d$是否永遠存在？
【Q2】 For any $m<n$, why $(m^e)^d \equiv m (\mod n)$ ?
- If $\gcd(m, p) = 1$ and $\gcd(m,q) = 1$, then ?
- If $\gcd(m, p) \neq 1$ or $\gcd(m,q) \neq 1$, then ?
【Q3】 RSA 是安全的嗎？
$\rightarrow$ 如果我們有 $d$ ，則我們可以知道祕密 （需要 $d$ ）
$\rightarrow$ 我們可以解 $d\cdot e\equiv 1(\mod r)$ 得到 $d$（需要 $r$ ）
$\rightarrow$ 如果我們知道 $p$ 和 $q$ ，則我們知道 $r$ （需要質因數分解 $n$ ）
RSA加密的安全性建立在質因數分解之困難程度


### 【Theorem】Bezout's identity 貝祖定理
For $a,b \in \mathbb{N}$, 如果 $gcd(a,b)=d$, 那麼 $\exists x,y \in Z$ 滿足 $ax+by=d$
證明：
(Well-ordering axiom: every nonempty subset of $\mathbb{N}$ has a smallest element. 任意取一堆正整數，裡面必有最小值)
- Let $S=\{ax+by|x,y\in \mathbb{Z},ax+by\gt 0\}$
- $S$ : nonempty $\xrightarrow[w.o. ](Creating note...){}$
<!-- 上面有缺 -->
$d^*|a,\ d^*|b,\ \forall c,\ c|a \land c|b \implies c|d^*$
$d^* = ax^* + by^*$
$\begin{aligned}
\text{let } &a = d^* \cdot k_1+r_1(r_1 = r_2 = 0)\\
&b = d^* \cdot k_2+r_2
\end{aligned}$

$d^*|a,\ (a=d^*\cdot k_1+r_1,\ 0 \leq r_1 \lt d^*)$
$d = ax^* + by^*$

$\begin{aligned}
d^* &= ax^* by^*
&= ck_1x^* + ck_2y^*\\
\end{aligned}$

$d^*|a,\ (a=d^*\cdot k_1 + r_1 )$
$d=ax^*+by^*$
$\begin{aligned}
ax^* &=
\end{aligned}$
<!-- 這邊還有缺 -->
#### 【Question】
Q. We know that there "exist" $x$ and $y$ such that $ax + by = d$, where $d = \gcd(a,b)$, but how do we find $x$ and $y$ ?
:::spoiler solution
已知存在 $x,y$ 使得 $ax+by=d$，$d=\gcd(a,b)$，我們要如何尋找 $x,y$ ?
e.g. a = 18 , b = 32

$\ 32 = 1*18+14 \rightarrow 14 = 32-1*18$
$\ 18 = 1*14+4 \rightarrow 4 = 18-1*14$
$\begin{aligned}
14 &= 3*4+2 \rightarrow 2 = 14-3*4\\
&= 14-3*(18-1*14)\\
&= -3*18+4*14\\
&= -3*18 + 4*(32-1*18)\\
&= 4*32-7*18
\end{aligned}$
:::

### 【Theorem】4.4.5 Fermat's Little Theorem 費馬小定理
Let $p$ be a prime.
Then $\forall a \in \mathbb{Z}, \gcd(a, p)= 1 \implies a^{p-1} \equiv 1 (\mod p)$.
(Proposed by Fermat in 1636, formally proved by Euler in 1736)
:::spoiler e.g.
$\begin{aligned}
&p=7,a=3 \\
&\gcd(7,3)=1\\
&3^{7-1} \equiv 1(\mod 7)
\end{aligned}$
| $(\mod7)$ | $3^1$ | $3^2$ | $3^3$ | $3^4$ | $3^5$ | $3^6$ |
| :---------: | :-----: | :-----: | :-----: | :-----: | :-----: | :-----: |
| | 3 | 2 | 6 | 4 | 5 | 1 |
:::
:::spoiler Proof.
consider $\{1,2,3,...,p-1\}$
$a \cdot 1,\ a\cdot 2,\ a\cdot 3,\ ...,\ a\cdot (p-1)$
$\forall \ i \neq j, a\cdot i \not\equiv a\cdot j \ (\mod p)$
$(\text{o.w.}\ \ p|(a\cdot i - a \cdot j)) \implies p|a(i-j) \implies p|(i-j) )$

$\begin{aligned}
(1\cdot a)(2\cdot a)\cdots((p-1)a)&\equiv 1\cdot 2 \cdot \cdots \cdot(p-1)(\mod p)\\
a^{p-1}(1\cdot2\cdot\dots\cdot(p-1))&\equiv 1\cdot2\cdot\dots\cdot(p-1)(\mod p)\\
\implies a^{p-1}&\equiv 1(\mod p)\end{aligned}$
:::

### 【Note】
To compute $d$ , we apply Euclidean algorithm, and then backward substitution.

We can also use Fermat's little theorem since $gcd(e,r) \equiv 1 \implies d = e^{r-2}$

### 【Problem】
Solving congruence equations.
:::spoiler e.g.
:::
......
#### 【Q1】Is there such a solution?(existence)
##### simplified system
$\begin{aligned}
x&\equiv a(\mod m_1)\\
x&\equiv a(\mod m_2)\\
&\vdots\\
x&\equiv a(\mod m_n)\\
\end{aligned}$
$x = a + (m_1, m_2, \cdots, m_n)$
#### 【Q2】

### 【Popostition】
Let $x_1$ and $x_2$ be two solutions of the system:
$\begin{aligned}
x&\equiv a_1(\mod m_1)\\
x&\equiv a_2(\mod m_2)\\
&\vdots\\
x&\equiv a_n(\mod m_n)\\
\end{aligned}$
Then $(x_1-x_2)|\text{lcm}(m_1,m_2,\dots,m_n)$

### 【Theorem】Chinese remainder theorem 中國餘數定理
Let $m_1, m_2, \cdots, m_n$ be pairwise relatively prime positive integer greater than 1, and $a_1, a_2, \cdots, a_n$ arbitrary integers. Then the system

$\begin{aligned}
x&\equiv a_1(\mod m_1)\\
x&\equiv a_2(\mod m_2)\\
&\vdots\\
x&\equiv a_n(\mod m_n)\\
\end{aligned}$

has a unique solution modulo $m_1 \cdot m_2 \cdot \dots \cdot m_n$

<!-- This is the end of the note. -->