Optimal characteristic polynomials for digital multistep pseudorandom numbers
type: Item
instance of: scholarly article
title: Optimal characteristic polynomials for digital multistep pseudorandom numbers
zbMATH Open document ID: 0618.65004
DOI: 10.1007/BF02310104
published in: Computing
publication date: 1987-01-01T00:00:00Z
review text: Digital k-step pseudorandom numbers are obtained from a sequence \(y_ 0,y_ 1,..\). of bits generated by the recursion \(y_{n+k}\equiv \sum ^{k-1}_{i=0}b_ iy_{n+i} mod 2\) for \(n=0,1,..\). by setting \(x_ n=\sum ^{k}_{j=1}y_{kn+j-1}2^{-j}\) for \(n=0,1..\).. It is assumed that the initial values \(y_ 0,y_ 1,...,y_{k-1}\) are not all 0, that \(k\geq 2\) and \(\gcd (k,2^ k-1)=1\), and that the characteristic polynomial \(f(x)=x^ k-\sum ^{k-1}_{i=0}b_ ix^ i\) of the recursion is primitive over the binary field \(F_ 2\). According to earlier work of the second author [Sitzungsber. Österr. Akad. Wiss. Math.-Naturwiss. Kl. Abt. II 195, 109-138 (1986)], digital k-step pseudorandom numbers pass the serial test for statistical independence of pairs precisely if L(f) is small, where L(f) is the maximum degree of the partial quotients in the continued fraction expansion of \(f(x)/x^ k\). The paper under review describes a systematic method of constructing primitive polynomials f over \(F_ 2\) with L(f)\(\leq 2\), which is based on results of the second author [Monatsh. Math. 103, 269-288 (1987)]. Tables of such polynomials for degrees \(k\leq 64\) are included.
Mathematics Subject Classification ID: 65C10
Mathematics Subject Classification ID: 11K16
zbMATH DE Number: 4003339
zbMATH Keywords: digital multistep pseudorandom numbers
zbMATH Keywords: serial test
zbMATH Keywords: continued fraction expansion
zbMATH Keywords: primitive polynomials
zbMATH Keywords: tables
author: Gary L. Mullen
author: Harald Niederreiter
MaRDI profile type: Publication
cites work: Factorizations of 𝑏ⁿ±1, 𝑏=2, 3, 5, 6, 7, 10, 11, 12 Up to High Powers
cites work: Q3935355
cites work: Q3765876
cites work: RANDOM NUMBERS FALL MAINLY IN THE PLANES
cites work: The Performance of k-Step Pseudorandom Number Generators under the Uniformity Test
cites work: Q4724719
cites work: Q3817493
cites work: Rational functions with partial quotients of small degree in their continued fraction expansion
cites work: Point sets and sequences with small discrepancy
cites work: Q5665102
cites work: Random Numbers Generated by Linear Recurrence Modulo Two
full work available at URL: https://doi.org/10.1007/bf02310104
OpenAlex ID: W1523628657
Recommended article: Figures of Merit for Digital Multistep Pseudorandom Numbers
Recommended article: Pseudorandom numbers and hash functions from iterations of multivariate polynomials
Recommended article: Q3334857
Recommended article: Pseudorandom Bits for Polynomials
Recommended article: On pseudorandom numbers from multivariate polynomial systems
Recommended article: Multiplicative Character Sums with Counter-Dependent Nonlinear Congruential Pseudorandom Number Generators
Recommended article: Optimal multipliers for linear congruential pseudorandom number generators with prime moduli
Recommended article: On Optimal GFSR Pseudorandom Number Generators
Recommended article: Number-theoretic constructions of efficient pseudo-random functions
Recommended article: On the structure of digital explicit nonlinear and inversive pseudorandom number generators
description: scientific article; zbMATH DE number 4003339