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

def slz_compute_integer_polynomial_modular_roots(inputPolynomial,

                                                 alpha,

                                                 N,

                                                 iBound,

                                                 tBound):

    """

    For a given set of arguments (see below) , compute the polynomial modular 

    roots, if any.

    """

    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_5(initialPolynomial,

                                             alpha,

                                             N,

                                             iBound,

                                             tBound,

                                             10)

    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)

    #print matrixToReduce

    ## Reduction and checking.

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

    isLLLReduced  = reducedMatrix.is_LLL_reduced()

    if not isLLLReduced:

        return None

    monomialsCount     = len(knownMonomials)

    monomialsCountSqrt = sqrt(monomialsCount)

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

            ccReducedPolynomial = \

                slz_compute_reduced_polynomial(row,

                                               knownMonomials,

                                               iVariable,

                                               iBound,

                                               tVariable,

                                               tBound)

            if not ccReducedPolynomial is None:

                ccReducedPolynomialsList.append(ccReducedPolynomial)

    if len(ccReducedPolynomialsList) < 2:

        print "Less than 2 Coppersmith condition compliant vectors."

        return None

    ## Create the valid (poly1 and poly2 are algebraically independent) 

    # resultant tuples (poly1, poly2, resultant(poly1, poly2)).

    # Try to mix and match all the polynomial pairs built from the 

    # ccReducedPolynomialsList to obtain non zero resultants.

    resultantsInITuplesList = []

    for polyOuterIndex in xrange(0, len(ccReducedPolynomialsList)-1):

        for polyInnerIndex in xrange(polyOuterIndex+1, 

                                     len(ccReducedPolynomialsList)):

            # Compute the resultant in resultants in the

            # first variable (is it the optimal choice?).

            resultantInI = \

               ccReducedPolynomialsList[polyOuterIndex].resultant(ccReducedPolynomialsList[polyInnerIndex],

                                                                  ccReducedPolynomialsList[0].parent(str(iVariable)))

            #print resultantInI

            #print "Resultant", resultantInI

            # Test algebraic independence.

            if not resultantInI.is_zero():

                resultantsInITuplesList.append((ccReducedPolynomialsList[polyOuterIndex],

                                                 ccReducedPolynomialsList[polyInnerIndex],

                                                 resultantInI))

    # If no non zero resultant was found: we can't get no algebraically 

    # independent polynomials pair. Give up!

    if len(resultantsInITuplesList) == 0:

        return None

    # Compute the roots.

    Zi = ZZ[str(iVariable)]

    Zt = ZZ[str(tVariable)]

    polynomialRootsSet = set()

    # First, solve in the second variable since resultants are in the first

    # variable.

    for resultantInITuple in resultantsInITuplesList:

        tRootsList = Zt(resultantInITuple[2]).roots()

        # For each tRoot, compute the corresponding iRoots and check 

        # them in the polynomial.

        for tRoot in tRootsList:

            print "tRoot:", tRoot

            # Roots returned by root() are (value, multiplicity) tuples.

            iRootsList = \

                Zi(resultantInITuple[0].subs({resultantInITuple[0].variables()[1]:tRoot[0]})).roots()

            # The iRootsList can be empty, hence the test.

            if len(iRootsList) != 0:

                for iRoot in iRootsList:

                    polyEvalModN = inputPolynomial(iRoot[0], tRoot[0]) / N

                    # polyEvalModN must be an integer.

                    if polyEvalModN == int(polyEvalModN):

                        polynomialRootsSet.add((iRoot[0],tRoot[0]))

    return polynomialRootsSet

# End slz_compute_integer_polynomial_modular_roots.

#

def slz_compute_reduced_polynomial(matrixRow,

    Compute a polynomial from a reduced matrix row.

    This function was introduced in order to avoid the computation of the

    polynomials (even those built from rows that do no verify the Coppersmith

    condition.

    """

    ## Check arguments.

    if len(knownMonomials) == 0:

        return None

    # varNounds can be zero since 0^0 returns 1.

    if (var1Bound < 0) or (var2Bound < 0):

        return None

    ## Initialisations. 

    polynomialRing = knownMonomials[0].parent() 

    currentPolynomial = polynomialRing(0)

    for colIndex in xrange(0, len(knownMonomials)):

        currentCoefficient = matrixRow[colIndex]

        if currentCoefficient != 0:

            #print "Current coefficient:", currentCoefficient

            currentMonomial = knownMonomials[colIndex]

            #print "Monomial as multivariate polynomial:", \

            #currentMonomial, type(currentMonomial)

            degreeInVar1 = currentMonomial.degree(var1)

            #print "Degree in var", var1, ":", degreeInVar1

            degreeInVar2 = currentMonomial.degree(var2)

            #print "Degree in var", var2, ":", degreeInVar2

            if degreeInVar1 > 0:

                currentCoefficient = \

                    currentCoefficient / var1Bound^degreeInVar1

                #print "varBound1 in degree:", var1Bound^degreeInVar1

                #print "Current coefficient(1)", currentCoefficient

            if degreeInVar2 > 0:

                currentCoefficient = \

                    currentCoefficient / var2Bound^degreeInVar2

                #print "Current coefficient(2)", currentCoefficient

            #print "Current reduced monomial:", (currentCoefficient * \

            #                                    currentMonomial)

            currentPolynomial += (currentCoefficient * currentMonomial)

            #print "Current polynomial:", currentPolynomial

        # End if

    # End for colIndex.

    #print "Type of the current polynomial:", type(currentPolynomial)

    return(currentPolynomial)

# End slz_compute_reduced_polynomial

#

def slz_compute_reduced_polynomials(reducedMatrix,

                                        knownMonomials,

                                        var1,

                                        var1Bound,

                                        var2,

                                        var2Bound):

    """

    Legacy function, use slz_compute_reduced_polynomials_list

    """

    return(slz_compute_reduced_polynomials_list(reducedMatrix,

                                                knownMonomials,

                                                var1,

                                                var1Bound,

                                                var2,

                                                var2Bound)

    )

def slz_compute_reduced_polynomials_list(reducedMatrix,

                                        knownMonomials,

                                        var1,

                                        var1Bound,

                                        var2,

                                        var2Bound):

    """

print