Improve efficiency of find_residue

[jkatzDfns]

Efficiency of the find_residue function in common/sqrt.rs (and the way that function is called by paillier_blum_modulus) can be improved. Remember the goal is to find bits a_i, b_i such that (-1)^{a_i} w^{b_i} y_i is a quadratic residue. This can be done as follows:

• In paillier_blum_modulus, compute jacobi(w, p) and jacobi(w,q). Those values will be passed as inputs to find_residue. (They could also be computed inside find_residue, but then you are repeating work unnecessarily.)
• In find_residue, compute jacobi(y, p) and jacobi(y, q). You then want to find a, b such that (-1)^a jacobi(w,p)^b jacobi(y_i,p) = 1 and (-1)^a jacobi(w,q)^b jacobi(y_i,q) = 1. They can be computed as if (jacobi(y_i, p) == jacobi(y_i, q)) b=0 else b=1; if (jacobi(y_i, p) == 1) a=0 else a=1;

[jkatzDfns]

I wanted to write the code more clearly and efficiently

• In paillier_blum_modulus, compute w_p = jacobi(w, p) (we don't need to compute jacobi(w,q) since jacobi(w,q)= - jacobi(w,p)). Pass w_p as input to find_residue.
• In find_residue, compute y_p=jacobi(y, p) and y_q=jacobi(y, q). Then: if (y_p == y_q) b=0 else b=1; if (y_p * (w_p)^b == 1) a=0 else a=1;