RSA系列——高精度除法

01-28

為什麼要寫這個呢……

RSA演算法中涉及到大質數的找尋以及大整數的運算，高精度的除法和取模難以避免，那本文就當是對之前的RSA系列的一個補充吧。

筆者苦苦求教很久，卻發覺國內有關高精度除法的相關文獻甚少，目前大概只知道三種演算法：課本除法（也就是模擬列豎式）、分治除法（具體尚不明確）以及牛頓除法（本文將會介紹）。另外還從Picks大爺處偷學來了多項式求逆、多項式除法和取模的演算法，本期待可坐享其成，不料Picks本人也表示也沒想過將那演算法應用到高精度除法去，只好作罷。後來經過@李陶冶大爺指點，學來了這麼個方法……在國外的一篇paper上看到這個方法叫Newton Division，姑且就譯作牛頓除法吧……下面對此演算法進行簡述。

我們在計算 $Adiv B$ 時，相當於計算 $Atimes frac{1}{B}$ ，我們可以試著求一下 $frac{1}{B}$ 的近似值。構造數列 $left{ a_{n} right}$ 其中 $0<a_{1} <frac{1}{B}$ ，且滿足遞推式 $a_{n+1} =a_{n}left( 2-Ba_{n} right)$ 。很容易得出此數列收斂於 $frac{1}{B}$ 。那麼 $left{ a_{n} right}$ 收斂得有多快呢？可以由計算的出結果。下面的方法由@陸葳蕤提供，這裡只說個大概。

構造數列 $left{ b_{n} right}$ ，其中 $b_{n}=frac{1}{B} -a_{n}$ ，則 $a_{n}=frac{1}{B}-b_{n}$ ，帶入 $left{ a_{n} right}$ 的遞推式有 $b_{n+1}=Bb_{n}^{2}$ ，累乘可得 $b_{n+1}=b_1left( Bb_1right) ^{2^n-1}$ 。雙指數！收斂速度十分可觀。