Paper Info
Title
Engineering Nonlinear Pseudorandom Number Generators
Abstract
In the era of multi and many-core processors, computer simulations increasingly require parallel, small and fast pseudorandom number generation. Although linear generators lend themselves to a simpler evaluation that ensures favorable properties like guaranteed period, they may adversely affect the result of simulations or be quite large. Conversely, nonlinear generators may provide apparently random sequences, but are either very slow or difficult to analyze regarding their period.This is the case of our previous functions, Tyche and Tyche-i. Despite being among the fastest in their class and having average periods of 2 127, they may contain smaller cycles of arbitrary size. To overcome this limitation, in this paper we explore different forms of counters impacting either the state or the speed of the generator. We also introduce two number-theoretic generators that use 2 x 127 bits for periods of 2 116 and 2 125 and low to moderate computational costs. We experimentally demonstrate the efficiency of our new generators and observe that they exchange speed for period guarantees in a tradeoff that seems widespread in state-of-the-art random number generators.
Year
DOI
Venue
2013
10.1007/978-3-642-55224-3_10
PARALLEL PROCESSING AND APPLIED MATHEMATICS (PPAM 2013), PT I
Keywords
Field
DocType
Nonlinear pseudorandom generator, Elliptic curves, Elliptic curve linear congruential generator
Nonlinear system,Computer science,Parallel computing,Elliptic curve,Distributed computing,Pseudorandom number generator
Conference
Volume
ISSN
Citations 
8384
0302-9743
2
PageRank 
References 
Authors
0.37
14
2
Name
Order
Citations
PageRank
Samuel Neves111210.86
Filipe Araujo221424.63