用户: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$,证明完成。