Révision 80 pobysoPythonSage/src/sageSLZ/sageSLZ.sage
| sageSLZ.sage (revision 80) | ||
|---|---|---|
| 58 | 58 |
# End slz_compute_polynomial_and_interval |
| 59 | 59 |
|
| 60 | 60 |
def slz_compute_scaled_function(functionSa, \ |
| 61 |
variableNameSa, \ |
|
| 62 | 61 |
lowerBoundSa, \ |
| 63 | 62 |
upperBoundSa, \ |
| 64 | 63 |
floatingPointPrecSa): |
| ... | ... | |
| 72 | 71 |
[3]: the scaled image lower bound |
| 73 | 72 |
[4]: the scaled image upper bound |
| 74 | 73 |
""" |
| 75 |
x = var(variableNameSa) |
|
| 74 |
x = functionSa.variables()[0] |
|
| 75 |
# Reassert f as a function (an not a mere expression). |
|
| 76 |
|
|
| 76 | 77 |
# Scalling the domain -> [1,2[. |
| 77 | 78 |
boundsIntervalRifSa = RealIntervalField(floatingPointPrecSa) |
| 78 | 79 |
domainBoundsIntervalSa = boundsIntervalRifSa(lowerBoundSa, upperBoundSa) |
| 79 | 80 |
(domainScalingExpressionSa, invDomainScalingExpressionSa) = \ |
| 80 |
slz_interval_scaling_expression(domainBoundsIntervalSa, variableNameSa)
|
|
| 81 |
slz_interval_scaling_expression(domainBoundsIntervalSa, x)
|
|
| 81 | 82 |
print "domainScalingExpression for argument :", domainScalingExpressionSa |
| 82 | 83 |
print "f: ", f |
| 83 | 84 |
ff = f.subs({x : domainScalingExpressionSa})
|
| 84 | 85 |
#ff = f.subs_expr(x==domainScalingExpressionSa) |
| 85 |
scaledLowerBoundSa = invDomainScalingExpressionSa(lowerBoundSa).n() |
|
| 86 |
scaledUpperBoundSa = invDomainScalingExpressionSa(upperBoundSa).n() |
|
| 86 |
domainScalingFunction(x) = invDomainScalingExpressionSa |
|
| 87 |
scaledLowerBoundSa = domainScalingFunction(lowerBoundSa).n() |
|
| 88 |
scaledUpperBoundSa = domainScalingFunction(upperBoundSa).n() |
|
| 87 | 89 |
print 'ff:', ff, "- Domain:", scaledLowerBoundSa, scaledUpperBoundSa |
| 88 | 90 |
# |
| 89 | 91 |
# Scalling the image -> [1,2[. |
| ... | ... | |
| 96 | 98 |
print 'ff:', ff, '- Image:', flbSa, fubSa, imageBinadeBottomSa |
| 97 | 99 |
imageBoundsIntervalSa = boundsIntervalRifSa(flbSa, fubSa) |
| 98 | 100 |
(imageScalingExpressionSa, invImageScalingExpressionSa) = \ |
| 99 |
slz_interval_scaling_expression(imageBoundsIntervalSa, variableNameSa)
|
|
| 101 |
slz_interval_scaling_expression(imageBoundsIntervalSa, x)
|
|
| 100 | 102 |
iis = invImageScalingExpressionSa.function(x) |
| 101 | 103 |
fff = iis.subs({x:ff})
|
| 102 | 104 |
print "fff:", fff, |
| ... | ... | |
| 110 | 112 |
return(polynomialRing(polyOfFloat)) |
| 111 | 113 |
# End slz_float_poly_of_float_to_rat_poly_of_rat |
| 112 | 114 |
|
| 113 |
def slz_get_intervals_and_polynomials(functionSa, variableNameSa, degreeSa,
|
|
| 115 |
def slz_get_intervals_and_polynomials(functionSa, degreeSa, |
|
| 114 | 116 |
lowerBoundSa, |
| 115 | 117 |
upperBoundSa, floatingPointPrecSa, |
| 116 | 118 |
internalSollyaPrecSa, approxPrecSa): |
| ... | ... | |
| 133 | 135 |
- the center, x0, of the interval; |
| 134 | 136 |
- the corresponding approximation error. |
| 135 | 137 |
""" |
| 136 |
x = var(variableNameSa) |
|
| 137 |
# Scalling the domain -> [1,2[. |
|
| 138 |
boundsIntervalRifSa = RealIntervalField(floatingPointPrecSa) |
|
| 139 |
domainBoundsIntervalSa = boundsIntervalRifSa(lowerBoundSa, upperBoundSa) |
|
| 140 |
(domainScalingExpressionSa, invDomainScalingExpressionSa) = \ |
|
| 141 |
slz_interval_scaling_expression(domainBoundsIntervalSa, variableNameSa) |
|
| 142 |
print "domainScalingExpression for argument :", domainScalingExpressionSa |
|
| 143 |
print "f: ", f |
|
| 144 |
ff = f.subs({x : domainScalingExpressionSa})
|
|
| 145 |
#ff = f.subs_expr(x==domainScalingExpressionSa) |
|
| 146 |
scaledLowerBoundSa = invDomainScalingExpressionSa(lowerBoundSa).n() |
|
| 147 |
scaledUpperBoundSa = invDomainScalingExpressionSa(upperBoundSa).n() |
|
| 148 |
print 'ff:', ff, "- Domain:", scaledLowerBoundSa, scaledUpperBoundSa |
|
| 138 |
x = functionSa.variables()[0] # Actual variable name can be anything. |
|
| 139 |
(fff, scaledLowerBoundSa, scaledUpperBoundSa, \ |
|
| 140 |
scaledLowerBoundImageSa, scaledUpperBoundImageSa) = \ |
|
| 141 |
slz_compute_scaled_function(functionSa, \ |
|
| 142 |
lowerBoundSa, \ |
|
| 143 |
upperBoundSa, \ |
|
| 144 |
floatingPointPrecSa) |
|
| 149 | 145 |
# |
| 150 |
# Scalling the image -> [1,2[. |
|
| 151 |
flbSa = f(lowerBoundSa).n() |
|
| 152 |
fubSa = f(upperBoundSa).n() |
|
| 153 |
if flbSa <= fubSa: # Increasing |
|
| 154 |
imageBinadeBottomSa = floor(flbSa.log2()) |
|
| 155 |
else: # Decreasing |
|
| 156 |
imageBinadeBottomSa = floor(fubSa.log2()) |
|
| 157 |
print 'ff:', ff, '- Image:', flbSa, fubSa, imageBinadeBottomSa |
|
| 158 |
imageBoundsIntervalSa = boundsIntervalRifSa(flbSa, fubSa) |
|
| 159 |
(imageScalingExpressionSa, invImageScalingExpressionSa) = \ |
|
| 160 |
slz_interval_scaling_expression(imageBoundsIntervalSa, variableNameSa) |
|
| 161 |
iis = invImageScalingExpressionSa.function(x) |
|
| 162 |
fff = iis.subs({x:ff})
|
|
| 163 |
print "fff:", fff, |
|
| 164 |
print " - Image:", fff(scaledLowerBoundSa), fff(scaledUpperBoundSa) |
|
| 165 |
# |
|
| 166 | 146 |
resultArray = [] |
| 167 | 147 |
# |
| 168 | 148 |
print "Approximation precision: ", RR(approxPrecSa) |
| ... | ... | |
| 208 | 188 |
return(resultArray) |
| 209 | 189 |
# End slz_get_intervals_and_polynomials |
| 210 | 190 |
|
| 211 |
def slz_interval_scaling_expression(boundsInterval, varName):
|
|
| 191 |
def slz_interval_scaling_expression(boundsInterval, expVar):
|
|
| 212 | 192 |
""" |
| 213 | 193 |
Compute the scaling expression to map an interval that span only |
| 214 | 194 |
a binade to [1, 2) and the inverse expression as well. |
| ... | ... | |
| 219 | 199 |
if boundsInterval.endpoints()[0] >= 0: |
| 220 | 200 |
scalingCoeff = 2^floor(boundsInterval.endpoints()[0].log2()) |
| 221 | 201 |
invScalingCoeff = 1/scalingCoeff |
| 222 |
return((scalingCoeff * eval(varName),
|
|
| 223 |
invScalingCoeff * eval(varName)))
|
|
| 202 |
return((scalingCoeff * expVar,
|
|
| 203 |
invScalingCoeff * expVar))
|
|
| 224 | 204 |
else: |
| 225 | 205 |
scalingCoeff = \ |
| 226 | 206 |
2^(floor((-boundsInterval.endpoints()[0]).log2()) - 1) |
| 227 | 207 |
scalingOffset = -3 * scalingCoeff |
| 228 |
return((scalingCoeff * eval(varName) + scalingOffset,
|
|
| 229 |
1/scalingCoeff * eval(varName) + 3))
|
|
| 208 |
return((scalingCoeff * expVar + scalingOffset,
|
|
| 209 |
1/scalingCoeff * expVar + 3))
|
|
| 230 | 210 |
else: |
| 231 | 211 |
if boundsInterval.endpoints()[0] >= 0: |
| 232 | 212 |
scalingCoeff = 2^floor(boundsInterval.endpoints()[0].log2()) |
| 233 | 213 |
scalingOffset = 0 |
| 234 |
return((scalingCoeff * eval(varName),
|
|
| 235 |
1/scalingCoeff * eval(varName)))
|
|
| 214 |
return((scalingCoeff * expVar,
|
|
| 215 |
1/scalingCoeff * expVar))
|
|
| 236 | 216 |
else: |
| 237 | 217 |
scalingCoeff = \ |
| 238 | 218 |
2^(floor((-boundsInterval.endpoints()[1]).log2())) |
| 239 | 219 |
scalingOffset = -3 * scalingCoeff |
| 240 | 220 |
#scalingOffset = 0 |
| 241 |
return((scalingCoeff * eval(varName) + scalingOffset,
|
|
| 242 |
1/scalingCoeff * eval(varName) + 3))
|
|
| 221 |
return((scalingCoeff * expVar + scalingOffset,
|
|
| 222 |
1/scalingCoeff * expVar + 3))
|
|
| 243 | 223 |
|
| 244 | 224 |
|
| 245 | 225 |
def slz_polynomial_and_interval_to_sage(polyRangeCenterErrorSo): |
| ... | ... | |
| 269 | 249 |
return((polynomialSa, polynomialChangedVarSa, intervalSa, centerSa, errorSa)) |
| 270 | 250 |
# End slz_polynomial_and_interval_to_sage |
| 271 | 251 |
|
| 272 |
def slz_rat_poly_of_int_to_int_poly_of_int(ratPolyOfInt): |
|
| 273 |
pass |
|
| 274 |
# End slz_ratPoly_of_int_to_int_poly_of_int |
|
| 252 |
def slz_rat_poly_of_int_to_poly_for_coppersmith(ratPolyOfInt, |
|
| 253 |
precision, |
|
| 254 |
targetHardnessToRound, |
|
| 255 |
variable1, |
|
| 256 |
variable2): |
|
| 257 |
""" |
|
| 258 |
Creates a new polynomial with integer coefficients for use with the |
|
| 259 |
Coppersmith method. |
|
| 260 |
A the same time it computes : |
|
| 261 |
- 2^K (N); |
|
| 262 |
- 2^k |
|
| 263 |
- lcm |
|
| 264 |
""" |
|
| 265 |
# Create a new integer polynomial ring. |
|
| 266 |
IP = PolynomialRing(ZZ, name=str(variable1) + "," + str(variable2)) |
|
| 267 |
# Coefficients are issued in the increasing power order. |
|
| 268 |
ratPolyCoefficients = ratPolyOfInt.coefficients() |
|
| 269 |
# Build the list of number we compute the lcmm of. |
|
| 270 |
coefficientDenominators = sro_denominators(ratPolyCoefficients) |
|
| 271 |
coefficientDenominators.append(2^precision) |
|
| 272 |
coefficientDenominators.append(2^(targetHardnessToRound + 1)) |
|
| 273 |
leastCommonMultiple = sro_lcmm(coefficientDenominators) |
|
| 274 |
# Compute the lcm |
|
| 275 |
leastCommonMultiple = sro_lcmm(coefficientDenominators) |
|
| 276 |
# Compute the expression corresponding to the new polynomial |
|
| 277 |
coefficientNumerators = sro_numerators(ratPolyCoefficients) |
|
| 278 |
print coefficientNumerators |
|
| 279 |
polynomialExpression = 0 |
|
| 280 |
power = 0 |
|
| 281 |
# Iterate over two lists at the same time, stop when the shorter is |
|
| 282 |
# exhausted. |
|
| 283 |
for numerator, denominator in \ |
|
| 284 |
zip(coefficientNumerators, coefficientDenominators): |
|
| 285 |
multiplicator = leastCommonMultiple / denominator |
|
| 286 |
newCoefficient = numerator * multiplicator |
|
| 287 |
polynomialExpression += newCoefficient * variable1^power |
|
| 288 |
power +=1 |
|
| 289 |
polynomialExpression += - variable2 |
|
| 290 |
return (IP(polynomialExpression), |
|
| 291 |
leastCommonMultiple / 2^precision, # 2^K or N. |
|
| 292 |
leastCommonMultiple / 2 ^(targetHardnessToRound + 1), # tBound |
|
| 293 |
leastCommonMultiple) |
|
| 294 |
|
|
| 295 |
# End slz_ratPoly_of_int_to_poly_for_coppersmith |
|
| 275 | 296 |
|
| 276 | 297 |
def slz_rat_poly_of_rat_to_rat_poly_of_int(ratPolyOfRat, |
| 277 | 298 |
precision): |
Formats disponibles : Unified diff