Opened 13 years ago

Closed 13 years ago

# implement Coppersmith's method for finding small roots of univariate polynomials modulo an integer

Reported by: Owned by: malb somebody minor sage-2.11 basic arithmetic

### Description

From the MAGMA 2.14 changelog: "Coppersmith's method for finding small roots of univariate polynomials modulo an integer has been implemented. This implementation uses the new fpLLL package of Damien Stehlé." ( http://magma.maths.usyd.edu.au/magma/htmlhelp/rel/node2.htm )

### comment:1 Changed 13 years ago by malb

• Priority changed from major to minor

### comment:2 Changed 13 years ago by malb

The MAGMA documentation for this function is here `SmallRoots`:

Coppersmith's algorithm is described and discussed in Alexander May's PhD thesis:

A first naive implementation would look like this:

```def small_roots(f, X=None):
d = f.degree()
K = f.base_ring()
M = K.characteristic()
f.change_ring(ZZ)
if X is None:
X =  M.nth_root(d*(d+1)/2)
A = Matrix(ZZ,d+1,d+1)
for i in range(d):
A[i,i] = M*X^i
for i in range(d+1):
A[d,i] = ZZ(f[i])*X^i
A = A.LLL()
x = ZZ['x'].gen(0)
g = 0
for i in range(d+1):
g+= A[0,i]/X^i * x^i
return map(lambda (x,y):(K(x),y), g.roots())
```

We can do slightly better though.

### comment:3 Changed 13 years ago by malb

• Resolution set to duplicate
• Status changed from new to closed

duplicate of #2424

### comment:4 Changed 13 years ago by mabshoff

• Milestone changed from sage-3.0 to sage-2.11
Note: See TracTickets for help on using tickets.