| 95 |
95 |
2^m <= number < 2^(m+1). If number == 0 return None.
|
| 96 |
96 |
"""
|
| 97 |
97 |
# Checking the parameter.
|
| 98 |
|
# The exception construction is used to detect if numbre is a RealNumber
|
|
98 |
# The exception construction is used to detect if number is a RealNumber
|
| 99 |
99 |
# since not all numbers have
|
| 100 |
100 |
# the mro() method. sage.rings.real_mpfr.RealNumber do.
|
| 101 |
101 |
try:
|
| 102 |
102 |
classTree = [number.__class__] + number.mro()
|
| 103 |
|
# If the number is not a RealNumber (of offspring thereof) try
|
|
103 |
# If the number is not a RealNumber (or offspring thereof) try
|
| 104 |
104 |
# to transform it.
|
| 105 |
105 |
if not sage.rings.real_mpfr.RealNumber in classTree:
|
| 106 |
106 |
numberAsRR = RR(number)
|
| ... | ... | |
| 624 |
624 |
scaled back by dividing by the "right" powers of the variables bounds.
|
| 625 |
625 |
|
| 626 |
626 |
The elements in knownMonomials must be of the "right" polynomial type.
|
| 627 |
|
They set the polynomial type of the output polynomials list.
|
|
627 |
They set the polynomial type of the output polynomials in list.
|
| 628 |
628 |
@param reducedMatrix: the reduced matrix as output from LLL;
|
| 629 |
629 |
@param kwnonMonomials: the ordered list of the monomials used to
|
| 630 |
630 |
build the polynomials;
|
| ... | ... | |
| 1055 |
1055 |
return((polynomialSa, polynomialChangedVarSa, intervalSa, centerSa, errorSa))
|
| 1056 |
1056 |
# End slz_interval_and_polynomial_to_sage
|
| 1057 |
1057 |
|
|
1058 |
def slz_is_htrn(argument, function, targetAccuracy, targetRF = None,
|
|
1059 |
targetPlusOnePrecRF = None, quasiExactRF = None):
|
|
1060 |
"""
|
|
1061 |
Check if an element (argument) of the domain of function (function)
|
|
1062 |
yields a HTRN case (rounding to next) for the target precision
|
|
1063 |
(as impersonated by targetRF) for a given accuracy (targetAccuraty).
|
|
1064 |
"""
|
|
1065 |
## Arguments filtering. TODO: filter the first argument for consistence.
|
|
1066 |
## If no target accuracy is given, assume it is that of the argument.
|
|
1067 |
if targetRF is None:
|
|
1068 |
targetRF = argument.parent()
|
|
1069 |
## Ditto for the real field holding the midpoints.
|
|
1070 |
if targetPlusOnePrecRF is None:
|
|
1071 |
targetPlusOnePrecRF = RealField(targetRF.prec()+1)
|
|
1072 |
## Create a high accuracy RealField
|
|
1073 |
if quasiExactRF is None:
|
|
1074 |
quasiExactRF = RealField(1536)
|
|
1075 |
|
|
1076 |
exactArgument = quasiExactRF(argument)
|
|
1077 |
quasiExactValue = function(exactArgument)
|
|
1078 |
roundedValue = targetRF(quasiExactValue)
|
|
1079 |
roundedValuePrecPlusOne = targetPlusOnePrecRF(roundedValue)
|
|
1080 |
# Upper midpoint.
|
|
1081 |
roundedValuePrecPlusOneNext = roundedValuePrecPlusOne.nextabove()
|
|
1082 |
# Lower midpoint.
|
|
1083 |
roundedValuePrecPlusOnePrev = roundedValuePrecPlusOne.nextbelow()
|
|
1084 |
binade = slz_compute_binade(roundedValue)
|
|
1085 |
binadeCorrectedTargetAccuracy = targetAccuracy * 2^binade
|
|
1086 |
#print "Argument:", argument
|
|
1087 |
#print "f(x):", roundedValue, binade, floor(binade), ceil(binade)
|
|
1088 |
#print "binadeCorrectedTargetAccuracy:", \
|
|
1089 |
# binadeCorrectedTargetAccuracy.n(prec=100)
|
|
1090 |
#print "binadeCorrectedTargetAccuracy:", \
|
|
1091 |
# binadeCorrectedTargetAccuracy.n(prec=100).str(base=2)
|
|
1092 |
#print "Upper midpoint:", \
|
|
1093 |
# roundedValuePrecPlusOneNext.n(prec=targetPlusOnePrecRF.prec()).str(base=2)
|
|
1094 |
#print "Rounded value :", \
|
|
1095 |
# roundedValuePrecPlusOne.n(prec=targetPlusOnePrecRF.prec()).str(base=2), \
|
|
1096 |
# roundedValuePrecPlusOne.ulp().n(prec=2).str(base=2)
|
|
1097 |
#print "QuasiEx value :", quasiExactValue.n(prec=250).str(base=2)
|
|
1098 |
#print "Lower midpoint:", \
|
|
1099 |
# roundedValuePrecPlusOnePrev.n(prec=targetPlusOnePrecRF.prec()).str(base=2)
|
|
1100 |
## Begining of the general case : check with the midpoint with
|
|
1101 |
# greatest absolute value.
|
|
1102 |
if quasiExactValue > 0:
|
|
1103 |
if abs(quasiExactRF(roundedValuePrecPlusOneNext) - quasiExactValue) <\
|
|
1104 |
binadeCorrectedTargetAccuracy:
|
|
1105 |
#print "Too close to the upper midpoint: ", \
|
|
1106 |
abs(quasiExactRF(roundedValuePrecPlusOneNext) - quasiExactValue).n(prec=100)
|
|
1107 |
#print argument.n().str(base=16, \
|
|
1108 |
# no_sci=False)
|
|
1109 |
#print "Lower midpoint:", \
|
|
1110 |
# roundedValuePrecPlusOnePrev.n(prec=targetPlusOnePrecRF.prec()).str(base=2)
|
|
1111 |
#print "Value :", \
|
|
1112 |
# quasiExactValue.n(prec=200).str(base=2)
|
|
1113 |
#print "Upper midpoint:", \
|
|
1114 |
# roundedValuePrecPlusOneNext.n(prec=targetPlusOnePrecRF.prec()).str(base=2)
|
|
1115 |
#print
|
|
1116 |
return True
|
|
1117 |
else:
|
|
1118 |
if abs(quasiExactRF(roundedValuePrecPlusOnePrev) - quasiExactValue) < \
|
|
1119 |
binadeCorrectedTargetAccuracy:
|
|
1120 |
#print "Too close to the upper midpoint: ", \
|
|
1121 |
# abs(quasiExactRF(roundedValuePrecPlusOneNext) - quasiExactValue).n(prec=100)
|
|
1122 |
#print argument.n().str(base=16, \
|
|
1123 |
# no_sci=False)
|
|
1124 |
#print "Lower midpoint:", \
|
|
1125 |
# roundedValuePrecPlusOnePrev.n(prec=targetPlusOnePrecRF.prec()).str(base=2)
|
|
1126 |
#print "Value :", \
|
|
1127 |
# quasiExactValue.n(prec=200).str(base=2)
|
|
1128 |
#print "Upper midpoint:", \
|
|
1129 |
# roundedValuePrecPlusOneNext.n(prec=targetPlusOnePrecRF.prec()).str(base=2)
|
|
1130 |
#print
|
|
1131 |
return True
|
|
1132 |
#2345678901234567890123456789012345678901234567890123456789012345678901234567890
|
|
1133 |
## For the midpoint of smaller absolute value,
|
|
1134 |
# split cases with the powers of 2.
|
|
1135 |
if sno_abs_is_power_of_two(roundedValue):
|
|
1136 |
if quasiExactValue > 0:
|
|
1137 |
if abs(quasiExactRF(roundedValuePrecPlusOnePrev) - quasiExactValue) <\
|
|
1138 |
binadeCorrectedTargetAccuracy / 2:
|
|
1139 |
#print "Lower midpoint:", \
|
|
1140 |
# roundedValuePrecPlusOnePrev.n(prec=targetPlusOnePrecRF.prec()).str(base=2)
|
|
1141 |
#print "Value :", \
|
|
1142 |
# quasiExactValue.n(prec=200).str(base=2)
|
|
1143 |
#print "Upper midpoint:", \
|
|
1144 |
# roundedValuePrecPlusOneNext.n(prec=targetPlusOnePrecRF.prec()).str(base=2)
|
|
1145 |
#print
|
|
1146 |
return True
|
|
1147 |
else:
|
|
1148 |
if abs(quasiExactRF(roundedValuePrecPlusOneNext) - quasiExactValue) < \
|
|
1149 |
binadeCorrectedTargetAccuracy / 2:
|
|
1150 |
#print "Lower midpoint:", \
|
|
1151 |
# roundedValuePrecPlusOnePrev.n(prec=targetPlusOnePrecRF.prec()).str(base=2)
|
|
1152 |
#print "Value :",
|
|
1153 |
# quasiExactValue.n(prec=200).str(base=2)
|
|
1154 |
#print "Upper midpoint:",
|
|
1155 |
# roundedValuePrecPlusOneNext.n(prec=targetPlusOnePrecRF.prec()).str(base=2)
|
|
1156 |
#print
|
|
1157 |
return True
|
|
1158 |
#2345678901234567890123456789012345678901234567890123456789012345678901234567890
|
|
1159 |
else: ## Not a power of 2, regular comparison with the midpoint of
|
|
1160 |
# smaller absolute value.
|
|
1161 |
if quasiExactValue > 0:
|
|
1162 |
if abs(quasiExactRF(roundedValuePrecPlusOnePrev) - quasiExactValue) < \
|
|
1163 |
binadeCorrectedTargetAccuracy:
|
|
1164 |
#print "Lower midpoint:", \
|
|
1165 |
# roundedValuePrecPlusOnePrev.n(prec=targetPlusOnePrecRF.prec()).str(base=2)
|
|
1166 |
#print "Value :", \
|
|
1167 |
# quasiExactValue.n(prec=200).str(base=2)
|
|
1168 |
#print "Upper midpoint:", \
|
|
1169 |
# roundedValuePrecPlusOneNext.n(prec=targetPlusOnePrecRF.prec()).str(base=2)
|
|
1170 |
#print
|
|
1171 |
return True
|
|
1172 |
else: # quasiExactValue <= 0
|
|
1173 |
if abs(quasiExactRF(roundedValuePrecPlusOneNext) - quasiExactValue) < \
|
|
1174 |
binadeCorrectedTargetAccuracy:
|
|
1175 |
#print "Lower midpoint:", \
|
|
1176 |
# roundedValuePrecPlusOnePrev.n(prec=targetPlusOnePrecRF.prec()).str(base=2)
|
|
1177 |
#print "Value :", \
|
|
1178 |
# quasiExactValue.n(prec=200).str(base=2)
|
|
1179 |
#print "Upper midpoint:", \
|
|
1180 |
# roundedValuePrecPlusOneNext.n(prec=targetPlusOnePrecRF.prec()).str(base=2)
|
|
1181 |
#print
|
|
1182 |
return True
|
|
1183 |
#print "distance to the upper midpoint:", \
|
|
1184 |
# abs(quasiExactRF(roundedValuePrecPlusOneNext) - quasiExactValue).n(prec=100).str(base=2)
|
|
1185 |
#print "distance to the lower midpoint:", \
|
|
1186 |
# abs(quasiExactRF(roundedValuePrecPlusOnePrev) - quasiExactValue).n(prec=100).str(base=2)
|
|
1187 |
return False
|
|
1188 |
# End slz_is_htrn
|
|
1189 |
|
| 1058 |
1190 |
def slz_rat_poly_of_int_to_poly_for_coppersmith(ratPolyOfInt,
|
| 1059 |
1191 |
precision,
|
| 1060 |
1192 |
targetHardnessToRound,
|