Opened 13 years ago

Closed 13 years ago

Last modified 13 years ago

#1757 closed enhancement (duplicate)

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

Reported by: malb Owned by: somebody
Priority: minor Milestone: sage-2.11
Component: basic arithmetic Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

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 )

Change History (4)

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:

http://magma.maths.usyd.edu.au/magma/htmlhelp/text300.htm

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

http://www.informatik.tu-darmstadt.de/KP/publications/03/bp.ps

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.