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

def spo_add_polynomial_coeffs_to_matrix(pMonomials, 

                                        pCoefficients, 

                                        knownMonomials, 

                                        protoMatrixRows, 

                                        columnsWidth=0):

    """

    For a given polynomial (under the form of monomials and coefficents lists),

    add the coefficients of the protoMatrix (a list of proto matrix rows).

    Coefficients are added to the protoMatrix row in the order imposed by the 

    monomials discovery list (the knownMonomials list) built as construction

    goes on. 

    As a bonus data can be printed out for a visual check.

    pMonomials     : the list of the monomials coming form some polynomial;

    pCoefficients  : the list of the corresponding coefficients to add to

                     the protoMatrix in the exact same order as the monomials;

    knownMonomials : the list of the already knonw monomials;

    protoMatrixRows: a list of lists, each one holding the coefficients of the 

                     monomials

    columnWith     : the width, in characters, of the displayed column ; if 0, 

                     do not display anything.

    """

    # We have started with the smaller degrees in the first variable.

    pMonomials.reverse()

    pCoefficients.reverse()

    # New empty proto matrix row.

    protoMatrixRowCoefficients = []

    # We work according to the order of the already known monomials

    # No known monomials yet: add the pMonomials to knownMonomials 

    # and add the coefficients to the proto matrix row.

    if len(knownMonomials) == 0: 

        for pmIdx in xrange(0, len(pMonomials)):

            knownMonomials.append(pMonomials[pmIdx])

            protoMatrixRowCoefficients.append(pCoefficients[pmIdx])

            if columnsWidth != 0:

                monomialAsString = str(pCoefficients[pmIdx]) + " " + \

                                   str(pMonomials[pmIdx])

                print monomialAsString, " " * \

                      (columnsWidth - len(monomialAsString)),

    # There are some known monomials. We search for them in pMonomials and 

    # add their coefficients to the proto matrix row.

    else: 

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

            # We lazily use an exception here since pMonomials.index() function

            # may fail throwing the ValueError exception.

            try:

                indexInPmonomials = \

                    pMonomials.index(knownMonomials[knownMonomialIndex])

                if columnsWidth != 0:

                    monomialAsString = str(pCoefficients[indexInPmonomials]) + \

                        " " + str(knownMonomials[knownMonomialIndex])

                    print monomialAsString, " " * \

                        (columnsWidth - len(monomialAsString)),

                # Add the coefficient to the proto matrix row and delete the \

                # known monomial from the current pMonomial list 

                #(and the corresponding coefficient as well).

                protoMatrixRowCoefficients.append(pCoefficients[indexInPmonomials])

                del pMonomials[indexInPmonomials]

                del pCoefficients[indexInPmonomials]

            # The knownMonomials element is not in pMonomials

            except ValueError:   

                protoMatrixRowCoefficients.append(0)

                if columnsWidth != 0:

                    monomialAsString = "0" + " "+ \

                        str(knownMonomials[knownMonomialIndex])

                    print monomialAsString, " " * \

                        (columnsWidth - len(monomialAsString)),

        # End for knownMonomialKey loop. 

        # We now append the remaining monomials of pMonomials to knownMonomials 

        # and the corresponding coefficients to proto matrix row.

        for pmIdx in xrange(0, len(pMonomials)):

            knownMonomials.append(pMonomials[pmIdx])

            protoMatrixRowCoefficients.append(pCoefficients[pmIdx])

            if columnsWidth != 0:

                monomialAsString = str(pCoefficients[pmIdx]) + " " \

                    + str(pMonomials[pmIdx])

                print monomialAsString, " " * \

                    (columnsWidth - len(monomialAsString)),

        # End for pmIdx loop.

    # Add the new list row elements to the proto matrix.

    protoMatrixRows.append(protoMatrixRowCoefficients)

    if columnsWidth != 0:

        print    

# End spo_add_polynomial_coeffs_to_matrix

def spo_expression_as_string(powI, powT, powP, alpha):

    """

    Computes a string version of the i^k + t^l + p^m + N^n expression for

    output.

    """

    expressionAsString =""

    if powI != 0:

        expressionAsString += "i^" + str(powI)

    if powT != 0:

        if len(expressionAsString) != 0:

            expressionAsString += " * "

        expressionAsString += "t^" + str(powT)

    if powP != 0:

        if len(expressionAsString) != 0:

            expressionAsString += " * "

        expressionAsString += "p^" + str(powP)

    if (alpha - powP) != 0 :

        if len(expressionAsString) != 0:

            expressionAsString += " * "

        expressionAsString += "N^" + str(alpha - powP)

    return(expressionAsString)

# End spo_expression_as_string.

    The matrix is such as those found in Boneh-Durphee and Stehl?.

    x = functionSa.variables()[0]

    # Reassert f as a function (an not a mere expression).

        slz_interval_scaling_expression(domainBoundsIntervalSa, x)

    domainScalingFunction(x) = invDomainScalingExpressionSa

    scaledLowerBoundSa = domainScalingFunction(lowerBoundSa).n()

    scaledUpperBoundSa = domainScalingFunction(upperBoundSa).n()

        slz_interval_scaling_expression(imageBoundsIntervalSa, x)

def slz_get_intervals_and_polynomials(functionSa, degreeSa, 

    x = functionSa.variables()[0] # Actual variable name can be anything.

    (fff, scaledLowerBoundSa, scaledUpperBoundSa, \

            scaledLowerBoundImageSa, scaledUpperBoundImageSa) = \

                slz_compute_scaled_function(functionSa, \

                                            lowerBoundSa, \

                                            upperBoundSa, \

                                            floatingPointPrecSa)

def slz_interval_scaling_expression(boundsInterval, expVar):

            return((scalingCoeff * expVar, 

                    invScalingCoeff * expVar))

            return((scalingCoeff * expVar + scalingOffset,

                    1/scalingCoeff * expVar + 3))

            return((scalingCoeff * expVar, 

                    1/scalingCoeff * expVar))

            return((scalingCoeff * expVar + scalingOffset,

                    1/scalingCoeff * expVar + 3))

def slz_rat_poly_of_int_to_poly_for_coppersmith(ratPolyOfInt, 

                                                precision,

                                                targetHardnessToRound,

                                                variable1,

                                                variable2):

    """

    Creates a new polynomial with integer coefficients for use with the

    Coppersmith method.

    A the same time it computes :

    - 2^K (N);

    - 2^k

    - lcm

    """

    # Create a new integer polynomial ring.

    IP = PolynomialRing(ZZ, name=str(variable1) + "," + str(variable2))

    # Coefficients are issued in the increasing power order.

    ratPolyCoefficients = ratPolyOfInt.coefficients()

    # Build the list of number we compute the lcmm of.

    coefficientDenominators = sro_denominators(ratPolyCoefficients)

    coefficientDenominators.append(2^precision)

    coefficientDenominators.append(2^(targetHardnessToRound + 1))

    leastCommonMultiple = sro_lcmm(coefficientDenominators)

    # Compute the lcm

    leastCommonMultiple = sro_lcmm(coefficientDenominators)

    # Compute the expression corresponding to the new polynomial

    coefficientNumerators =  sro_numerators(ratPolyCoefficients)

    print coefficientNumerators

    polynomialExpression = 0

    power = 0

    # Iterate over two lists at the same time, stop when the shorter is

    # exhausted.

    for numerator, denominator in \

                            zip(coefficientNumerators, coefficientDenominators):

        multiplicator = leastCommonMultiple / denominator 

        newCoefficient = numerator * multiplicator

        polynomialExpression += newCoefficient * variable1^power

        power +=1

    polynomialExpression += - variable2

    return (IP(polynomialExpression),

            leastCommonMultiple / 2^precision, # 2^K or N.

            leastCommonMultiple / 2 ^(targetHardnessToRound + 1), # tBound

            leastCommonMultiple)

# End slz_ratPoly_of_int_to_poly_for_coppersmith

def sro_denominators(rationalList = None):

# End sro_denominators

def sro_lcmm(rationalList = None):

# End sro_lcmm

def sro_numerators(rationalList = None):

    return(numeratorsList)

# End sro_numerators

/* Identique ? abbr */

/* L'appel de note est r?alis? par un ?l?ment "a" de classe callNote */

/* Le retour de note est r?alis? par un ?l?ment "a" de classe retFromNote */

</style>