#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: |
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
- Priority changed from major to minor
comment:2 Changed 13 years ago by
comment:3 Changed 13 years ago by
- Resolution set to duplicate
- Status changed from new to closed
duplicate of #2424
comment:4 Changed 13 years ago by
- Milestone changed from sage-3.0 to sage-2.11
Note: See
TracTickets for help on using
tickets.
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:
We can do slightly better though.