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

def run_SLZ_v01(inputFunction,

                inputLowerBound,

                inputUpperBound,

                alpha,

                degree,

                precision,

                emin,

                emax,

                targetHardnessToRound,

                debug = False):

        #### For polynomials

        basisConstructionTime         = cputime()

        ##### To a polynomial with rational coefficients with rational arguments

        ratRatP = slz_float_poly_of_float_to_rat_poly_of_rat_pow_two(floatP)

        ##### To a polynomial with rational coefficients with integer arguments

        ratIntP = \

            slz_rat_poly_of_rat_to_rat_poly_of_int(ratRatP, precision)

        #####  Ultimately a polynomial with integer coefficients with integer 

        #      arguments.

        coppersmithTuple = \

            slz_rat_poly_of_int_to_poly_for_coppersmith(ratIntP, 

                                                        precision, 

                                                        targetHardnessToRound, 

                                                        i, t)

        #### Recover Coppersmith information.

        intIntP = coppersmithTuple[0]

        N = coppersmithTuple[1]

        nAtAlpha = N^alpha

        tBound = coppersmithTuple[2]

        leastCommonMultiple = coppersmithTuple[3]

        iBound = max(abs(intLb),abs(intUb))

        basisConstructionsFullTime        += cputime(basisConstructionTime)

        basisConstructionsCount           += 1

        reductionTime                     = cputime()

        # Compute the reduced polynomials.

        ccReducedPolynomialsList =  \

            slz_compute_coppersmith_reduced_polynomials(intIntP, 

                                                        alpha, 

                                                        N, 

                                                        iBound, 

                                                        tBound)

        if ccReducedPolynomialsList is None:

            raise Exception("Reduction failed.")

        reductionsFullTime    += cputime(reductionTime)

        reductionsCount       += 1

        if len(ccReducedPolynomialsList) < 2:

            print "Nothing to form resultants with."

            print

            coppCondFailedCount += 1

            coppCondFailed = True

            ##### Apply a different shrink factor according to 

            #  the number of complient polynomials.

            if len(ccReducedPolynomialsList) == 0:

                ub  = lb + bw / 4

            else: # At least one complient polynomial.

                ub = lb + bw / 2

            if ub > sdub:

                ub = sdub

            if lb == ub:

                raise Exception("Cant shrink interval \

                anymore to get Coppersmith condition.")

            nbw = 0

            continue

        #### We have at least two polynomials.

        #   Let us try to compute resultants.

        resultantsComputationTime      = cputime()

        resultantsInTTuplesList = []

        for polyOuterIndex in xrange(0, len(ccReducedPolynomialsList) - 1):

            for polyInnerIndex in xrange(polyOuterIndex+1, 

                                         len(ccReducedPolynomialsList)):

                resultantTuple = \

                slz_resultant_tuple(ccReducedPolynomialsList[polyOuterIndex],

                                ccReducedPolynomialsList[polyInnerIndex],

                                t)

                if len(resultantTuple) > 2:                    

                    #print resultantTuple[2]

                    resultantsInTTuplesList.append(resultantTuple)

                else:

                    print "No non nul resultant"

        print len(resultantsInTTuplesList), "resultant(s) in t tuple(s) created."

        resultantsComputationsFullTime += cputime(resultantsComputationTime)

        resultantsComputationsCount    += 1

        if len(resultantsInTTuplesList) == 0:

            print "Only null resultants, shrinking interval."

            resultCondFailed      =  True

            resultCondFailedCount += 1

            ### Shrink interval for next iteration.

            ub = lb + bw / 2

            if ub > sdub:

                ub = sdub

            nbw = 0

            continue

        #### Compute roots.

        reducedPolynomialsRootsSet = set()

        ##### Solve in the second variable since resultants are in the first

        #     variable.

        for resultantInTTuple in resultantsInTTuplesList:

            currentResultant = resultantInTTuple[2]

            ##### If the resultant degree is not at least 1, there are no roots.

            if currentResultant.degree() < 1:

                print "Resultant is constant:", currentResultant

                continue # Next resultantInTTuple

            ##### Compute i roots

            iRootsList = Zi(currentResultant).roots()

            ##### For each iRoot, compute the corresponding tRoots and check 

            #     them in the input polynomial.

            for iRoot in iRootsList:

                ####### Roots returned by roots() are (value, multiplicity) 

                #       tuples.

                #print "iRoot:", iRoot

                ###### Use the tRoot against each polynomial, alternatively.

                for indexInTuple in range(0,2):

                    currentPolynomial = resultantInTTuple[indexInTuple]

                    ####### If the polynomial is univariate, just drop it.

                    if len(currentPolynomial.variables()) < 2:

                        print "    Current polynomial is not in two variables."

                        continue # Next indexInTuple

                    tRootsList = \

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

                    ####### The tRootsList can be empty, hence the test.

                    if len(tRootsList) == 0:

                        print "    No t root."

                        continue # Next indexInTuple

                    for tRoot in tRootsList:

                        reducedPolynomialsRootsSet.add((iRoot[0], tRoot[0]))

        # End of roots computation

    ## Prepare for results.

    intervalResultsList = []

    intervalResultsList.append((lb, ub))

    ## Check roots.

    rootsResultsList = []

    rootsComputationTime        = cputime()

    for root in reducedPolynomialsRootsSet:

        specificRootResultsList = []

        failingBounds = []

        intIntPdivN = intIntP(root[0], root[1]) / N

        if int(intIntPdivN) != intIntPdivN:

            continue # Next root

        # Root qualifies for modular equation, test it for hardness to round.

        hardToRoundCaseAsFloat = RRR((icAsInt + root[0]) / toIntegerFactor)

        #print "Before unscaling:", hardToRoundCaseAsFloat.n(prec=precision)

        #print scalingFunction

        scaledHardToRoundCaseAsFloat = scalingFunction(hardToRoundCaseAsFloat) 

        print "Candidate HTRNc at x =", scaledHardToRoundCaseAsFloat.n().str(base=2),

        if slz_is_htrn(scaledHardToRoundCaseAsFloat,

                       f,

                       2^-(targetHardnessToRound),

                       RRR):

            print hardToRoundCaseAsFloat, "is HTRN case."

            if lb <= hardToRoundCaseAsFloat and hardToRoundCaseAsFloat <= ub:

                print "Found in interval."

            else:

                print "Found out of interval."

            specificRootResultsList.append(hardToRoundCaseAsFloat.n().str(base=2))

            # Check the root is in the bounds

            if abs(root[0]) > iBound or abs(root[1]) > tBound:

                print "Root", root, "is out of bounds."

                if abs(root[0]) > iBound:

                    print "root[0]:", root[0]

                    print "i bound:", iBound

                    failingBounds.append('i')

                    failingBounds.append(root[0])

                    failingBounds.append(iBound)

                if abs(root[1]) > tBound:

                    print "root[1]:", root[1]

                    print "t bound:", tBound

                    failingBounds.append('t')

                    failingBounds.append(root[1])

                    failingBounds.append(tBound)

            if len(failingBounds) > 0:

                specificRootResultsList.append(failingBounds)

        else: # From slz_is_htrn...

            print "is not an HTRN case."

        if len(specificRootResultsList) > 0:

            rootsResultsList.append(specificRootResultsList)

    rootsComputationsFullTime       =   cputime(rootsComputationTime)

    rootsComputationsCount          +=  1

    if len(rootsResultsList) > 0:

        intervalResultsList.append(rootsResultsList)

    ## An intervalResultsList has at least the bounds.

    globalResultsList.append(intervalResultsList)   

# End runSLZ-v01

run_SLZ_v01(inputFunction=func, 

            inputLowerBound = 1/4, 

            inputUpperBound = RRR(1/2) - RRR(1/4).ulp(), 

            alpha = 2, 

            degree = 10, 

            precision = 53, 

            emin = -1022, 

            emax = 1023, 

            targetHardnessToRound =  precision+50, 

            debug = True)