SEAL全同态加密開源庫(三) NTT代碼分析
[email protected]
2021-10-17
前言
這是SEAL開源庫代碼分析報告第三篇，本篇将首先介紹一下編譯運作的最終版的成果，借此對第一篇部落格的部分編譯内容加以修正。然後本篇将重點介紹SEAL庫多項式乘法的重要基礎算法：NTT。注意這裡将涉及大量的理論基礎，可能略顯枯燥困難。
編譯步驟的修正
在第一篇部落格中，講述了編譯運作SEAL庫的完整步驟，但是并未經過實戰檢驗，經過檢驗，發現部分内容存在漏洞，在經過很久的嘗試之後，終于對最新版的SEAL庫（version:3.7）實作了編譯運作，這在網絡上還是很難找到相關的資料的，是以我覺得有必要加以記錄下來。
當時的步驟是這樣的：
但是後來發現這樣是不對的，原因在于release版本和debug版本的編譯結果并不能完全混用，是以我重新想辦法解決了這個問題：
完美運作SEAL庫示例
打開cmake編譯後的SEAL工程，找到INSTALL，這個時候要注意，我們要選擇release編譯（VS沒有，那就在config裡面建立一個release的編譯選項），右鍵INSTALL 點選生成。然後等待顯示成功編譯後，我們回到這個目錄 就會發現生成了release所對應的lib庫，（再說一次，帶d的是debug的，不帶d的是release），接下來就可以進行release的配置了。完美！
其中可能會遇到報錯，解決方案：用管理者身份打開VS2019即可。
目前終于完全解決了安裝配置的問題。
可以做到建立項目檔案中導入SEAL作為第三方庫。（雖然短期看來沒什麼用，主要是為了驗證安裝配置的正确性）
example檔案夾可以跑了。
把該檔案夾拷貝出來，用VS隻打開該檔案夾，會自動執行cmake，當然，注意配置cmake時，一定要選擇Release-x64（預設的是debug-x64），因為我們引用的庫是release版本的。
打開sealexample.cpp，點選運作，編譯無誤，即可生成.exe檔案運作。
注意，網上的例子絕大多數，導包是沒問題的，都不能成功運作，因為版本問題。最好還是跑3.7包裡面的example。
FTT
由于NTT是對FTT的優化，是以在講解NTT之前，有必要先講解FTT——快速傅裡葉變換。
快速傅裡葉變換 (fast Fourier transform),即利用計算機計算離散傅裡葉變換（DFT)的高效、快速計算方法的統稱，簡稱FFT。快速傅裡葉變換是1965年由J.W.庫利和T.W.圖基提出的。采用這種算法能使計算機計算離散傅裡葉變換所需要的乘法次數大為減少，特别是被變換的抽樣點數N越多，FFT算法計算量的節省就越顯著。
FFT（Fast Fourier Transformation） 是離散傅氏變換（DFT）的快速算法。即為快速傅氏變換。它是根據離散傅氏變換的奇、偶、虛、實等特性，對離散傅立葉變換的算法進行改進獲得的。
——百度百科
FFT（Fast Fourier Transformation），中文名快速傅裡葉變換，用來加速多項式乘法。
在這裡在讀完相關文獻入門之後，我先給出我個人的一點了解：
任意多項式由系數形式轉換為點值形式，正常代入n個不同數的複雜度是O（n^2），原因是n個數，每個數n項，相乘就是平方。
通過Omega的特殊性質，我們可以将帶入的數標明為Omega的k(k:1-n)次方，這樣還是n個數，但每個數的複雜度降為logn（分治了，每次分治砍一半，回溯看一半的結果即可推得下一半，是以2^x=n，x是對數形式），是以總複雜度化為了nlongn。
受限于篇幅，僅介紹一些重要的理論基礎：
對于兩個用系數表示的多項式，我們把它們相乘，設兩個多項式分别為A ( x ) , B ( x ) ，我們要枚舉A每一位的系數與B每一位的系數相乘，那麼系數表示法做多項式乘法時間複雜度O(n^2)，但兩個用點值表示的多項式相乘，隻需要O(n)的時間。
這裡設計一些複數、極坐标的理論基礎，不再贅述。
重點是掌握這幾個公式：
OK，掌握了這些基本性質之後，我們把A(X)裡面的x替換成機關根的k次方，看看有什麼可以化簡的地方，這也就是FTT的牛逼之處：
IFFT
我們把兩個多項式相乘 （也叫求卷積），做完兩遍F F T FFTFFT也知道了積的多項式的點值表示。下面要解決的問題是，怎麼把點值表示的多項式快速轉回系數表示法？
先給結論：
一個多項式在分治的過程中乘上機關根的共轭複數，分治完的每一項除以n nn即為原多項式的每一項系數。
是以FFT和IFFT可以一起完成。
下面給出代碼實作，基本上就是分治遞歸的思想，當然進一步優化加入了疊代，非常巧妙：
void fft(cp *a,int n,int inv)
{
int bit=0;
while ((1<<bit)<n)bit++;
fo(i,0,n-1)
{
rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
if (i<rev[i])swap(a[i],a[rev[i]]);//不加這條if會交換兩次（就是沒交換）
}
for (int mid=1;mid<n;mid*=2)//mid是準備合并序列的長度的二分之一
{
cp temp(cos(pi/mid),inv*sin(pi/mid));//機關根，pi的系數2已經約掉了
for (int i=0;i<n;i+=mid*2)//mid*2是準備合并序列的長度，i是合并到了哪一位
{
cp omega(1,0);
for (int j=0;j<mid;j++,omega*=temp)//隻掃左半部分，得到右半部分的答案
{
cp x=a[i+j],y=omega*a[i+j+mid];
a[i+j]=x+y,a[i+j+mid]=x-y;//這個就是蝴蝶變換什麼的
}
}
}
}
NTT
簡介：
一種快速數論變換算法，這種算法是以數論為基礎，對樣本點為的數論變換，按時間抽取的方法，得到一組等價的疊代方程，有效高速簡化了方程中的計算公式·與直接計算相比，大大減少了運算次數。（見快速傅裡葉變換）。
在計算機實作多項式乘法中，我們所熟知的快速傅裡葉變換(FFT)是基于n次機關根 (omega) 的優秀性質實作的，而由于其計算時會使用正弦函數和餘弦函數，在不斷運算時無法避免地會産生精度誤差。而多項式乘法有些時候會建立在模域中，在對一些特殊的大質數取模時，便可以考慮用原根g來代替 ，而這些特殊的大質數的原根恰好滿足 的某些性質，這使得多項式乘法在模域中也可以快速的分治合并。
——百度百科
和FFT一樣，NTT也用來加速多項式乘法，不過NTT最大的優點是可以取模，或者可以了解為NTT是FFT的取模更新版。
其優點如下：
- 能取模，FFT的複數無法取個模
- 沒有精度差，F F T FFTFFT浮點數的精度怎麼也會出一點問題
- 由于均為整數操作（雖然取模多）NTT常數小，通常比一大堆浮點運算的FFT要快
是以，我們的SEAL庫選用NTT來完成多項式乘法。
理論基礎，涉及到數論的一些知識，重點是原根。
原根是一種數學符号，設m是正整數，a是整數，若a模m的階等于φ(m)，則稱a為模m的一個原根。（其中φ(m)表示m的歐拉函數）
假設一個數g是P的原根，那麼g^i mod P的結果兩兩不同，且有 1<g<P，0<i<P，歸根到底就是g^(P-1) = 1 (mod P)當且僅當指數為P-1的時候成立.(這裡P是素數)。
簡單來說，g^i mod p ≠ g^j mod p （p為素數），其中i≠j且i, j介于1至(p-1)之間，則g為p的原根。
是以可以把g^{(p-1)/n}看成w n 1 的等價。其他的思想、步驟與FTT大部分相同。
貼代碼就知道了：
inline void ntt(int a[],int len,int inv)
{
int bit=0;
while ((1<<bit)<len)++bit;
fo(i,0,len-1)
{
rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
if (i<rev[i])swap(a[i],a[rev[i]]);
}//前面和FFT一樣
for (int mid=1;mid<len;mid*=2)
{
int tmp=pow(g,(mod-1)/(mid*2));//原根代替機關根
if (inv==-1)tmp=pow(tmp,mod-2);//逆變換則乘上逆元
for (int i=0;i<len;i+=mid*2)
{
int omega=1;
for (ll j=0;j<mid;++j,omega=omega*tmp%mod)
{
int x=a[i+j],y=omega*a[i+j+mid]%mod;
a[i+j]=(x+y)%mod,a[i+j+mid]=(x-y+mod)%mod;//注意取模
}
}//大體和FFT差不多
}
}
後記
以上是有關NTT一些核心的理論、代碼，至于SEAL中對NTT的實作則複雜得多，詳見下一篇部落格。