Computational Algebra Seminar: Shparlinski, Brent

Speaker: Igor Shparlinski (Macquarie)
Title: TBA
Time & Place: 2:35-3:30pm, Thursday 14 June, Carslaw 535

Afternoon Tea: 3:30-4pm

Speaker: Richard Brent (ANU)
Title: Using Magma to find good xorshift random number generators
Time & Place: 4:05-5pm, Thursday 14 June, Carslaw 535

Abstract (Brent):
Marsaglia recently introduced a class of ``xorshift’’ random number
generators (RNGs) with periods $2^n - 1$ for $n = 32, 64$, etc. We
describe a generalisation of Marsaglia’s xorshift generators in order
to obtain fast and high-quality RNGs with extremely long periods.

RNGs based on primitive trinomials may be unsatisfactory because a
trinomial has very small weight (number of nonzero terms).  In
contrast, our generators can be chosen so that their minimal
polynomials have large weight. A search using Magma has found good
generators for $n$ a power of two up to 4096.  These have been
implemented in a free software package xorgens.  Aspects of the search
using Magma, and a connection with Fermat numbers, will be mentioned.