交個朋友吧

符號說明

數(shù)域

\(R\)：實(shí)數(shù)
\(Z\)：整數(shù)
\(C\)：復(fù)數(shù)
\(Q\)：有理數(shù)

空間

\(R^n\)：n維實(shí)數(shù)
\(Z^n\)：n維整數(shù)
\(C^n\)：n維復(fù)數(shù)
\(Q^n\)：n維有理數(shù)

集合

\(Z^+\)：正整數(shù)
\(R^+\)：非負(fù)實(shí)數(shù)
\(Z_q,q\geq 1\)：商環(huán)\(Z/qZ\)
\(\left [ n \right ]\)：表示\({1,...,n}\)
\(A/B\)：B在A上的補(bǔ)集
\(|B|\)：集合B中元素的個數(shù)
\(log\)：以2為底
\(M^T\)：向量/矩陣的轉(zhuǎn)置

區(qū)間

（1）對于\(x,y\in R\)，其中\(y>0\)，\(\left \lfloor x \right \rfloor\)表示小于\(x\)的最大整數(shù)，\(x mod y =x-\left \lfloor x/y \right \rfloor y\)
（2）\(\left \lceil x \right \rfloor=\left \lfloor x+1/2 \right \rfloor\)

范數(shù)

范數(shù)（Norm）是一個數(shù)學(xué)概念，用于測量向量空間中向量的“大小”。范數(shù)需要滿足以下性質(zhì)：

非負(fù)性：所有向量的范數(shù)都大于或等于零，只有零向量的范數(shù)為零。
齊次性：對任意實(shí)數(shù)λ和任意向量v，有||λv|| = |λ| ||v||。
三角不等式：對任意向量u和v，有||u + v|| ≤ ||u|| + ||v||。

在實(shí)際應(yīng)用中，范數(shù)通常用于衡量向量或矩陣的大小，比如在機(jī)器學(xué)習(xí)中，范數(shù)常用于正則化項的計算。

常見的范數(shù)有：

L0范數(shù)：向量中非零元素的個數(shù)。
L1范數(shù)：向量中各個元素絕對值之和，也被稱為曼哈頓距離。
L2范數(shù)：向量中各個元素的平方和然后開方，也被稱為歐幾里得距離。
向量：\(||v||=(\sum_{i}v_i^2)^{1/2}\)
矩陣：\(||M||=max_i||m_i||,m_i\)是\(M\)的第\(i\)列
無窮范數(shù)：向量中各個元素絕對值的最大值。

需要注意的是，L0范數(shù)并不是嚴(yán)格意義上的范數(shù)，因為它違反了齊次性。但是在機(jī)器學(xué)習(xí)中，L0范數(shù)常用于衡量向量中非零元素的個數(shù)，因此也被稱為“偽范數(shù)”。

分布采樣

（1）D表示集合S上的一個概率分布，\(x\leftarrow D\)表示根據(jù)概率D采樣\(x\in S\)
（2）\(U(S)\)：S上的均勻分布
（3）若D是一個概率算法，使用\(y\leftarrow D(x)\)表示在輸入x上運(yùn)行算法D，最后賦值\(D(x)\)到輸出y上

最小熵(min entropy)

這里\(X\)是集合中的分布還是元素？

運(yùn)算

模2加\(\oplus\)

即逐比特異或

模\(2^{16}\)加\(\boxplus\)

即加模65536

\[0000000000000000 \boxplus 1000000000000000=1000000000000000 \]

因為\(0 + 2^{15} \bmod \left(2^{16}\right)=2^{15}\)

模\(2^{16}+1\)乘\(\odot\)

即乘模65537，全0作為\(2^{16}\)處理

\[0000000000000000 \odot 1000000000000000=1000000000000001 \]

因為\(2^{16} \times 2^{15} \bmod \left(2^{16}+1\right)=2^{15}+1\)

復(fù)雜度

符號表示

1、\(\Theta\)符號

讀音：theta、西塔；既是上界也是下界(tight)，等于的意思。

是大\(O\)符號和大\(\Omega\)符號的結(jié)合
2、\(O\)符號

讀音：big-oh、歐米可榮（大寫）；表示上界(tightness unknown)，小于等于的意思。

是用于描述函數(shù)漸近行為的數(shù)學(xué)符號,更確切地說，它是用另一個（通常更簡單的）函數(shù)來描述一個函數(shù)數(shù)量級的漸近上界。
3、\(o\)符號

讀音：small-oh、歐米可榮（小寫）；表示上界(not tight)，小于的意思。

4、\(\Omega\)符號

讀音：big omega、歐米伽（大寫）；表示下界(tightness unknown)，大于等于的意思。

與大\(O\)符號的定義類似，但主要區(qū)別是，大\(O\)符號表示函數(shù)在增長到一定程度時總小于一個特定函數(shù)的常數(shù)倍，大\(\Omega\)符號則表示總大于，來描述一個函數(shù)數(shù)量級的漸近下界。
5、\(w\)符號

讀音：small omega、歐米伽（小寫）；表示下界(not tight)，大于的意思。

下面是具體定義：

漸進(jìn)標(biāo)準(zhǔn)

其中\(\widetilde{O}(n)\)表示忽略了poly因子的復(fù)雜度

多項式的(polynomial)

對于某個常數(shù)\(c\)，若\(f(n)=O(n^c)\)，則稱\(f(n)\)關(guān)于n是多項式的，記為\(poly(n)\)。

例如：\(q=Poly(n)\)，即關(guān)于\(n\)的多項式，例如\(q=n^2\)

可忽略的(hegligible)

對于任意常數(shù)\(c\)，有\(f(n)=o(n^{-c})\)，則稱\(f(n)\)關(guān)于n是可忽略的，記為\(negl(n)\)

若一個事件以至少\(1-negl(n)\)的概率發(fā)生，則稱這件事發(fā)生的概率是壓倒性的（overwhelming）

語義安全

（1）\(ADV_Y^X\)：算法\(A\)在攻擊基于安全定義\(X\)的方案\(Y\)時的優(yōu)勢，可簡寫為\(ADV(A)\)
（2）統(tǒng)計不可區(qū)分

若\(\Delta (D_1,D_2)\leq negl(n)\)，則稱\(D_1\)和\(D_2\)是統(tǒng)計不可區(qū)分的，表示\(D_1\approx _s D_2\)。
（3）計算不可區(qū)分
對于任意可區(qū)分分布\(D_1\)和\(D_2\)的概率多項式時間（PPT）算法A，若\(|Pr[A(1^n,D_1)=1]-Pr[A(1^n,D_2)=1]|\leq negl(n)\)，則稱\(D_1\)和\(D_2\)是計算不可區(qū)分的，表示\(D_1\approx _c D_2\)
（4）分布不可區(qū)分