2009/3/7 Ryan Hinton <iob...@email.com>: > > 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.
I could mail you a copy on Monday (assuming that I can find it, which is nontrivial since I have moved offices more than once since I last saw it). John > > 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 -~----------~----~----~----~------~----~------~--~---
