The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Des générateurs de nombres pseudo-aléatoires sont nécessaires pour générer des nombres pseudo-aléatoires qui ont de bonnes propriétés statistiques ainsi qu'une imprévisibilité en cryptographie. Une séquence m est une séquence de registre à décalage à rétroaction linéaire avec une période maximale sur un champ fini. Les séquences M ont de bonnes propriétés statistiques, mais nous devons non-linéariser les séquences m à des fins cryptographiques. Une séquence géométrique est une séquence donnée en appliquant une fonction de rétroaction non linéaire à une séquence m. Nogami, Tada et Uehara ont proposé une séquence géométrique dont la fonction de rétroaction non linéaire est donnée par le symbole de Legendre, et ont montré la période, l'autocorrélation périodique et la complexité linéaire de la séquence. De plus, Nogami et al. a proposé une généralisation de la séquence et a montré la période et l'autocorrélation périodique. Dans cet article, nous étudions d’abord la complexité linéaire des séquences géométriques. Dans le cas où la formule de Chan-Games qui décrit la complexité linéaire des séquences géométriques ne tient pas, nous montrons la nouvelle formule en considérant la séquence des nombres complémentaires, la dérivée de Hasse et les classes cyclotomiques. Sous certaines conditions, nous pouvons garantir que les séquences géométriques ont une grande complexité linéaire à partir des résultats sur la complexité linéaire des séquences de Sidel'nikov. Les séquences géométriques ont une longue période et une grande complexité linéaire dans certaines conditions, mais elles n'ont pas la propriété d'équilibre. Afin de construire des séquences possédant la propriété d'équilibre, nous proposons des séquences entrelacées de la séquence géométrique et de son complément. De plus, nous montrons l’autocorrélation périodique et la complexité linéaire des séquences proposées. Les séquences proposées ont la propriété d'équilibre, et ont une grande complexité linéaire si les séquences géométriques en ont une grande.
Kazuyoshi TSUCHIYA
the Koden Electronics Co., Ltd.
Chiaki OGAWA
Okayama University
Yasuyuki NOGAMI
Okayama University
Satoshi UEHARA
the University of Kitakyushu
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.
Copier
Kazuyoshi TSUCHIYA, Chiaki OGAWA, Yasuyuki NOGAMI, Satoshi UEHARA, "Linear Complexity of Geometric Sequences Defined by Cyclotomic Classes and Balanced Binary Sequences Constructed by the Geometric Sequences" in IEICE TRANSACTIONS on Fundamentals,
vol. E101-A, no. 12, pp. 2382-2391, December 2018, doi: 10.1587/transfun.E101.A.2382.
Abstract: Pseudorandom number generators are required to generate pseudorandom numbers which have good statistical properties as well as unpredictability in cryptography. An m-sequence is a linear feedback shift register sequence with maximal period over a finite field. M-sequences have good statistical properties, however we must nonlinearize m-sequences for cryptographic purposes. A geometric sequence is a sequence given by applying a nonlinear feedforward function to an m-sequence. Nogami, Tada and Uehara proposed a geometric sequence whose nonlinear feedforward function is given by the Legendre symbol, and showed the period, periodic autocorrelation and linear complexity of the sequence. Furthermore, Nogami et al. proposed a generalization of the sequence, and showed the period and periodic autocorrelation. In this paper, we first investigate linear complexity of the geometric sequences. In the case that the Chan-Games formula which describes linear complexity of geometric sequences does not hold, we show the new formula by considering the sequence of complement numbers, Hasse derivative and cyclotomic classes. Under some conditions, we can ensure that the geometric sequences have a large linear complexity from the results on linear complexity of Sidel'nikov sequences. The geometric sequences have a long period and large linear complexity under some conditions, however they do not have the balance property. In order to construct sequences that have the balance property, we propose interleaved sequences of the geometric sequence and its complement. Furthermore, we show the periodic autocorrelation and linear complexity of the proposed sequences. The proposed sequences have the balance property, and have a large linear complexity if the geometric sequences have a large one.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E101.A.2382/_p
Copier
@ARTICLE{e101-a_12_2382,
author={Kazuyoshi TSUCHIYA, Chiaki OGAWA, Yasuyuki NOGAMI, Satoshi UEHARA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Linear Complexity of Geometric Sequences Defined by Cyclotomic Classes and Balanced Binary Sequences Constructed by the Geometric Sequences},
year={2018},
volume={E101-A},
number={12},
pages={2382-2391},
abstract={Pseudorandom number generators are required to generate pseudorandom numbers which have good statistical properties as well as unpredictability in cryptography. An m-sequence is a linear feedback shift register sequence with maximal period over a finite field. M-sequences have good statistical properties, however we must nonlinearize m-sequences for cryptographic purposes. A geometric sequence is a sequence given by applying a nonlinear feedforward function to an m-sequence. Nogami, Tada and Uehara proposed a geometric sequence whose nonlinear feedforward function is given by the Legendre symbol, and showed the period, periodic autocorrelation and linear complexity of the sequence. Furthermore, Nogami et al. proposed a generalization of the sequence, and showed the period and periodic autocorrelation. In this paper, we first investigate linear complexity of the geometric sequences. In the case that the Chan-Games formula which describes linear complexity of geometric sequences does not hold, we show the new formula by considering the sequence of complement numbers, Hasse derivative and cyclotomic classes. Under some conditions, we can ensure that the geometric sequences have a large linear complexity from the results on linear complexity of Sidel'nikov sequences. The geometric sequences have a long period and large linear complexity under some conditions, however they do not have the balance property. In order to construct sequences that have the balance property, we propose interleaved sequences of the geometric sequence and its complement. Furthermore, we show the periodic autocorrelation and linear complexity of the proposed sequences. The proposed sequences have the balance property, and have a large linear complexity if the geometric sequences have a large one.},
keywords={},
doi={10.1587/transfun.E101.A.2382},
ISSN={1745-1337},
month={December},}
Copier
TY - JOUR
TI - Linear Complexity of Geometric Sequences Defined by Cyclotomic Classes and Balanced Binary Sequences Constructed by the Geometric Sequences
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2382
EP - 2391
AU - Kazuyoshi TSUCHIYA
AU - Chiaki OGAWA
AU - Yasuyuki NOGAMI
AU - Satoshi UEHARA
PY - 2018
DO - 10.1587/transfun.E101.A.2382
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E101-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2018
AB - Pseudorandom number generators are required to generate pseudorandom numbers which have good statistical properties as well as unpredictability in cryptography. An m-sequence is a linear feedback shift register sequence with maximal period over a finite field. M-sequences have good statistical properties, however we must nonlinearize m-sequences for cryptographic purposes. A geometric sequence is a sequence given by applying a nonlinear feedforward function to an m-sequence. Nogami, Tada and Uehara proposed a geometric sequence whose nonlinear feedforward function is given by the Legendre symbol, and showed the period, periodic autocorrelation and linear complexity of the sequence. Furthermore, Nogami et al. proposed a generalization of the sequence, and showed the period and periodic autocorrelation. In this paper, we first investigate linear complexity of the geometric sequences. In the case that the Chan-Games formula which describes linear complexity of geometric sequences does not hold, we show the new formula by considering the sequence of complement numbers, Hasse derivative and cyclotomic classes. Under some conditions, we can ensure that the geometric sequences have a large linear complexity from the results on linear complexity of Sidel'nikov sequences. The geometric sequences have a long period and large linear complexity under some conditions, however they do not have the balance property. In order to construct sequences that have the balance property, we propose interleaved sequences of the geometric sequence and its complement. Furthermore, we show the periodic autocorrelation and linear complexity of the proposed sequences. The proposed sequences have the balance property, and have a large linear complexity if the geometric sequences have a large one.
ER -