Index: sageSLZ.sage
===================================================================
--- sageSLZ.sage	(revision 273)
+++ sageSLZ.sage	(revision 274)
@@ -521,6 +521,161 @@
     else:
         return ccReducedPolynomialsList
 # End slz_compute_coppersmith_reduced_polynomials_proj
+def slz_compute_weak_coppersmith_reduced_polynomials_proj(inputPolynomial,
+                                                          alpha,
+                                                          N,
+                                                          iBound,
+                                                          tBound,
+                                                          debug = False):
+    """
+    For a given set of arguments (see below), compute a list
+    of "reduced polynomials" that could be used to compute roots
+    of the inputPolynomial.
+    INPUT:
+    
+    - "inputPolynomial" -- (no default) a bivariate integer polynomial;
+    - "alpha" -- the alpha parameter of the Coppersmith algorithm;
+    - "N" -- the modulus;
+    - "iBound" -- the bound on the first variable;
+    - "tBound" -- the bound on the second variable.
+    
+    OUTPUT:
+    
+    A list of bivariate integer polynomial obtained using the Coppersmith
+    algorithm. The polynomials correspond to the rows of the LLL-reduce
+    reduced base that comply with the weak version of Coppersmith condition.
+    """
+    #@par Changes from runSLZ-113.sage
+    # LLL reduction is not performed on the matrix itself but rather on the
+    # product of the matrix with a uniform random matrix.
+    # The reduced matrix obtained is discarded but the transformation matrix 
+    # obtained is used to multiply the original matrix in order to reduced it.
+    # If a sufficient level of reduction is obtained, we stop here. If not
+    # the product matrix obtained above is LLL reduced. But as it has been
+    # pre-reduced at the above step, reduction is supposed to be much faster.
+    #
+    # Arguments check.
+    if iBound == 0 or tBound == 0:
+        return None
+    # End arguments check.
+    nAtAlpha = N^alpha
+    ## Building polynomials for matrix.
+    polyRing   = inputPolynomial.parent()
+    # Whatever the 2 variables are actually called, we call them
+    # 'i' and 't' in all the variable names.
+    (iVariable, tVariable) = inputPolynomial.variables()[:2]
+    #print polyVars[0], type(polyVars[0])
+    initialPolynomial = inputPolynomial.subs({iVariable:iVariable * iBound,
+                                              tVariable:tVariable * tBound})
+    if debug:
+        polynomialsList = \
+            spo_polynomial_to_polynomials_list_8(initialPolynomial,
+                                                 alpha,
+                                                 N,
+                                                 iBound,
+                                                 tBound,
+                                                 20)
+    else:
+        polynomialsList = \
+            spo_polynomial_to_polynomials_list_8(initialPolynomial,
+                                                 alpha,
+                                                 N,
+                                                 iBound,
+                                                 tBound,
+                                                 0)
+    #print "Polynomials list:", polynomialsList
+    ## Building the proto matrix.
+    knownMonomials = []
+    protoMatrix    = []
+    if debug:
+        for poly in polynomialsList:
+            spo_add_polynomial_coeffs_to_matrix_row(poly,
+                                                    knownMonomials,
+                                                    protoMatrix,
+                                                    20)
+    else:
+        for poly in polynomialsList:
+            spo_add_polynomial_coeffs_to_matrix_row(poly,
+                                                    knownMonomials,
+                                                    protoMatrix,
+                                                    0)
+    matrixToReduce = spo_proto_to_row_matrix(protoMatrix)
+    #print matrixToReduce
+    ## Reduction and checking.
+    ### Reduction with projection
+    (reducedMatrixStep1, reductionMatrixStep1) = \
+         slz_reduce_lll_proj(matrixToReduce,16)
+    #print "Reduced matrix:"
+    #print reducedMatrixStep1
+    #for row in reducedMatrix.rows():
+    #    print row
+    monomialsCount     = len(knownMonomials)
+    monomialsCountSqrt = sqrt(monomialsCount)
+    #print "Monomials count:", monomialsCount, monomialsCountSqrt.n()
+    #print reducedMatrix
+    ## Check the Coppersmith condition for each row and build the reduced 
+    #  polynomials.
+    ccReducedPolynomialsList = []
+    for row in reducedMatrixStep1.rows():
+        l1Norm = row.norm(1)
+        l2Norm = row.norm(2)
+        if l2Norm * monomialsCountSqrt < l1Norm:
+            print "l1norm is smaller than l2norm*sqrt(w)."
+        else:
+            print "l1norm is NOT smaller than l2norm*sqrt(w)."
+            print (l2Norm * monomialsCountSqrt).n(), 'vs ', l1Norm.n()
+        if l1Norm < nAtAlpha:
+            #print l2Norm.n()
+            ccReducedPolynomial = \
+                slz_compute_reduced_polynomial(row,
+                                               knownMonomials,
+                                               iVariable,
+                                               iBound,
+                                               tVariable,
+                                               tBound)
+            if not ccReducedPolynomial is None:
+                ccReducedPolynomialsList.append(ccReducedPolynomial)
+        else:
+            #print l2Norm.n() , ">", nAtAlpha
+            pass
+    if len(ccReducedPolynomialsList) < 2: # Insufficient reduction.
+        print "Less than 2 Coppersmith condition compliant vectors."
+        print "Extra reduction starting..."
+        reducedMatrix = reducedMatrixStep1.LLL(algorithm='fpLLL:wrapper')
+        ### If uncommented, the following statement avoids performing
+        #   an actual LLL reduction. This allows for demonstrating
+        #   the behavior of our pseudo-reduction alone.
+        #return ()
+    else:
+        print "First step of reduction afforded enough vectors"
+        return ccReducedPolynomialsList
+    #print ccReducedPolynomialsList
+    ## Check again the Coppersmith condition for each row and build the reduced 
+    #  polynomials.
+    ccReducedPolynomialsList = []
+    for row in reducedMatrix.rows():
+        l2Norm = row.norm(2)
+        if (l2Norm * monomialsCountSqrt) < nAtAlpha:
+            #print (l2Norm * monomialsCountSqrt).n()
+            #print l2Norm.n()
+            ccReducedPolynomial = \
+                slz_compute_reduced_polynomial(row,
+                                               knownMonomials,
+                                               iVariable,
+                                               iBound,
+                                               tVariable,
+                                               tBound)
+            if not ccReducedPolynomial is None:
+                ccReducedPolynomialsList.append(ccReducedPolynomial)
+        else:
+            #print l2Norm.n() , ">", nAtAlpha
+            pass
+    if len(ccReducedPolynomialsList) < 2: # Insufficient reduction.
+        print "Less than 2 Coppersmith condition compliant vectors after extra reduction."
+        return ()
+    else:
+        return ccReducedPolynomialsList
+# End slz_compute_coppersmith_reduced_polynomials_proj
 #
 def slz_compute_coppersmith_reduced_polynomials_with_lattice_volume(inputPolynomial,
                                                                     alpha,
