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

def slz_compute_coppersmith_reduced_polynomials_with_lattice_volume(inputPolynomial,

                                                                    alpha,

                                                                    N,

                                                                    iBound,

                                                                    tBound):

    """

    For a given set of arguments (see below), compute a list

    of "reduced polynomials" that could be used to compute roots

    of the inputPolynomial.

    Print the volume of the initial basis as well.

    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 Coppersmith condition.

    """

    # 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})

##    polynomialsList = \

##        spo_polynomial_to_polynomials_list_8(initialPolynomial,

##        spo_polynomial_to_polynomials_list_5(initialPolynomial,

    polynomialsList = \

        spo_polynomial_to_polynomials_list_5(initialPolynomial,

                                             alpha,

                                             N,

                                             iBound,

                                             tBound,

                                             0)

    #print "Polynomials list:", polynomialsList

    ## Building the proto matrix.

    knownMonomials = []

    protoMatrix    = []

    for poly in polynomialsList:

        spo_add_polynomial_coeffs_to_matrix_row(poly,

                                                knownMonomials,

                                                protoMatrix,

                                                0)

    matrixToReduce = spo_proto_to_row_matrix(protoMatrix)

    matrixToReduceTranspose = matrixToReduce.transpose()

    squareMatrix = matrixToReduce * matrixToReduceTranspose

    squareMatDet = det(squareMatrix)

    latticeVolume = sqrt(squareMatDet)

    print "Lattice volume:", latticeVolume.n()

    print "Lattice volume / N:", (latticeVolume/N).n()

    #print matrixToReduce

    ## Reduction and checking.

    ## S.T. changed 'fp' to None as of Sage 6.6 complying to

    #  error message issued when previous code was used.

    #reducedMatrix = matrixToReduce.LLL(fp='fp')

    reductionTimeStart = cputime() 

    reducedMatrix = matrixToReduce.LLL(fp=None)

    reductionTime = cputime(reductionTimeStart)

    print "Reduction time:", reductionTime

    isLLLReduced  = reducedMatrix.is_LLL_reduced()

    if not isLLLReduced:

        return None

    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 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:

        print "Less than 2 Coppersmith condition compliant vectors."

        return ()

    #print ccReducedPolynomialsList

    return ccReducedPolynomialsList

# End slz_compute_coppersmith_reduced_polynomials_with_lattice volume