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 -~----------~----~----~----~------~----~------~--~---
