Pseudorandom number generators have been widely used in Monte Carlo methods, communication systems, cryptography and so on. For cryptographic applications, pseudorandom number generators are required to generate sequences which have good statistical properties, long period and unpredictability. A Dickson generator is a nonlinear congruential generator whose recurrence function is the Dickson polynomial. Aly and Winterhof obtained a lower bound on the linear complexity profile of a Dickson generator. Moreover Vasiga and Shallit studied the state diagram given by the Dickson polynomial of degree two. However, they do not specify sets of initial values which generate a long period sequence. In this paper, we show conditions for parameters and initial values to generate long period sequences, and asymptotic properties for periods by numerical experiments. We specify sets of initial values which generate a long period sequence. For suitable parameters, every element of this set occurs exactly once as a component of generating sequence in one period. In order to obtain sets of initial values, we consider a logistic generator proposed by Miyazaki, Araki, Uehara and Nogami, which is obtained from a Dickson generator of degree two with a linear transformation. Moreover, we remark on the linear complexity profile of the logistic generator. The sets of initial values are described by values of the Legendre symbol. The main idea is to introduce a structure of a hyperbola to the sets of initial values. Our results ensure that generating sequences of Dickson generator of degree two have long period. As a consequence, the Dickson generator of degree two has some good properties for cryptographic applications.
Kazuyoshi TSUCHIYA
the Koden Electronics Co., Ltd.
Yasuyuki NOGAMI
Okayama University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Kazuyoshi TSUCHIYA, Yasuyuki NOGAMI, "Long Period Sequences Generated by the Logistic Map over Finite Fields with Control Parameter Four" in IEICE TRANSACTIONS on Fundamentals,
vol. E100-A, no. 9, pp. 1816-1824, September 2017, doi: 10.1587/transfun.E100.A.1816.
Abstract: Pseudorandom number generators have been widely used in Monte Carlo methods, communication systems, cryptography and so on. For cryptographic applications, pseudorandom number generators are required to generate sequences which have good statistical properties, long period and unpredictability. A Dickson generator is a nonlinear congruential generator whose recurrence function is the Dickson polynomial. Aly and Winterhof obtained a lower bound on the linear complexity profile of a Dickson generator. Moreover Vasiga and Shallit studied the state diagram given by the Dickson polynomial of degree two. However, they do not specify sets of initial values which generate a long period sequence. In this paper, we show conditions for parameters and initial values to generate long period sequences, and asymptotic properties for periods by numerical experiments. We specify sets of initial values which generate a long period sequence. For suitable parameters, every element of this set occurs exactly once as a component of generating sequence in one period. In order to obtain sets of initial values, we consider a logistic generator proposed by Miyazaki, Araki, Uehara and Nogami, which is obtained from a Dickson generator of degree two with a linear transformation. Moreover, we remark on the linear complexity profile of the logistic generator. The sets of initial values are described by values of the Legendre symbol. The main idea is to introduce a structure of a hyperbola to the sets of initial values. Our results ensure that generating sequences of Dickson generator of degree two have long period. As a consequence, the Dickson generator of degree two has some good properties for cryptographic applications.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E100.A.1816/_p
Copy
@ARTICLE{e100-a_9_1816,
author={Kazuyoshi TSUCHIYA, Yasuyuki NOGAMI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Long Period Sequences Generated by the Logistic Map over Finite Fields with Control Parameter Four},
year={2017},
volume={E100-A},
number={9},
pages={1816-1824},
abstract={Pseudorandom number generators have been widely used in Monte Carlo methods, communication systems, cryptography and so on. For cryptographic applications, pseudorandom number generators are required to generate sequences which have good statistical properties, long period and unpredictability. A Dickson generator is a nonlinear congruential generator whose recurrence function is the Dickson polynomial. Aly and Winterhof obtained a lower bound on the linear complexity profile of a Dickson generator. Moreover Vasiga and Shallit studied the state diagram given by the Dickson polynomial of degree two. However, they do not specify sets of initial values which generate a long period sequence. In this paper, we show conditions for parameters and initial values to generate long period sequences, and asymptotic properties for periods by numerical experiments. We specify sets of initial values which generate a long period sequence. For suitable parameters, every element of this set occurs exactly once as a component of generating sequence in one period. In order to obtain sets of initial values, we consider a logistic generator proposed by Miyazaki, Araki, Uehara and Nogami, which is obtained from a Dickson generator of degree two with a linear transformation. Moreover, we remark on the linear complexity profile of the logistic generator. The sets of initial values are described by values of the Legendre symbol. The main idea is to introduce a structure of a hyperbola to the sets of initial values. Our results ensure that generating sequences of Dickson generator of degree two have long period. As a consequence, the Dickson generator of degree two has some good properties for cryptographic applications.},
keywords={},
doi={10.1587/transfun.E100.A.1816},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - Long Period Sequences Generated by the Logistic Map over Finite Fields with Control Parameter Four
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1816
EP - 1824
AU - Kazuyoshi TSUCHIYA
AU - Yasuyuki NOGAMI
PY - 2017
DO - 10.1587/transfun.E100.A.1816
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E100-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2017
AB - Pseudorandom number generators have been widely used in Monte Carlo methods, communication systems, cryptography and so on. For cryptographic applications, pseudorandom number generators are required to generate sequences which have good statistical properties, long period and unpredictability. A Dickson generator is a nonlinear congruential generator whose recurrence function is the Dickson polynomial. Aly and Winterhof obtained a lower bound on the linear complexity profile of a Dickson generator. Moreover Vasiga and Shallit studied the state diagram given by the Dickson polynomial of degree two. However, they do not specify sets of initial values which generate a long period sequence. In this paper, we show conditions for parameters and initial values to generate long period sequences, and asymptotic properties for periods by numerical experiments. We specify sets of initial values which generate a long period sequence. For suitable parameters, every element of this set occurs exactly once as a component of generating sequence in one period. In order to obtain sets of initial values, we consider a logistic generator proposed by Miyazaki, Araki, Uehara and Nogami, which is obtained from a Dickson generator of degree two with a linear transformation. Moreover, we remark on the linear complexity profile of the logistic generator. The sets of initial values are described by values of the Legendre symbol. The main idea is to introduce a structure of a hyperbola to the sets of initial values. Our results ensure that generating sequences of Dickson generator of degree two have long period. As a consequence, the Dickson generator of degree two has some good properties for cryptographic applications.
ER -