| 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)
|