#5519: [with patch, needs work] Irreducibility test is slow for polynomials over
GF(2)
-------------------------+--------------------------------------------------
Reporter: rhinton | Owner: rhinton
Type: enhancement | Status: new
Priority: major | Milestone:
Component: algebra | Keywords:
-------------------------+--------------------------------------------------
Comment(by rhinton):
Replying to [comment:9 zimmerma]:
> > Supposedly, polynomials with few terms (e.g. trinomials) have
relatively poor properties for PRNGs...
>
> do you have any argument supporting that claim?
I'm just reciting what I've read. I am enjoying [1] right now, available
at
http://www.iro.umontreal.ca/~lecuyer/papers.html
as f2lin.pdf. They make this claim on page 11 in the first full
paragraph, and cite [2] and [3]. They malign trinomials and pentanomials
in particular (no offense intended) for PRNGs. Incidentally, I'm working
on a tool to search for maximally-equidistributed WELL generators
(explained in [1], defined in [4] -- also very readable).
[1] 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.
[2] A. Compagner. The hierarchy of correlations in random binary
sequences. Journal of Statistical Physics, 63:883–896, 1991.
[3] D. Wang and A. Compagner. On the use of reducible polynomials as
random number generators. Mathematics of Computation, 60:363–374, 1993.
[4] 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.
Note that [4] is also available with errata from L'Ecuyer's site along
with C source code. And I have a few additional errata not currently
listed in case you want to implement one.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5519#comment:12>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
