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

#

def slz_compute_coppersmith_reduced_polynomials_gram(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 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})

    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.

    ### In this variant we use the Pari LLL_gram reduction function.

    #   It works with the Gram matrix instead of the plain matrix.

    matrixToReduceTransposed = matrixToReduce.transpose() 

    matrixToReduceGram = matrixToReduce * matrixToReduceTransposed

    ### LLL_gram returns a unimodular transformation matrix such that:

    #   umt.transpose() * matrixToReduce * umt is reduced..

    umt = matrixToReduceGram.LLL_gram()

    #print "Unimodular transformation matrix:"

    #for row in umt.rows():

    #    print row

    ### The computed transformation matrix is transposed and applied to the

    #   left side of matrixToReduce. 

    reducedMatrix = umt.transpose() * matrixToReduce

    #print "Reduced matrix:"

    #for row in reducedMatrix.rows():

    #    print row

    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_gram

#