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

r"""

Sage core functions needed for the implementation of SLZ.

AUTHORS:

- S.T. (2013-08): initial version

Examples:

TODO::

"""

sys.stderr.write("sageSLZ loading...\n")

#

import inspect

#

def slz_compute_binade(number):

    """"

    For a given number, compute the "binade" that is integer m such that

    2^m <= number < 2^(m+1). If number == 0 return None.

    """

    # Checking the parameter.

    # The exception construction is used to detect if number is a RealNumber

    # since not all numbers have

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

    try:

        classTree = [number.__class__] + number.mro()

        # If the number is not a RealNumber (or offspring thereof) try

        # to transform it.

        if not sage.rings.real_mpfr.RealNumber in classTree:

            numberAsRR = RR(number)

        else:

            numberAsRR = number

    except AttributeError:

        return None

    # Zero special case.

    if numberAsRR == 0:

        return RR(-infinity)

    else:

        realField           = numberAsRR.parent()

        numberLog2          = numberAsRR.abs().log2()

        floorNumberLog2     = floor(numberLog2)

        ## Do not get caught by rounding of log2() both ways.

        ## When numberLog2 is an integer, compare numberAsRR

        #  with 2^numberLog2.

        if floorNumberLog2 == numberLog2:

            if numberAsRR.abs() < realField(2^floorNumberLog2):

                return floorNumberLog2 - 1

            else:

                return floorNumberLog2

        else:

            return floorNumberLog2

# End slz_compute_binade

#

def slz_compute_binade_bounds(number, emin, emax=sys.maxint):

    """

    For given "real number", compute the bounds of the binade it belongs to.

    NOTE::

        When number >= 2^(emax+1), we return the "fake" binade

        [2^(emax+1), +infinity]. Ditto for number <= -2^(emax+1)

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

        this case from that of "really" invalid arguments.

    """

    # Check the parameters.

    # RealNumbers or RealNumber offspring only.

    # The exception construction is necessary since not all objects have

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

    try:

        classTree = [number.__class__] + number.mro()

        if not sage.rings.real_mpfr.RealNumber in classTree:

            return None

    except AttributeError:

        return None

    # Non zero negative integers only for emin.

    if emin >= 0 or int(emin) != emin:

        return None

    # Non zero positive integers only for emax.

    if emax <= 0 or int(emax) != emax:

        return None

    precision = number.precision()

    RF  = RealField(precision)

    if number == 0:

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

    # A more precise RealField is needed to avoid unwanted rounding effects

    # when computing number.log2().

    RRF = RealField(max(2048, 2 * precision))

    # number = 0 special case, the binade bounds are

    # [0, 2^emin - 2^(emin-precision)]

    # Begin general case

    l2 = RRF(number).abs().log2()

    # Another special one: beyond largest representable -> "Fake" binade.

    if l2 >= emax + 1:

        if number > 0:

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

        else:

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

    # Regular case cont'd.

    offset = int(l2)

    # number.abs() >= 1.

    if l2 >= 0:

        if number >= 0:

            lb = RF(2^offset)

            ub = RF(2^(offset + 1) - 2^(-precision+offset+1))

        else: #number < 0

            lb = -RF(2^(offset + 1) - 2^(-precision+offset+1))

            ub = -RF(2^offset)

    else: # log2 < 0, number.abs() < 1.

        if l2 < emin: # Denormal

           # print "Denormal:", l2

            if number >= 0:

                lb = RF(0)

                ub = RF(2^(emin)) - RF(2^(emin-precision))

            else: # number <= 0

                lb = - RF(2^(emin)) + RF(2^(emin-precision))

                ub = RF(0)

        elif l2 > emin: # Normal number other than +/-2^emin.

            if number >= 0:

                if int(l2) == l2:

                    lb = RF(2^(offset))

                    ub = RF(2^(offset+1)) - RF(2^(-precision+offset+1))

                else:

                    lb = RF(2^(offset-1))

                    ub = RF(2^(offset)) - RF(2^(-precision+offset))

            else: # number < 0

                if int(l2) == l2: # Binade limit.

                    lb = -RF(2^(offset+1) - 2^(-precision+offset+1))

                    ub = -RF(2^(offset))

                else:

                    lb = -RF(2^(offset) - 2^(-precision+offset))

                    ub = -RF(2^(offset-1))

        else: # l2== emin, number == +/-2^emin

            if number >= 0:

                lb = RF(2^(offset))

                ub = RF(2^(offset+1)) - RF(2^(-precision+offset+1))

            else: # number < 0

                lb = -RF(2^(offset+1) - 2^(-precision+offset+1))

                ub = -RF(2^(offset))

    return (lb, ub)

# End slz_compute_binade_bounds

#

def slz_compute_coppersmith_reduced_polynomials(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.

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

    reducedMatrix = matrixToReduce.LLL(fp=None)

    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

#

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

#

def slz_compute_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 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():

        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

        # End if

    # End for.

    if len(ccReducedPolynomialsList) < 2: # Insufficient reduction.

        print "Less than 2 Coppersmith condition compliant vectors."

        print "Extra reduction starting..."

        reducedMatrixStep2 = reducedMatrixStep1.LLL(algorithm='fpLLL:wrapper')

        ## Create a fresh reduced polynomials list.

        ccReducedPolynomialsList = []

        for row in reducedMatrixStep2.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)

        # End for.

    else: # At least 2 small norm enough vectors from reducedMatrixStep2.

        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

#

def slz_compute_weak_coppersmith_reduced_polynomials_proj_02(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_02(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_02

#

def slz_compute_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 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():

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

        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

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: