# Lagrange Gauss Reduction Algorithm

Sorry if my question is trivial. My question is related to a post "Paillier Homomorphic encryption to calculate the means" where a member suggests Lagrange Gauss Reduction Algorithm for reducing a decrypted value to a rational number. How to use Lagrange Gauss Reduction Algorithm for reducing numbers? Here is the link to the original post: Paillier Homomorphic encryption to calculate the means.

Lagrange-Gauss algorithm can also be seen as LLL in dimension 2. Here is an implementation using 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]);
}


EDIT: Consider the lattice defined by the two column vectors $\begin{pmatrix}1\\A\end{pmatrix}$ and $\begin{pmatrix}0\\N\end{pmatrix}$. The vectors in the lattice are: $$\alpha \begin{pmatrix}1\\A\end{pmatrix} + \beta \begin{pmatrix}0\\N\end{pmatrix} = \begin{pmatrix}\alpha\\ \alpha A + \beta N\end{pmatrix}$$ As we are in dimension 2, LLL will return the shortest (non-zero) vector in the lattice.

Let's call $$\vec{v} := \begin{pmatrix}v_1\\v_2\end{pmatrix} = \begin{pmatrix}\alpha^*\\ \alpha^* A + \beta^* N\end{pmatrix} \in \mathbb{Z}^2$$ the vector returned by LLL: $v_1$ and $v_2$ are small. Clearly, we have $$v_2 = \alpha^* A + \beta^* N \equiv \alpha^* A \equiv v_1 A \pmod N$$ and thus $$A \equiv \frac{v_2}{v_1} \pmod N$$ with $v_1$ and $v_2$ small.

• Can you elaborate this implementation a bit more as I am not used to GP/Pari or can you suggest some material about this algorithm? Feb 2, 2018 at 13:04
• @Mosen: See the EDIT. Does it answer your question? Feb 2, 2018 at 17:38
• Now I understand the algorithm. My question is about the implementation code you have given above in which some terms (lift(A), qflll) are not clear to me as it is written in GP/Pari. I am more familiar with MATLAB. Anyhow nice explanation. Feb 3, 2018 at 2:59
• can you please explain the programming terms lift(A), qflll(L), and L3 in the above implementation? Feb 5, 2018 at 4:19
• Feb 5, 2018 at 5:22