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

        with interval [-infinity, -2^(emax+1)]. We want to distinguish

        this case from that of "really" invalid arguments.

    # RealNumbers or RealNumber offspring only.

    # The execption construction is necessary since not all objects have

    # the mro() method. sage.rings.real_mpfr.RealNumber do.

    if number == 0:

        return (RF(0),RF(2^(emin)) - RF(2^(emin-precision)))

            return (RF(2^(emax+1)), RF(+infinity) )

        return set()

            #print l2Norm.n()

            #print l2Norm.n() , ">", nAtAlpha

        print "Less than 2 Coppersmith condition compliant vectors."

    #print ccReducedPolynomialsList

    ccReducedPolynomialsList = \

        slz_compute_coppersmith_reduced_polynomials (inputPolynomial,

                                                     alpha,

                                                     N,

                                                     iBound,

                                                     tBound)

    if len(ccReducedPolynomialsList) == 0:

        return set()   

def slz_compute_integer_polynomial_modular_roots_2(inputPolynomial,

                                                 alpha,

                                                 N,

                                                 iBound,

                                                 tBound):

    """

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

    roots, if any.

    This version differs in the way resultants are computed.   

    """

    # Arguments check.

    if iBound == 0 or tBound == 0:

        return set()

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

    ccReducedPolynomialsList = \

        slz_compute_coppersmith_reduced_polynomials (inputPolynomial,

                                                     alpha,

                                                     N,

                                                     iBound,

                                                     tBound)

    if len(ccReducedPolynomialsList) == 0:

        return set()   

    ## 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.

    resultantsInTTuplesList = []

    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?).

            resultantInT = \

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

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

            #print "Resultant", resultantInT

            # Test algebraic independence.

            if not resultantInT.is_zero():

                resultantsInTTuplesList.append((ccReducedPolynomialsList[polyOuterIndex],

                                                 ccReducedPolynomialsList[polyInnerIndex],

                                                 resultantInT))

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

    # independent polynomials pair. Give up!

    if len(resultantsInTTuplesList) == 0:

        return set()

    #print resultantsInITuplesList

    # 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 resultantInTTuple in resultantsInTTuplesList:

        iRootsList = Zi(resultantInTTuple[2]).roots()

        # For each iRoot, compute the corresponding tRoots and check 

        # them in the input polynomial.

        for iRoot in iRootsList:

            #print "iRoot:", iRoot

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

            tRootsList = \

                Zt(resultantInTTuple[0].subs({resultantInTTuple[0].variables()[0]:iRoot[0]})).roots()

            print tRootsList

            # The tRootsList can be empty, hence the test.

            if len(tRootsList) != 0:

                for tRoot in tRootsList:

                    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_2.

#

    Compute a polynomial from a single reduced matrix row.

    all the polynomials  from the full matrix (even those built from rows 

    that do no verify the Coppersmith condition) as this may involves 

    expensive operations over (large) integer.