Abstract
A necessary and sufficient condition is established for the generalized feedback shift register (GFSR) sequence introduced by Lewis and Payne to be k-distributed. Based upon the theorem, a theoretical test for k-distributivity is proposed and performed in a reasonable amount of computer time, even for k = 16 and a high degree of resolution (for which statistical tests are impossible because of the astronomical amount of computer time required). For the special class of GFSR generators considered by Arvillias and Maritsas based on the primitive trinomial D p + D q + 1 with q = an integral power of 2, it is shown that the sequence is k-distributed if and only if the lengths of all subregisters are at least k. The theorem also leads to a simple and efficient method of initializing the GFSR generator so that the sequence to be generated is k-distributed.
Keywords
TrinomialInitializationPseudorandom number generatorSequence (biology)Shift registerGenerator (circuit theory)Discrete mathematicsComputer scienceSimple (philosophy)ErgodicityClass (philosophy)MathematicsAlgorithmPower (physics)Programming languagePhysics
Affiliated Institutions
Related Publications
Free energy minimisation algorithmfor decoding and cryptanalysis
An algorithm is derived for inferring a binary vector s given noisy observations of As modulo 2, where A is a binary matrix. The binary vector is replaced by a vector of probabi...
Maximum distanceq-nary codes
A <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</tex> -nary error-correcting code with <tex xmlns:mml="http://www.w3.org/1998/...
Mixed-state entanglement and quantum error correction
Entanglement purification protocols (EPP) and quantum error-correcting codes (QECC) provide two ways of protecting quantum states from interaction with the environment. In an EP...
Properties of statistical tests of neutrality for DNA polymorphism data.
Abstract A class of statistical tests based on molecular polymorphism data is studied to determine size and power properties. The class includes Tajima's D statistic as well as ...
SOME PUBLIC-KEY CRYPTO-FUNCTIONS AS INTRACTABLE AS FACTORIZATION
In the RSA public-key crypto system a message M (<R) is encrypted by calculating K≡me (mod R), where 0<K<R and R, e are integers which are made public. The recipient of K can de...
Publication Info
- Year
- 1983
- Type
- article
- Volume
- 26
- Issue
- 7
- Pages
- 516-523
- Citations
- 100
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
100
OpenAlex
Cite This
Masanori Fushimi,
Shu Tezuka
(1983).
The <i>k</i> -distribution of generalized feedback shift register pseudorandom numbers.
Communications of the ACM
, 26
(7)
, 516-523.
https://doi.org/10.1145/358150.358159
Identifiers
- DOI
- 10.1145/358150.358159