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

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

    (reducedMatrix1, reductionMatrix1) = \

         slz_reduce_lll_proj(matrixToReduce, 2^16)

    #print "Reduced matrix:"

    matrixIsReducedEnough = reducedMatrix1.is_LLL_reduced()

    #

    if not matrixIsReducedEnough:

        reducedMatrix = reducedMatrix1.LLL(algorithm='fpLLL:wrapper')

        isLLLReduced  = reducedMatrix.is_LLL_reduced()

    else:

        reducedMatrix = reducedMatrix1

        isLLLReduced  = matrixIsReducedEnough

    #for row in reducedMatrix.rows():

    #    print row

    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_proj

#

#

def slz_pm1():

    """

    Compute a uniform RV in {-1, 1}.

    """

    ## function getrandbits(N) generates a long int with N random bits.

    return getrandbits(1) * 2-1

# End slz_pm1.

#

def slz_random_proj_pm1(r, c):

    """

    r x c matrix with \pm 1 ({-1, 1}) coefficients

    """

    M = matrix(r, c)

    for i in range(0, r):

        for j in range (0, c):

            M[i,j] = slz_pm1()

    return M

# End random_proj_pm1.

#

def slz_random_proj_uniform(n, r, c):

    """

    r x c integer matrix with uniform n-bit integer coefficients

    """

    M = matrix(r, c)

    for i in range(0, r):

        for j in range (0, c):

            M[i,j] = slz_uniform(n)

    return M       

# End slz_random_proj_uniform.

#

def slz_reduce_lll_proj(matToReduce, n):

    """

    Compute the transformation matrix that realizes an LLL reduction on

    the random uniform projected matrix.

    Return both the initial matrix "reduced" by the transformation matrix and

    the transformation matrix itself.

    """

    ## Compute the projected matrix.

    matProjector = slz_random_proj_uniform(n,

                                           matToReduce.ncols(),

                                           matToReduce.nrows())

    matProjected = matToReduce * matProjector

    ## Build the argument matrix for LLL in such a way that the transformation

    #  matrix is also returned. This matrix is obtained at almost no extra

    # cost. An identity matrix must be appended to 

    #  the left of the initial matrix. The transformation matrix will

    # will be recovered at the same location from the returned matrix .

    idMat = identity_matrix(matProjected.nrows())

    augmentedMatToReduce = idMat.augment(matProjected)

    reducedProjMat = \

        augmentedMatToReduce.LLL(algorithm='fpLLL:wrapper')

    ## Recover the transformation matrix (the left part of the reduced matrix). 

    #  We discard the reduced matrix itself.

    transMat = reducedProjMat.submatrix(0,

                                        0,

                                        reducedProjMat.nrows(),

                                        reducedProjMat.nrows())

    ## Return the initial matrix "reduced" and the transformation matrix tuple.

    return (transMat * matToReduce, transMat)

# End  slz_reduce_lll_proj.

#

def slz_uniform(n):

    """

    Compute a uniform RV in {-1, 1}.

    """

    ## function getrandbits(n) generates a long int with n random bits.

    return getrandbits(n) - 2^(n-1)

# End slz_uniform.

#