Laboratoire de l'Informatique et du Parallélisme » Pobyso

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