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

def slz_compute_initial_lattice_matrix(inputPolynomial,

                                       alpha,

                                       N,

                                       iBound,

                                       tBound):

    """

    For a given set of arguments (see below), compute the initial lattice

    that could be reduced. 

    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})

    polynomialsList = \

        spo_polynomial_to_polynomials_list_8(initialPolynomial,

                                             alpha,

                                             N,

                                             iBound,

                                             tBound,

                                             0)

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

    return matrixToReduce

# End slz_compute_initial_lattice_matrix.

                                        sollyaPrecSa=None, debug=False):

    """

    Under the assumptions listed for slz_get_intervals_and_polynomials, compute

    a polynomial that approximates the function on a an interval starting

    at lowerBoundSa and finishing at a value that guarantees that the polynomial

    approximates with the expected precision.

    The interval upper bound is lowered until the expected approximation 

    precision is reached.

    The polynomial, the bounds, the center of the interval and the error

    are returned.

    OUTPUT:

    A tuple made of 4 Sollya objects:

    - a polynomial;

    - an range (an interval, not in the sense of number given as an interval);

    - the center of the interval;

    - the maximum error in the approximation of the input functionSo by the

      output polynomial ; this error <= approxAccurSaS.

    """

    #print"In slz_compute_polynomial_and_interval..."

    ## Superficial argument check.

    if lowerBoundSa > upperBoundSa:

        return None

    ## Change Sollya precision, if requested.

    if not sollyaPrecSa is None:

        sollyaPrecSo = pobyso_get_prec_so()

        pobyso_set_prec_sa_so(sollyaPrecSa)

    else:

        sollyaPrecSa = pobyso_get_prec_so_sa()

        sollyaPrecSo = None

    RRR = lowerBoundSa.parent()

    intervalShrinkConstFactorSa = RRR('0.9')

    absoluteErrorTypeSo = pobyso_absolute_so_so()

    currentRangeSo = pobyso_bounds_to_range_sa_so(lowerBoundSa, upperBoundSa)

    currentUpperBoundSa = upperBoundSa

    currentLowerBoundSa = lowerBoundSa

    # What we want here is the polynomial without the variable change, 

    # since our actual variable will be x-intervalCenter defined over the 

    # domain [lowerBound-intervalCenter , upperBound-intervalCenter]. 

    (polySo, intervalCenterSo, maxErrorSo) = \

        pobyso_taylor_expansion_no_change_var_so_so(functionSo, degreeSo, 

                                                    currentRangeSo, 

                                                    absoluteErrorTypeSo)

    maxErrorSa = pobyso_get_constant_as_rn_with_rf_so_sa(maxErrorSo)

    while maxErrorSa > approxAccurSa:

        print "++Approximation error:", maxErrorSa.n()

        sollya_lib_clear_obj(polySo)

        sollya_lib_clear_obj(intervalCenterSo)

        sollya_lib_clear_obj(maxErrorSo)

        # Very empirical shrinking factor.

        shrinkFactorSa = 1 /  (maxErrorSa/approxAccurSa).log2().abs()

        print "Shrink factor:", \

              shrinkFactorSa.n(), \

              intervalShrinkConstFactorSa

        print

        #errorRatioSa = approxAccurSa/maxErrorSa

        #print "Error ratio: ", errorRatioSa

        # Make sure interval shrinks.

        if shrinkFactorSa > intervalShrinkConstFactorSa:

            actualShrinkFactorSa = intervalShrinkConstFactorSa

            #print "Fixed"

        else:

            actualShrinkFactorSa = shrinkFactorSa

            #print "Computed",shrinkFactorSa,maxErrorSa

            #print shrinkFactorSa, maxErrorSa

        #print "Shrink factor", actualShrinkFactorSa

        currentUpperBoundSa = currentLowerBoundSa + \

                                (currentUpperBoundSa - currentLowerBoundSa) * \

                                actualShrinkFactorSa

        #print "Current upper bound:", currentUpperBoundSa

        sollya_lib_clear_obj(currentRangeSo)

        # Check what is left with the bounds.

        if currentUpperBoundSa <= currentLowerBoundSa or \

              currentUpperBoundSa == currentLowerBoundSa.nextabove():

            sollya_lib_clear_obj(absoluteErrorTypeSo)

            print "Can't find an interval."

            print "Use either or both a higher polynomial degree or a higher",

            print "internal precision."

            print "Aborting!"

            if not sollyaPrecSo is None:

                pobyso_set_prec_so_so(sollyaPrecSo)

                sollya_lib_clear_obj(sollyaPrecSo)

            return None

        currentRangeSo = pobyso_bounds_to_range_sa_so(currentLowerBoundSa, 

                                                      currentUpperBoundSa)

        # print "New interval:",

        # pobyso_autoprint(currentRangeSo)

        #print "Second Taylor expansion call."

        (polySo, intervalCenterSo, maxErrorSo) = \

            pobyso_taylor_expansion_no_change_var_so_so(functionSo, degreeSo, 

                                                        currentRangeSo, 

                                                        absoluteErrorTypeSo)

        #maxErrorSa = pobyso_get_constant_as_rn_with_rf_so_sa(maxErrorSo, RRR)

        #print "Max errorSo:",

        #pobyso_autoprint(maxErrorSo)

        maxErrorSa = pobyso_get_constant_as_rn_with_rf_so_sa(maxErrorSo)

        #print "Max errorSa:", maxErrorSa

        #print "Sollya prec:",

        #pobyso_autoprint(sollya_lib_get_prec(None))

    # End while

    sollya_lib_clear_obj(absoluteErrorTypeSo)

    itpSo           = pobyso_constant_from_int_sa_so(floor(sollyaPrecSa/3))

    ftpSo           = pobyso_constant_from_int_sa_so(floor(2*sollyaPrecSa/3))

    maxPrecSo       = pobyso_constant_from_int_sa_so(sollyaPrecSa)

    approxAccurSo   = pobyso_constant_sa_so(RR(approxAccurSa))

    if debug:

        print "About to call polynomial rounding with:"

        print "polySo: ",           ; pobyso_autoprint(polySo)

        print "functionSo: ",       ; pobyso_autoprint(functionSo)

        print "intervalCenterSo: ", ; pobyso_autoprint(intervalCenterSo)

        print "currentRangeSo: ",   ; pobyso_autoprint(currentRangeSo)

        print "itpSo: ",            ; pobyso_autoprint(itpSo)

        print "ftpSo: ",            ; pobyso_autoprint(ftpSo)

        print "maxPrecSo: ",        ; pobyso_autoprint(maxPrecSo)

        print "approxAccurSo: ",    ; pobyso_autoprint(approxAccurSo)

    (roundedPolySo, roundedPolyMaxErrSo) = \

    pobyso_polynomial_coefficients_progressive_round_so_so(polySo,

                                                           functionSo,

                                                           intervalCenterSo,

                                                           currentRangeSo,

                                                           itpSo,

                                                           ftpSo,

                                                           maxPrecSo,

                                                           approxAccurSo)

    sollya_lib_clear_obj(polySo)

    sollya_lib_clear_obj(maxErrorSo)

    sollya_lib_clear_obj(itpSo)

    sollya_lib_clear_obj(ftpSo)

    sollya_lib_clear_obj(approxAccurSo)

    if not sollyaPrecSo is None:

        pobyso_set_prec_so_so(sollyaPrecSo)

        sollya_lib_clear_obj(sollyaPrecSo)

    if debug:

        print "1: ", ; pobyso_autoprint(roundedPolySo)

        print "2: ", ; pobyso_autoprint(currentRangeSo)

        print "3: ", ; pobyso_autoprint(intervalCenterSo)

        print "4: ", ; pobyso_autoprint(roundedPolyMaxErrSo)

    return (roundedPolySo, currentRangeSo, intervalCenterSo, roundedPolyMaxErrSo)

# End slz_compute_polynomial_and_interval_01

def slz_compute_polynomial_and_interval_02(functionSo, degreeSo, lowerBoundSa, 

                                        upperBoundSa, approxAccurSa, 

# End slz_compute_polynomial_and_interval_02