拉格朗日高斯約簡算法
對不起，如果我的問題是微不足道的。我的問題與一篇文章“Paillier Homomorphic encryption to calculate the mean”有關，其中一位成員建議使用拉格朗日高斯歸約算法將解密值減小為有理數。如何使用拉格朗日高斯歸約算法來減少數字？這是原始文章的連結：Paillier Homomorphic encryption to calculate the mean。
Lagrange-Gauss 算法也可以看作是維度 2 中的 LLL。這是使用 GP/Pari 的實現：
\\ Given A modulo N, it returns a fraction u/v s.t. A = u/v (mod N) Gauss(A,N) = { local(L,L3); L = [1,0;lift(A),N]; L3 = L*qflll(L); return(L3[2,1]/L3[1,1]); }**編輯：**考慮由兩個列向量定義的晶格 $ \begin{pmatrix}1\A\end{pmatrix} $ 和 $ \begin{pmatrix}0\N\end{pmatrix} $ . 格子中的向量是：
$$ \alpha \begin{pmatrix}1\A\end{pmatrix} + \beta \begin{pmatrix}0\N\end{pmatrix} = \begin{pmatrix}\alpha\ \alpha A + \beta N\end{pmatrix} $$ 由於我們處於第 2 維，LLL 將返回晶格中最短（非零）的向量。 讓我們打電話
$$ \vec{v} := \begin{pmatrix}v_1\v_2\end{pmatrix} = \begin{pmatrix}\alpha^\ \alpha^ A + \beta^* N\end{pmatrix} \in \mathbb{Z}^2 $$ LLL 返回的向量： $ v_1 $ 和 $ v_2 $ 很小。顯然，我們有 $$ v_2 = \alpha^* A + \beta^* N \equiv \alpha^* A \equiv v_1 A \pmod N $$ 因此 $$ A \equiv \frac{v_2}{v_1} \pmod N $$ 和 $ v_1 $ 和 $ v_2 $ 小的。