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.


1 Answer 1


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) = {

  L = [1,0;lift(A),N];
  L3 = L*qflll(L);


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.

  • $\begingroup$ 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? $\endgroup$
    – Mosen
    Feb 2, 2018 at 13:04
  • $\begingroup$ @Mosen: See the EDIT. Does it answer your question? $\endgroup$
    – user94293
    Feb 2, 2018 at 17:38
  • $\begingroup$ 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. $\endgroup$
    – Mosen
    Feb 3, 2018 at 2:59
  • $\begingroup$ can you please explain the programming terms lift(A), qflll(L), and L3 in the above implementation? $\endgroup$
    – Mosen
    Feb 5, 2018 at 4:19
  • $\begingroup$ See pari.math.u-bordeaux.fr $\endgroup$
    – user94293
    Feb 5, 2018 at 5:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.