How to use the coppersmith method in sagemath?

How to use the coppersmith method in sagemath?

Z^2 + 665748*Z + 1494997090560 = 1501297920*W


to be fair, I am writing to you what it is. It is an exercise but it is understood well.

edit retag close merge delete

What is it ? What is your aim ?

( 2021-12-17 09:54:58 +0200 )edit

@FrédéricC (1) https://en.wikipedia.org/wiki/Coppers... (2) I need it for a factorization algorithm

( 2021-12-17 10:49:07 +0200 )edit

Sort by » oldest newest most voted

Coppersmith's method for univariate polynomials is provided as .small_roots() method, or via PARI/GP as gp.zncoppersmith() function:

sage: R.<Z> = ZZ[]
sage: gp.zncoppersmith( Z^2+665748*Z+1494997090560, 1501297920, 2^14  )
[11520, 15852]

more

@Max Alekseyev thank you! what does 2^14 mean?

( 2021-12-17 15:14:16 +0200 )edit
1

Bound for the roots. I've provided links to documentation for both implementations.

( 2021-12-17 15:48:46 +0200 )edit

@Max Alekseyev thank you

( 2021-12-17 16:03:17 +0200 )edit