用戶:C44986054/沙盒

学校文法				教育文法
語意上可獨立使用	活用	品詞
是＝自（じ）立（りつ）語（ご）	有＝用（よう）言（げん）	動詞（終止形以ウ段結尾）
		形容詞（終止形以い結尾）		イ形容詞
		形容動詞（終止形以だ結尾）		ナ形容詞
	無	體言（可做為主詞）	名詞
			代名詞
			數詞
		副詞（主要修飾用言）
		連體詞（主要修飾體言）
		接続詞（接續）
		感動詞（感嘆）
否＝付（ふ）属（ぞく）語（ご）	有	助動詞		（語尾變化）
	無

			唇音	齒音 / 齒齦音	軟顎音	聲門音
塞音	清	送氣	(φ) pʰ	(θ) tʰ	(χ) kʰ
		不送氣	(π) p	(τ) t	(κ) k
	濁		(β) b	(δ) d	(γ) ɡ
鼻音			(μ) m	(ν) n	(ŋ)
擦音	清			, (σ) s		(ʽ) h
	濁			(z)
顫音	清			(r̥)
	濁			(ρ) r
近音				(λ) l

		第一時態		第二時態
		主動	中間態	主動	中間態
單數	第一人稱	-ω	-μαι	-ν	-μην
	第二人稱	-εις	-σαι	-ς	-σο
	第三人稱	-ει(ν)	-ται	(空)	-το
雙數	第二人稱	-τον	-σθον	-τον	-σθον
	第三人稱			-την	-σθην
複數	第一人稱	-μεν	-μεθα	-μεν	-μεθα
	第二人稱	-τε	-σθε	-τε	-σθε
	第三人稱	-ουσι	-νται	-ν	-ντο

定義

定義 — 

若 $X$ 上的二元關係 $F$ 若滿足：

• 反對稱性（antisymmetric）：$(\forall a\in X)(\forall b\in X)\{[(aFb)\wedge (bFa)]\Rightarrow (a=b)\}$
• 傳遞性（transitive）：$(\forall a\in X)(\forall b\in X)(\forall c\in X)\{[(aFb)\wedge (bFc)]\Rightarrow (aFc)\}$
• 完全性（total）：$(\forall a\in X)(\forall b\in X)\{(aFb)\lor (bFa)\}$

則 $F$ 被稱為 $X$ 上的全序關係（total order），此時 $X$ 可稱為全序集合、線性序集合、簡單序集合或鏈。

在不引起混淆的前提下，一般會模仿不等式，將全序關係直觀的表記為 $\leq$ ，這種狀況下，也可以把 $a\leq b$ 記為 $b\geq a$ 。

將完全性定義裏的 $b$ （以量詞公理A4）「代換」成 $b$ 有：

$(\forall a\in X)[(aFa)\lor (aFa)]$

換句話說：

$(\forall a\in X)(aFa)$

所以從完全性可以推出自反性，因此全序關係也是個偏序關係。

正確性證明

首選取兩個互質數 $a$ 和 $b$，並設

$N=ab$

由於$a$和$b$都是質數，與比$N$小又與之不互質的數有兩種:

(1) $a$的倍數，總共$b-1$個

(2) $b$的倍數，總共$a-1$個

故$N$的歐拉函數$\Phi (N)$，也就是比$N$小又與之互質的數，其總數為:

$\Phi (N)=ab-(b-1)-(a-1)-1=(a-1)(b-1)$

若取某個與$\Phi (N)$ 互質的整數$k_{pub}$，並要求$1<k_{pub}<\Phi (N)$，這樣根據擴展歐幾里得算法，可以找到整數$n$和$n^{\prime }$滿足：

$nk_{pub}+n^{\prime }\Phi (N)=1$

整數$n$有時被稱為$e$關於$\Phi (N)$的模反元素

---

此時，RSA的公鑰就是$k_{pub}$，私鑰則設為$k_{pri}=n$。

設原文是正整數$d$，取加密後的整數$c$為

$c=d^{k_{pub}}\%N$

那會有

$d=c^{k_{pri}}\%N$

這是因為

$c^{k_{pri}}\%N-d$

$=\left[{(d^{k_{pub}}\%N)}^{k_{pri}}\right]\%N-d$

$=(d^{k_{pub}k_{pri}})\%N-d$

$=m^{k(p-1)(q-1)+1}\%N-m$

$=m*(m^{k(p-1)(q-1)}-1)\%N$

當m與N互質時，根據費馬小定理公式

$a^{p-1}\equiv 1(mod\ p)$

$\Rightarrow (m^{k(q-1)})^{p-1}\equiv 1(mod\ p)$

$\Rightarrow (m^{k(p-1)})^{q-1}\equiv 1(mod\ q)$

$\Rightarrow m^{k(p-1)(q-1)}\equiv 1(mod\ pq)$

$\Rightarrow m^{k(p-1)(q-1)}\equiv 1(mod\ N)$

$\Rightarrow m*(m^{k(p-1)(q-1)}-1)\%N=0$

當m與N不互質時，不妨設公因子為p，即$m=ph_{1}(h_{1}<q)$

假設q整除m。因此$q\mid ph_{1}$，因為q與p互質，根據歐幾里德引理，$q\mid h_{1}$。所以$q\leq h_{1}$，而這與$h_{1}<q$矛盾，所以q不整除m。

此時m與q互質，根據費馬小定理公式

$a^{p-1}\equiv 1(mod\ p)$

$\Rightarrow m^{q-1}\equiv 1(mod\ q)$

$\Rightarrow m^{k(p-1)(q-1)}\equiv 1(mod\ q)$

$\Rightarrow m^{k(p-1)(q-1)}-1=qh_{2}$

$\Rightarrow m*(m^{k(p-1)(q-1)}-1)\%N=ph_{1}*qh_{2}\%N=Nh_{1}h_{2}\%N=0$,證明完成。