| 1087 |
1087 |
# Coefficients are issued in the increasing power order.
|
| 1088 |
1088 |
ratPolyCoefficients = ratPolyOfInt.coefficients()
|
| 1089 |
1089 |
# Print the reversed list for debugging.
|
|
1090 |
print
|
| 1090 |
1091 |
print "Rational polynomial coefficients:", ratPolyCoefficients[::-1]
|
| 1091 |
1092 |
# Build the list of number we compute the lcm of.
|
| 1092 |
1093 |
coefficientDenominators = sro_denominators(ratPolyCoefficients)
|
|
1094 |
print "Coefficient denominators:", coefficientDenominators
|
| 1093 |
1095 |
coefficientDenominators.append(2^precision)
|
| 1094 |
|
coefficientDenominators.append(2^(targetHardnessToRound + 1))
|
|
1096 |
coefficientDenominators.append(2^(targetHardnessToRound))
|
| 1095 |
1097 |
leastCommonMultiple = lcm(coefficientDenominators)
|
| 1096 |
1098 |
# Compute the expression corresponding to the new polynomial
|
| 1097 |
1099 |
coefficientNumerators = sro_numerators(ratPolyCoefficients)
|
| 1098 |
1100 |
#print coefficientNumerators
|
| 1099 |
1101 |
polynomialExpression = 0
|
| 1100 |
1102 |
power = 0
|
| 1101 |
|
# Iterate over two lists at the same time, stop when the shorter is
|
| 1102 |
|
# exhausted.
|
|
1103 |
# Iterate over two lists at the same time, stop when the shorter
|
|
1104 |
# (is this case coefficientsNumerators) is
|
|
1105 |
# exhausted. Both lists are ordered in the order of increasing powers
|
|
1106 |
# of variable1.
|
| 1103 |
1107 |
for numerator, denominator in \
|
| 1104 |
1108 |
zip(coefficientNumerators, coefficientDenominators):
|
| 1105 |
1109 |
multiplicator = leastCommonMultiple / denominator
|
| ... | ... | |
| 1108 |
1112 |
power +=1
|
| 1109 |
1113 |
polynomialExpression += - variable2
|
| 1110 |
1114 |
return (IP(polynomialExpression),
|
| 1111 |
|
leastCommonMultiple / 2^precision, # 2^K or N.
|
| 1112 |
|
leastCommonMultiple / 2^(targetHardnessToRound + 1), # tBound
|
|
1115 |
leastCommonMultiple / 2^precision, # 2^K aka N.
|
|
1116 |
#leastCommonMultiple / 2^(targetHardnessToRound + 1), # tBound
|
|
1117 |
leastCommonMultiple / 2^(targetHardnessToRound), # tBound
|
| 1113 |
1118 |
leastCommonMultiple) # If we want to make test computations.
|
| 1114 |
1119 |
|
| 1115 |
|
# End slz_ratPoly_of_int_to_poly_for_coppersmith
|
|
1120 |
# End slz_rat_poly_of_int_to_poly_for_coppersmith
|
| 1116 |
1121 |
|
| 1117 |
1122 |
def slz_rat_poly_of_rat_to_rat_poly_of_int(ratPolyOfRat,
|
| 1118 |
1123 |
precision):
|
| ... | ... | |
| 1132 |
1137 |
polynomialField(ratPolyOfRat.subs({polynomialVariable : \
|
| 1133 |
1138 |
polynomialVariable/2^(precision-1)}))
|
| 1134 |
1139 |
|
| 1135 |
|
# Return a tuple:
|
| 1136 |
|
# - the bivariate integer polynomial in (i,j);
|
| 1137 |
|
# - 2^K
|
| 1138 |
1140 |
# End slz_rat_poly_of_rat_to_rat_poly_of_int
|
| 1139 |
1141 |
|
| 1140 |
1142 |
|