Pseudo Random Ternary Sequence and Its Autocorrelation Property Over Finite Field

Full Text (PDF, 699KB), PP.54-63

Author(s)

1. Graduate School of Natural Science and Technology, Okayama University, 3-1-1 Tsushima-naka, Kita-ku, Okayama 700-8530, Japan

2. Department of Computer Science and Engineering, Hajee Mohammad Danesh Science and Technology University, Dinajpur-5200, Bangladesh

* Corresponding author.

Received: 14 Jun. 2017 / Revised: 16 Jul. 2017 / Accepted: 9 Aug. 2017 / Published: 8 Sep. 2017

Index Terms

Ternary sequence, finite field, autocorrelation, primitive polynomial, trace function, Legendre symbol

Abstract

In this paper, the authors have proposed an innovative approach for generating a pseudo random ternary sequence by using a primitive polynomial, trace function, and Legendre symbol over odd characteristics field. Let p be an odd prime number, FP be an odd characteristic prime field, and m be the degree of the primitive polynomial f(x) Let w be its zero and a primitive element in Fpm* In the beginning, a primitive polynomial f(x) generates maximum length vector sequence, then the trace function Tr(.) is used to map an element of the extension field (Fpm) to an element of the prime field Fthen non-zero scalar A∈Fp is added to the trace value, and finally the Legendre symbol (a/p) is utilized to map the scalars into ternary sequence having the values, {0,1,and -1} By applying the new parameter A the period of the sequence is extended to its maximum value that is n=pm-1 Hence, our proposed sequence has some parameters such as p,m,and A This paper mathematically explains the properties of the proposed ternary sequence such as period and autocorrelation. Additionally, these properties are also justified based on some experimental results.

Cite This Paper

Md. Arshad Ali, Emran Ali, Md. Ahsan Habib, Md. Nadim, Takuya Kusaka, Yasuyuki Nogami,"Pseudo Random Ternary Sequence and Its Autocorrelation Property Over Finite Field", International Journal of Computer Network and Information Security(IJCNIS), Vol.9, No.9, pp.54-63, 2017.DOI: 10.5815/ijcnis.2017.09.07

Reference

[1] W. Cusick, C. Ding, and A. Renvall, Stream Ciphers and Number Theory, North-Holland Mathematical Library. Elsevier Science, 1998.

[2] S. W. Golomb, Shift Register Sequences, Holden-Day, San Francisco, 1967.

[3] M. K. Simon, J. K. Omura, R. A. Scholtz, and B. K. Levitt, Spread Spectrum Communications Handbook, McGraw-Hill, 1994.

[4] R. Lidl and H. Niederreiter, Finite Fields, Encyclopaedia of Mathematics and Its Applications, Cambridge University Press, 1984.

[5] A. J. Menezes, P. C. Van Oorschot, and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996.

[6] A. Kinga, F. Aline, E. Christain, “Generation and Testing of Random Numbers for Cryptographic Applications”, Proceedings of Romania Academy, vol. 13, no. 4, pp. 368-377, 2012.

[7] C. Ding, T. Helleseth, and W. Shan, “On the Linear Complexity of Legendre Sequences”, IEEE Trans. on Inform. Theory, vol. 44, pp. 1276-1278, 1998.

[8] N. Zierler, “Linear Recurring Sequences”, Journal of the Society for Industrial and Applied Mathematics (SIAM), vol. 7, issue 1, pp. 31-48, 1959.

[9] J. S. No, H. K. Lee, H. Chung, H. Y. Song, and K. Yang, “Trace Representation of Legendre Sequences of Mersenne Prime Period”, IEEE Trans. on Inform. Theory, vol. 42, pp. 2254-2255, 1996.

[10] N. Zierler, Legendre Sequence, M.I.T. Lincoln Publications, 1958.

[11] A. Md. Arshad, Y. Nogami, “A Pseudo-Random Binary Sequence Generated by Using Primitive Polynomial of Degree over Odd Characteristic Field Fp”, International Conference on Consumer Electronics-Taiwan, pp.15-16, May 2016.

[12] Y. Nogami, K. Tada, and S. Uehara, “A Geometric Sequence Binarized with Legendre Symbol over Odd Characteristic Field and Its Properties”, IEICE Trans., vol. 97-A, no. 12, pp. 2336–2342, 2014.

[13] E. R. Berlekamp, Algebraic Coding Theory, Aegean Park Press, 1984.

[14] B. Fassi, A. Djebbari, and A. Taleb-Ahmed, “Ternary Zero Correlation Zone Sequence Sets for Asynchronous DS-CDMA”, Journal Communications and Network, vol.6, issue 4, pp. 209-217, 2014.

[15] P. Z.Fan, “Spreading Sequence Design and Theoretical Limits for quasi-synchronous CDMA Systems”, EURASIP Journal on wireless Communications and Networking, pp. 19-31, 2004.

[16] H. Donelan, T. O’Farrell, “Large Families of Ternary Sequences with Aperiodic Zero Correlation Zones for a MC-DS-CDMA System”, Proc. Of 13 th. IEEE Intl. SPIMRC, vol. 5, pp. 2322-2326, 2002.

[17] Y. Nogami, S. Uehara, K. Tsuchiya, N. Begum, H. Ino, and R. H. Morelos-Zaragoza, “A Multi-value Sequence Generated by Power Residue Symbol and Trace Function over Odd Characteristic Field”, IEICE Transactions on Fundamentals, vol. E99-A, issue 12, pp. 2226-2237, 2016.

[18] B. Nasima, Y. Nogami, S. Uehara, and R. H. Morelos-Zaragoza, “Multi-valued Sequences Generated by Power Residue Symbol over Odd Characteristic Fields”, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E100.A, issue 4, pp. 922-929,2017.

[19] Y. Nogami, K. Tada, and S. Uehara, “A Geometric Sequence Binarized with Legendre Symbol over Odd Characteristic Field and Its Properties”, IEICE Transactions on Fundamentals, vol. E97-A, issue 12, pp. 2336-2342, 2014.