Lattice structure and linear complexity of nonlinear pseudorandom numbers

被引：25

作者：

Niederreiter, H

Winterhof, A

机构：

[1] Natl Univ Singapore, Dept Math, Singapore 117543, Singapore

[2] Austrian Acad Sci, Inst Discrete Math, A-1010 Vienna, Austria

来源：

APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING | 2002年 / 13卷 / 04期

关键词：

pseudorandom number generator; nonlinear method; inversive method; linear complexity; Marsaglia's lattice test;

D O I：

10.1007/s002000200105

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

It is shown that a q-periodic sequence over the finite field F-q passes an extended version of Marsaglia's lattice test for high dimensions if and only if its linear complexity is large. The consequences of this result for nonlinear and inversive pseudorandom number generators are worked out.

引用

页码：319 / 326

页数：8

共 50 条

[1] Lattice Structure and Linear Complexity of Nonlinear Pseudorandom Numbers
Harald Niederreiter
Arne Winterhof
Applicable Algebra in Engineering, Communication and Computing, 2002, 13 : 319 - 326
[2] Lattice structure and linear complexity profile of nonlinear pseudorandom number generators
Dorfer, G
Winterhof, A
APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING, 2003, 13 (06) : 499 - 508
[3] Lattice Structure and Linear Complexity Profile of Nonlinear Pseudorandom Number Generators
Gerhard Dorfer
Arne Winterhof
Applicable Algebra in Engineering, Communication and Computing, 2003, 13 : 499 - 508
[4] On the linear complexity profile of explicit nonlinear pseudorandom numbers
Meidl, W
Winterhof, A
INFORMATION PROCESSING LETTERS, 2003, 85 (01) : 13 - 18
[5] On the distribution and lattice structure of nonlinear congruential pseudorandom numbers
Niederreiter, H
Shparlinski, IE
FINITE FIELDS AND THEIR APPLICATIONS, 1999, 5 (03) : 246 - 253
[6] On the linear and nonlinear complexity profile of nonlinear pseudorandom number generators
Gutierrez, J
Shparlinski, IE
Winterhof, A
IEEE TRANSACTIONS ON INFORMATION THEORY, 2003, 49 (01) : 60 - 64
[7] Lattice profile and linear complexity profile of pseudorandom number sequences
Dorfer, G
FINITE FIELDS AND APPLICATIONS, 2004, 2948 : 69 - 78
[8] On the linear complexity profile of some new explicit inversive pseudorandom numbers
Meidl, W
Winterhof, A
JOURNAL OF COMPLEXITY, 2004, 20 (2-3) : 350 - 355
[9] ON MARSAGLIA LATTICE TEST FOR PSEUDORANDOM NUMBERS
EICHENAUER, J
NIEDERREITER, H
MANUSCRIPTA MATHEMATICA, 1988, 62 (02) : 245 - 248
[10] On the lattice structure of pseudorandom numbers generated over arbitrary finite fields
Niederreiter, H
Winterhof, A
APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING, 2001, 12 (03) : 265 - 272

← 1 2 3 4 5 →