Révision 123 pobysoPythonSage/src/sageSLZ/sageSLZ.sage
| sageSLZ.sage (revision 123) | ||
|---|---|---|
| 169 | 169 |
return (lb, ub) |
| 170 | 170 |
# End slz_compute_binade_bounds |
| 171 | 171 |
# |
| 172 |
def slz_compute_coppersmith_reduced_polynomials(inputPolynomial, |
|
| 173 |
alpha, |
|
| 174 |
N, |
|
| 175 |
iBound, |
|
| 176 |
tBound): |
|
| 177 |
""" |
|
| 178 |
For a given set of arguments (see below), compute a list |
|
| 179 |
of "reduced polynomials" that could be used to compute roots |
|
| 180 |
of the inputPolynomial. |
|
| 181 |
""" |
|
| 182 |
# Arguments check. |
|
| 183 |
if iBound == 0 or tBound == 0: |
|
| 184 |
return () |
|
| 185 |
# End arguments check. |
|
| 186 |
nAtAlpha = N^alpha |
|
| 187 |
## Building polynomials for matrix. |
|
| 188 |
polyRing = inputPolynomial.parent() |
|
| 189 |
# Whatever the 2 variables are actually called, we call them |
|
| 190 |
# 'i' and 't' in all the variable names. |
|
| 191 |
(iVariable, tVariable) = inputPolynomial.variables()[:2] |
|
| 192 |
#print polyVars[0], type(polyVars[0]) |
|
| 193 |
initialPolynomial = inputPolynomial.subs({iVariable:iVariable * iBound,
|
|
| 194 |
tVariable:tVariable * tBound}) |
|
| 195 |
polynomialsList = \ |
|
| 196 |
spo_polynomial_to_polynomials_list_5(initialPolynomial, |
|
| 197 |
alpha, |
|
| 198 |
N, |
|
| 199 |
iBound, |
|
| 200 |
tBound, |
|
| 201 |
0) |
|
| 202 |
#print "Polynomials list:", polynomialsList |
|
| 203 |
## Building the proto matrix. |
|
| 204 |
knownMonomials = [] |
|
| 205 |
protoMatrix = [] |
|
| 206 |
for poly in polynomialsList: |
|
| 207 |
spo_add_polynomial_coeffs_to_matrix_row(poly, |
|
| 208 |
knownMonomials, |
|
| 209 |
protoMatrix, |
|
| 210 |
0) |
|
| 211 |
matrixToReduce = spo_proto_to_row_matrix(protoMatrix) |
|
| 212 |
#print matrixToReduce |
|
| 213 |
## Reduction and checking. |
|
| 214 |
reducedMatrix = matrixToReduce.LLL(fp='fp') |
|
| 215 |
isLLLReduced = reducedMatrix.is_LLL_reduced() |
|
| 216 |
if not isLLLReduced: |
|
| 217 |
return () |
|
| 218 |
monomialsCount = len(knownMonomials) |
|
| 219 |
monomialsCountSqrt = sqrt(monomialsCount) |
|
| 220 |
#print "Monomials count:", monomialsCount, monomialsCountSqrt.n() |
|
| 221 |
#print reducedMatrix |
|
| 222 |
## Check the Coppersmith condition for each row and build the reduced |
|
| 223 |
# polynomials. |
|
| 224 |
ccReducedPolynomialsList = [] |
|
| 225 |
for row in reducedMatrix.rows(): |
|
| 226 |
l2Norm = row.norm(2) |
|
| 227 |
if (l2Norm * monomialsCountSqrt) < nAtAlpha: |
|
| 228 |
#print (l2Norm * monomialsCountSqrt).n() |
|
| 229 |
print l2Norm.n() |
|
| 230 |
ccReducedPolynomial = \ |
|
| 231 |
slz_compute_reduced_polynomial(row, |
|
| 232 |
knownMonomials, |
|
| 233 |
iVariable, |
|
| 234 |
iBound, |
|
| 235 |
tVariable, |
|
| 236 |
tBound) |
|
| 237 |
if not ccReducedPolynomial is None: |
|
| 238 |
ccReducedPolynomialsList.append(ccReducedPolynomial) |
|
| 239 |
else: |
|
| 240 |
print l2Norm.n() , ">", nAtAlpha |
|
| 241 |
pass |
|
| 242 |
if len(ccReducedPolynomialsList) < 2: |
|
| 243 |
print "***Less than 2 Coppersmith condition compliant vectors.***" |
|
| 244 |
return () |
|
| 245 |
return ccReducedPolynomialsList |
|
| 246 |
# End slz_compute_coppersmith_reduced_polynomials |
|
| 247 |
|
|
| 172 | 248 |
def slz_compute_integer_polynomial_modular_roots(inputPolynomial, |
| 173 | 249 |
alpha, |
| 174 | 250 |
N, |
| 175 | 251 |
iBound, |
| 176 | 252 |
tBound): |
| 177 | 253 |
""" |
| 178 |
For a given set of arguments (see below) , compute the polynomial modular
|
|
| 254 |
For a given set of arguments (see below), compute the polynomial modular |
|
| 179 | 255 |
roots, if any. |
| 180 | 256 |
""" |
| 257 |
# Arguments check. |
|
| 258 |
if iBound == 0 or tBound == 0: |
|
| 259 |
return set() |
|
| 260 |
# End arguments check. |
|
| 181 | 261 |
nAtAlpha = N^alpha |
| 182 | 262 |
## Building polynomials for matrix. |
| 183 | 263 |
polyRing = inputPolynomial.parent() |
| ... | ... | |
| 193 | 273 |
N, |
| 194 | 274 |
iBound, |
| 195 | 275 |
tBound, |
| 196 |
10)
|
|
| 197 |
print "Polynomials list:", polynomialsList |
|
| 276 |
0) |
|
| 277 |
#print "Polynomials list:", polynomialsList
|
|
| 198 | 278 |
## Building the proto matrix. |
| 199 | 279 |
knownMonomials = [] |
| 200 | 280 |
protoMatrix = [] |
| ... | ... | |
| 209 | 289 |
reducedMatrix = matrixToReduce.LLL(fp='fp') |
| 210 | 290 |
isLLLReduced = reducedMatrix.is_LLL_reduced() |
| 211 | 291 |
if not isLLLReduced: |
| 212 |
return None
|
|
| 292 |
return set()
|
|
| 213 | 293 |
monomialsCount = len(knownMonomials) |
| 214 | 294 |
monomialsCountSqrt = sqrt(monomialsCount) |
| 295 |
#print "Monomials count:", monomialsCount, monomialsCountSqrt.n() |
|
| 296 |
#print reducedMatrix |
|
| 215 | 297 |
## Check the Coppersmith condition for each row and build the reduced |
| 216 | 298 |
# polynomials. |
| 217 | 299 |
ccReducedPolynomialsList = [] |
| 218 | 300 |
for row in reducedMatrix.rows(): |
| 219 | 301 |
l2Norm = row.norm(2) |
| 220 |
if (l2Norm * monomialsCountSqrt < nAtAlpha): |
|
| 221 |
print (l2Norm * monomialsCountSqrt).n() |
|
| 302 |
if (l2Norm * monomialsCountSqrt) < nAtAlpha: |
|
| 303 |
#print (l2Norm * monomialsCountSqrt).n() |
|
| 304 |
#print l2Norm.n() |
|
| 222 | 305 |
ccReducedPolynomial = \ |
| 223 | 306 |
slz_compute_reduced_polynomial(row, |
| 224 | 307 |
knownMonomials, |
| ... | ... | |
| 228 | 311 |
tBound) |
| 229 | 312 |
if not ccReducedPolynomial is None: |
| 230 | 313 |
ccReducedPolynomialsList.append(ccReducedPolynomial) |
| 314 |
else: |
|
| 315 |
#print l2Norm.n() , ">", nAtAlpha |
|
| 316 |
pass |
|
| 231 | 317 |
if len(ccReducedPolynomialsList) < 2: |
| 232 | 318 |
print "Less than 2 Coppersmith condition compliant vectors." |
| 233 |
return None |
|
| 319 |
return set() |
|
| 320 |
#print ccReducedPolynomialsList |
|
| 234 | 321 |
## Create the valid (poly1 and poly2 are algebraically independent) |
| 235 | 322 |
# resultant tuples (poly1, poly2, resultant(poly1, poly2)). |
| 236 | 323 |
# Try to mix and match all the polynomial pairs built from the |
| ... | ... | |
| 244 | 331 |
resultantInI = \ |
| 245 | 332 |
ccReducedPolynomialsList[polyOuterIndex].resultant(ccReducedPolynomialsList[polyInnerIndex], |
| 246 | 333 |
ccReducedPolynomialsList[0].parent(str(iVariable))) |
| 247 |
#print resultantInI |
|
| 248 | 334 |
#print "Resultant", resultantInI |
| 249 | 335 |
# Test algebraic independence. |
| 250 | 336 |
if not resultantInI.is_zero(): |
| ... | ... | |
| 254 | 340 |
# If no non zero resultant was found: we can't get no algebraically |
| 255 | 341 |
# independent polynomials pair. Give up! |
| 256 | 342 |
if len(resultantsInITuplesList) == 0: |
| 257 |
return None |
|
| 343 |
return set() |
|
| 344 |
#print resultantsInITuplesList |
|
| 258 | 345 |
# Compute the roots. |
| 259 | 346 |
Zi = ZZ[str(iVariable)] |
| 260 | 347 |
Zt = ZZ[str(tVariable)] |
| ... | ... | |
| 264 | 351 |
for resultantInITuple in resultantsInITuplesList: |
| 265 | 352 |
tRootsList = Zt(resultantInITuple[2]).roots() |
| 266 | 353 |
# For each tRoot, compute the corresponding iRoots and check |
| 267 |
# them in the polynomial. |
|
| 354 |
# them in the input polynomial.
|
|
| 268 | 355 |
for tRoot in tRootsList: |
| 269 |
print "tRoot:", tRoot |
|
| 356 |
#print "tRoot:", tRoot
|
|
| 270 | 357 |
# Roots returned by root() are (value, multiplicity) tuples. |
| 271 | 358 |
iRootsList = \ |
| 272 | 359 |
Zi(resultantInITuple[0].subs({resultantInITuple[0].variables()[1]:tRoot[0]})).roots()
|
| 360 |
print iRootsList |
|
| 273 | 361 |
# The iRootsList can be empty, hence the test. |
| 274 | 362 |
if len(iRootsList) != 0: |
| 275 | 363 |
for iRoot in iRootsList: |
| ... | ... | |
| 378 | 466 |
## Initialisations. |
| 379 | 467 |
polynomialRing = knownMonomials[0].parent() |
| 380 | 468 |
currentPolynomial = polynomialRing(0) |
| 469 |
# TODO: use zip instead of indices. |
|
| 381 | 470 |
for colIndex in xrange(0, len(knownMonomials)): |
| 382 | 471 |
currentCoefficient = matrixRow[colIndex] |
| 383 | 472 |
if currentCoefficient != 0: |
| ... | ... | |
| 386 | 475 |
#print "Monomial as multivariate polynomial:", \ |
| 387 | 476 |
#currentMonomial, type(currentMonomial) |
| 388 | 477 |
degreeInVar1 = currentMonomial.degree(var1) |
| 389 |
#print "Degree in var", var1, ":", degreeInVar1 |
|
| 478 |
#print "Degree in var1", var1, ":", degreeInVar1
|
|
| 390 | 479 |
degreeInVar2 = currentMonomial.degree(var2) |
| 391 |
#print "Degree in var", var2, ":", degreeInVar2 |
|
| 480 |
#print "Degree in var2", var2, ":", degreeInVar2
|
|
| 392 | 481 |
if degreeInVar1 > 0: |
| 393 | 482 |
currentCoefficient = \ |
| 394 |
currentCoefficient / var1Bound^degreeInVar1
|
|
| 483 |
currentCoefficient / (var1Bound^degreeInVar1)
|
|
| 395 | 484 |
#print "varBound1 in degree:", var1Bound^degreeInVar1 |
| 396 | 485 |
#print "Current coefficient(1)", currentCoefficient |
| 397 | 486 |
if degreeInVar2 > 0: |
| 398 | 487 |
currentCoefficient = \ |
| 399 |
currentCoefficient / var2Bound^degreeInVar2
|
|
| 488 |
currentCoefficient / (var2Bound^degreeInVar2)
|
|
| 400 | 489 |
#print "Current coefficient(2)", currentCoefficient |
| 401 | 490 |
#print "Current reduced monomial:", (currentCoefficient * \ |
| 402 | 491 |
# currentMonomial) |
Formats disponibles : Unified diff