Thank you very much for the pointers! I'll try the thesis and online paper you mentioned in your follow-up email. If I really need the Lenstra paper I'll try plying the librarian with brownies or something.
Thanks again! - Ryan John Cremona wrote: > 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 -~----------~----~----~----~------~----~------~--~---
