A class of maximum-period nonlinear congruential generators derived from the Renyi chaotic map

被引:73
作者
Addabbo, T.
Alioto, M.
Fort, A.
Pasini, A.
Rocchi, S.
Vignoli, V.
机构
[1] Univ Siena, Dept Informat Engn, I-53100 Siena, Italy
[2] Univ Siena, Math Dept R Magari, I-53100 Siena, Italy
关键词
digital circuits; nonlinear systems; random number generators (RNGs); sequences; BEHAVIOR;
D O I
10.1109/TCSI.2007.890622
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
In this paper, a family of nonlinear congruential generators (NLCGs) based on the digitized Renyi map is considered for the definition of hardware-efficient pseudorandom number generators (PRNGs), and a theoretical framework for their study is presented. The authors investigate how the nonlinear structure of these systems eliminates some of the statistical regularities spoiling the randomness of sequences generated with linear techniques. In detail, in this paper, a necessary condition that the considered NLCGs must satisfy to have maximum period length is given, and a list of such maximum period PRNGs for period lengths up to 2(31) - 1 is provided. Referring to the NIST800-22 statistical test suite, two PRNG examples are presented and compared to well-known PRNGs based on linear recurrencies requiring a similar amount of resources for their implementation.
引用
收藏
页码:816 / 828
页数:13
相关论文
共 22 条
[1]   Low-hardware complexity PRBGs based on a piecewise-linear chaotic map [J].
Addabbo, T. ;
Alioto, M. ;
Fort, A. ;
Rocchi, S. ;
Vignoli, V. .
IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS, 2006, 53 (05) :329-333
[2]   An efficient implementation of PRNGs based on the digital sawtooth map [J].
Alioto, M ;
Bernardi, S ;
Fort, A ;
Rocchi, S ;
Vignoli, V .
INTERNATIONAL JOURNAL OF CIRCUIT THEORY AND APPLICATIONS, 2004, 32 (06) :615-627
[3]  
[Anonymous], 2003, Random Number Generations and Monte Carlo Methods
[4]   EFFECTS OF PHASE-SPACE DISCRETIZATION ON THE LONG-TIME BEHAVIOR OF DYNAMIC-SYSTEMS [J].
BECK, C ;
ROEPSTORFF, G .
PHYSICA D, 1987, 25 (1-3) :173-180
[5]   SIMULATING CHAOTIC BEHAVIOR WITH FINITE-STATE MACHINES [J].
BINDER, PM ;
JENSEN, RV .
PHYSICAL REVIEW A, 1986, 34 (05) :4460-4463
[6]  
David Rene., 1998, Random Testing of Digital Circuits
[7]   RECONSTRUCTING TRUNCATED INTEGER VARIABLES SATISFYING LINEAR CONGRUENCES [J].
FRIEZE, AM ;
HASTAD, J ;
KANNAN, R ;
LAGARIAS, JC ;
SHAMIR, A .
SIAM JOURNAL ON COMPUTING, 1988, 17 (02) :262-280
[8]  
Gruber P.M., 1987, Geometry of numbers
[9]  
Hardy G.H., 1983, INTRO THEORY NUMBERS, V5th
[10]  
JESSA M, 2001, ICECS 2001, V1, P449