Differences between revisions 2 and 3
Revision 2 as of 2008-04-28 00:40:37
Size: 1060
Editor: was
Revision 3 as of 2008-11-14 13:42:11
Size: 1072
Editor: anonymous
Comment: converted to 1.6 markup
Deletions are marked like this. Additions are marked like this.
Line 5: Line 5:
    attachment:proofofconcept.sws attachment:proofofconcept.pdf     [[attachment:proofofconcept.sws]] [[attachment:proofofconcept.pdf]]
Line 14: Line 14:
    attachment:Cyclotomic.pdf     [[attachment:Cyclotomic.pdf]]

Implement p-adic solver with cyclotomic p-adic reconstruction algorithm

* Here is a proof of concept implementation:

Notes: (1) I realized that reducing the entries in B modulo p^prec right before doing right_solve greatly speeds up the above proof of concept. (2) To make the above viable will require either modifying IML, modifying Linbox, or implementing Dixon p-adic lifting from scratch. I think implementing Dixon itself will be the best strategy, since we really need fine control over how it works, *and* we really want to use Pernet'ts FFLAS fast matrix-mod-p code, which IML doesn't use.

* Here are slides from a talk by Michael Monagan (join work with Liang Chen) on the same problem, but the approach is different:

I think this approach is perhaps misguided (?), since it doesn't seem to mention LLL at all, and it's of course critical to understand how to apply LLL to this problem. There's no way around that.

cyclo/padicsolver (last edited 2008-11-14 13:42:11 by anonymous)