Sage does not do this as far as I know but my student David Roberts implemented it in Magma for his thesis. He was following an alternative treatment by Mulders and Storjohann (the latter spoke at Sage Days in Nancy) since I did not know Arjen Lenstra's essentially equivalent formulation until I gave a talk in Leiden with Hendrik L in the audience ;).
The algorithm is the same for polynomial lattices over any field, but in the smae way as for polynomial gcd and the Euclidean Algorithm, it works better over some fields than others (e.g. finite fields good, rationals bad). I would guess that it could be implemented more efficiently over GF(2). John Cremona PS See http://www.warwick.ac.uk/staff/J.E.Cremona/theses/index.html for the thesis (it's the last one) PS I have paper copy (only) of the Lenstra paper 2009/3/6 Ryan Hinton <iob...@email.com>: > > Thanks in advance for any help. Please let me know if I'm producing too > much noise on the list. > > I'm still working on the pseudo-random number generators. To verify a > certain property (maximal equidistribution) [1], it is equivalent [2,3] > to finding a Minkowski-reduced basis for a lattice over polynomials with > coefficients in GF(2) (specifically, the non-zero point with the > smallest maximum polynomial degree). They give [4] as an example of an > algorithm that will do the trick. > > I'm stuck. I have not yet found a copy of [4], but from the abstract it > sounds like the reduced lattice basis is a means to the title of the > paper, factoring multivariate polynomials over finite fields. On IRC, > Carl Witty suggested that the LLL algorithm sounded similar, but for > integers. I haven't figured out how to frame my polynomial lattice > problem as an integer lattice problem, though. > > So, question #1. Does anyone know if Sage does this? > > Question #2. Does anyone have electronic access to article [4] or an > improved algorithm to do this basis reduction? The ScienceDirect link > for the Lenstra article is is > http://dx.doi.org/10.1016/0022-0000(85)90016-9. > > Thanks! > > References: > > Most of these are on Dr. L'Ecuyer's website, > http://www.iro.umontreal.ca/~lecuyer/papers.html > > [1] F. Panneton, P. L'Ecuyer, and M. Matsumoto, ``Improved Long-Period > Generators Based on Linear Recurrences Modulo 2'', ACM Transactions on > Mathematical Software, 32, 1 (2006), 1-16. > > [2] P. L'Ecuyer and F. Panneton, ``F_2-Linear Random Number > Generators'', 2007, to appear with minor revisions in "Advancing the > Frontiers of Simulation: A Festschrift in Honor of George S. Fishman." > GERAD Report 2007-21. > > [3] R. Couture and P. L'Ecuyer, ``Lattice Computations for Random > Numbers'', Mathematics of Computation, 69, 230 (2000), 757--765. > > [4] A. K. Lenstra. Factoring multivariate polynomials over finite > fields. Journal of Computer and System Sciences, 30:235–248, 1985. > > --- > Ryan Hinton > PhD candidate, Electrical Engineering > University of Virginia > > > > --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
