Lattice structure and linear complexity profile of nonlinear pseudorandom number generators
type: Item
instance of: scholarly article
title: Lattice structure and linear complexity profile of nonlinear pseudorandom number generators
zbMATH Open document ID: 1026.11064
author: Gerhard Dorfer
author: Arne Winterhof
published in: Applicable Algebra in Engineering, Communication and Computing
publication date: 2003-07-08T00:00:00Z
review text: The authors extend a generalized version of Marsaglia's lattice test for sequences over finite fields to segments of sequences over an arbitrary field \(\mathbb{K}\) and give the relation between lattice test and linear complexity profile for such sequences. For given \(s\geq 1\) and \(N\geq 1\) we say that a sequence \((\eta_n)\) over \(\mathbb{K}\) (it is not necessarily periodic) passes the \(s\)-dimensional \(N\)-lattice test if the vectors \(\vec\eta_n- \vec\eta_0\) \((1< n< N-s) \operatorname {span} \mathbb{K}^s\), where \(\vec\eta_n= (\eta_n, \eta_{n+1},\dots, \eta_{n+s-1})\). Let \(L(N)= L((\eta_n),N)\) be the greatest one among such \(s\). Further, the linear complexity profile \(L(N)= L((\eta_n),N)\) is defined by the least order of a linear recurrence relation over \(\mathbb{K}\) satisfied by the first \(N\) terms of \((\eta_n)\). The authors prove that either \(S(N)= \min(L(N), N+1-L(N))\), or \(S(N)= \min(L(N), N+1- L(N))-1\), and so this lattice test and linear complexity profile provide essentially equivalent quality measures for randomness.
Mathematics Subject Classification ID: 11K45
Mathematics Subject Classification ID: 65C10
zbMATH DE Number: 1947286
zbMATH Keywords: pseudorandom number generator
zbMATH Keywords: nonlinear method
zbMATH Keywords: Marsaglia's lattice test
zbMATH Keywords: linear complexity profile
reviewed by: Yaochen Zhu
MaRDI profile type: Publication
full work available at URL: s00200-003-0116-6
OpenAlex ID: W1972186222
DOI: 10.1007/S00200-003-0116-6
description: scientific article; zbMATH DE number 1947286