American Institute of Mathematical Sciences

Advanced
doi: 10.3934/amc.2021008

On the correlation measures of orders $ 3 $ and $ 4 $ of binary sequence of period $ p^2 $ derived from Fermat quotients

Huaning Liu , and  Xi Liu

Research Center for Number Theory and Its Applications, School of Mathematics, Northwest University, Xi'an 710127, China

* Corresponding author: Huaning Liu

Received  October 2020 Revised  February 2021 Published  April 2021

Let
$ p $
 be a prime and let
$ n $
 be an integer with
$ (n, p) = 1 $
. The Fermat quotient
$ q_p(n) $
 is defined as
$ q_p(n)\equiv \frac{n^{p-1}-1}{p} \ (\bmod\ p), \quad 0\leq q_p(n)\leq p-1. $
We also define
$ q_p(kp) = 0 $
 for
$ k\in \mathbb{Z} $
. Chen, Ostafe and Winterhof constructed the binary sequence
$ E_{p^2} = \left(e_0, e_1, \cdots, e_{p^2-1}\right)\in \{0, 1\}^{p^2} $
 as
$ \begin{equation*} \begin{split} e_{n} = \left\{\begin{array}{ll} 0, & \hbox{if }\ 0\leq \frac{q_p(n)}{p}<\frac{1}{2}, \\ 1, & \hbox{if }\ \frac{1}{2}\leq \frac{q_p(n)}{p}<1, \end{array} \right. \end{split} \end{equation*} $
and studied the well-distribution measure and correlation measure of order
$ 2 $
 by using estimates for exponential sums of Fermat quotients. In this paper we further study the correlation measures of the sequence. Our results show that the correlation measure of order
$ 3 $
 is quite good, but the
$ 4 $
-order correlation measure of the sequence is very large.
Keywords: Fermat quotient, binary sequence, correlation measure, exponential sum.
Mathematics Subject Classification: Primary: 11K45, 11B50; Secondary: 94A55, 94A60.
Citation: Huaning Liu, Xi Liu. On the correlation measures of orders $ 3 $ and $ 4 $ of binary sequence of period $ p^2 $ derived from Fermat quotients. Advances in Mathematics of Communications, doi: 10.3934/amc.2021008
References:
[1]

H. Aly and A. Winterhof, Boolean functions derived from Fermat quotients, Cryptogr. Commun., 3 (2011), 165-174.  doi: 10.1007/s12095-011-0043-5.  Google Scholar

[2]

M.-C. Chang, Short character sums with Fermat quotients, Acta Arith., 152 (2012), 23-38.  doi: 10.4064/aa152-1-3.  Google Scholar

[3]

Z. Chen, Trace representation and linear complexity of binary sequences derived from Fermat quotients, Sci. China Inf. Sci., 57 (2014), 112109, 10 pp. doi: 10.1007/s11432-014-5092-x.  Google Scholar

[4]

Z. Chen and X. Du, On the linear complexity of binary threshold sequences derived from Fermat quotients, Des. Codes Cryptogr., 67 (2013), 317-323.  doi: 10.1007/s10623-012-9608-3.  Google Scholar

[5]

Z. Chen, L. Hu and X. Du, Linear complexity of some binary sequences derived from Fermat quotients, China Commun., 9 (2012), 105-108.   Google Scholar

[6]

Z. Chen, A. Ostafe and A. Winterhof, Structure of pseudorandom numbers derived from Fermat quotients, In Arithmetic of Finite Fields, Lecture Notes in Computer Science 6087, Springer, Berlin, (2010), 73-85. doi: 10.1007/978-3-642-13797-6_6.  Google Scholar

[7]

Z. Chen and A. Winterhof, Interpolation of Fermat quotients, SIAM J. Discr. Math., 28 (2014), 1-7.  doi: 10.1137/130907951.  Google Scholar

[8]

X. Du, A. Klapper and Z. Chen, Linear complexity of pseudorandom sequences generated by Fermat quotients and their generalizations, Inform. Process. Lett., 112 (2012), 233-237.  doi: 10.1016/j.ipl.2011.11.017.  Google Scholar

[9]

D. Gomez and A. Winterhof, Multiplicative character sums of Fermat quotients and pseudorandom sequences, Period. Math. Hungar., 64 (2012), 161-168.  doi: 10.1007/s10998-012-3747-1.  Google Scholar

[10]

D. R. Heath-Brown, An estimate for Heilbronn's exponential sum, In Analytic Number Theory, Proceedings of a Conference in Honor of Heini Halberstam, Progr. Math., Birkhäuser, Boston, 139 (1996), 451-463.  Google Scholar

[11]

C. Mauduit and A. Sárközy, On finite pseudorandom binary sequencs I: Measure of pseudorandomness, the Legendre symbol, Acta Arith., 82 (1997), 365-377.  doi: 10.4064/aa-82-4-365-377.  Google Scholar

[12]

A. Ostafe and I. E. Shparlinski, Pseudorandomness and dynamics of Fermat quotients, SIAM J. Discr. Math., 25 (2011), 50-71.  doi: 10.1137/100798466.  Google Scholar

[13]

I. E. Shparlinskii, Fermat quotients: Exponential sums, value set and primitive roots, Bull. Lond. Math. Soc., 43 (2011), 1228-1238.  doi: 10.1112/blms/bdr058.  Google Scholar

[14]

I. E. Shparlinski, Character sums with Fermat quotients, Quart. J. Math., 62 (2011), 1031-1043.  doi: 10.1093/qmath/haq028.  Google Scholar

[15]

I. E. Shparlinski, Bounds of multiplicative character sums with Fermat quotients of primes, Bull. Aust. Math. Soc., 83 (2011), 456-462.  doi: 10.1017/S000497271000198X.  Google Scholar

show all references

References:
[1]

H. Aly and A. Winterhof, Boolean functions derived from Fermat quotients, Cryptogr. Commun., 3 (2011), 165-174.  doi: 10.1007/s12095-011-0043-5.  Google Scholar

[2]

M.-C. Chang, Short character sums with Fermat quotients, Acta Arith., 152 (2012), 23-38.  doi: 10.4064/aa152-1-3.  Google Scholar

[3]

Z. Chen, Trace representation and linear complexity of binary sequences derived from Fermat quotients, Sci. China Inf. Sci., 57 (2014), 112109, 10 pp. doi: 10.1007/s11432-014-5092-x.  Google Scholar

[4]

Z. Chen and X. Du, On the linear complexity of binary threshold sequences derived from Fermat quotients, Des. Codes Cryptogr., 67 (2013), 317-323.  doi: 10.1007/s10623-012-9608-3.  Google Scholar

[5]

Z. Chen, L. Hu and X. Du, Linear complexity of some binary sequences derived from Fermat quotients, China Commun., 9 (2012), 105-108.   Google Scholar

[6]

Z. Chen, A. Ostafe and A. Winterhof, Structure of pseudorandom numbers derived from Fermat quotients, In Arithmetic of Finite Fields, Lecture Notes in Computer Science 6087, Springer, Berlin, (2010), 73-85. doi: 10.1007/978-3-642-13797-6_6.  Google Scholar

[7]

Z. Chen and A. Winterhof, Interpolation of Fermat quotients, SIAM J. Discr. Math., 28 (2014), 1-7.  doi: 10.1137/130907951.  Google Scholar

[8]

X. Du, A. Klapper and Z. Chen, Linear complexity of pseudorandom sequences generated by Fermat quotients and their generalizations, Inform. Process. Lett., 112 (2012), 233-237.  doi: 10.1016/j.ipl.2011.11.017.  Google Scholar

[9]

D. Gomez and A. Winterhof, Multiplicative character sums of Fermat quotients and pseudorandom sequences, Period. Math. Hungar., 64 (2012), 161-168.  doi: 10.1007/s10998-012-3747-1.  Google Scholar

[10]

D. R. Heath-Brown, An estimate for Heilbronn's exponential sum, In Analytic Number Theory, Proceedings of a Conference in Honor of Heini Halberstam, Progr. Math., Birkhäuser, Boston, 139 (1996), 451-463.  Google Scholar

[11]

C. Mauduit and A. Sárközy, On finite pseudorandom binary sequencs I: Measure of pseudorandomness, the Legendre symbol, Acta Arith., 82 (1997), 365-377.  doi: 10.4064/aa-82-4-365-377.  Google Scholar

[12]

A. Ostafe and I. E. Shparlinski, Pseudorandomness and dynamics of Fermat quotients, SIAM J. Discr. Math., 25 (2011), 50-71.  doi: 10.1137/100798466.  Google Scholar

[13]

I. E. Shparlinskii, Fermat quotients: Exponential sums, value set and primitive roots, Bull. Lond. Math. Soc., 43 (2011), 1228-1238.  doi: 10.1112/blms/bdr058.  Google Scholar

[14]

I. E. Shparlinski, Character sums with Fermat quotients, Quart. J. Math., 62 (2011), 1031-1043.  doi: 10.1093/qmath/haq028.  Google Scholar

[15]

I. E. Shparlinski, Bounds of multiplicative character sums with Fermat quotients of primes, Bull. Aust. Math. Soc., 83 (2011), 456-462.  doi: 10.1017/S000497271000198X.  Google Scholar

[1]

Mehmet Duran Toksari, Emel Kizilkaya Aydogan, Berrin Atalay, Saziye Sari. Some scheduling problems with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021044
[2]

Xinqun Mei, Jundong Zhou. The interior gradient estimate of prescribed Hessian quotient curvature equation in the hyperbolic space. Communications on Pure & Applied Analysis, 2021, 20 (3) : 1187-1198. doi: 10.3934/cpaa.2021012
[3]

Christoforidou Amalia, Christian-Oliver Ewald. A lattice method for option evaluation with regime-switching asset correlation structure. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1729-1752. doi: 10.3934/jimo.2020042
[4]

Charlene Kalle, Niels Langeveld, Marta Maggioni, Sara Munday. Matching for a family of infinite measure continued fraction transformations. Discrete & Continuous Dynamical Systems, 2020, 40 (11) : 6309-6330. doi: 10.3934/dcds.2020281
[5]

Ugo Bessi. Another point of view on Kusuoka's measure. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3241-3271. doi: 10.3934/dcds.2020404
[6]

Ruchika Sehgal, Aparna Mehra. Worst-case analysis of Gini mean difference safety measure. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1613-1637. doi: 10.3934/jimo.2020037
[7]

Mrinal K. Ghosh, Somnath Pradhan. A nonzero-sum risk-sensitive stochastic differential game in the orthant. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021025
[8]

Manoel J. Dos Santos, Baowei Feng, Dilberto S. Almeida Júnior, Mauro L. Santos. Global and exponential attractors for a nonlinear porous elastic system with delay term. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2805-2828. doi: 10.3934/dcdsb.2020206
[9]

Emanuela R. S. Coelho, Valéria N. Domingos Cavalcanti, Vinicius A. Peralta. Exponential stability for a transmission problem of a nonlinear viscoelastic wave equation. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021055
[10]

Chloé Jimenez. A zero sum differential game with correlated informations on the initial position. A case with a continuum of initial positions. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021009
[11]

Zhaoxia Wang, Hebai Chen. A nonsmooth van der Pol-Duffing oscillator (I): The sum of indices of equilibria is $ -1 $. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021096
[12]

Muberra Allahverdi, Harun Aydilek, Asiye Aydilek, Ali Allahverdi. A better dominance relation and heuristics for Two-Machine No-Wait Flowshops with Maximum Lateness Performance Measure. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1973-1991. doi: 10.3934/jimo.2020054
[13]

Yunjuan Jin, Aifang Qu, Hairong Yuan. Radon measure solutions for steady compressible hypersonic-limit Euler flows passing cylindrically symmetric conical bodies. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021048
[14]

Zhaoxia Wang, Hebai Chen. A nonsmooth van der Pol-Duffing oscillator (II): The sum of indices of equilibria is $ 1 $. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021101
[15]

Jennifer D. Key, Bernardo G. Rodrigues. Binary codes from $ m $-ary $ n $-cubes $ Q^m_n $. Advances in Mathematics of Communications, 2021, 15 (3) : 507-524. doi: 10.3934/amc.2020079
[16]

Claudianor O. Alves, César T. Ledesma. Multiplicity of solutions for a class of fractional elliptic problems with critical exponential growth and nonlocal Neumann condition. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021058
[17]

Xin Zhong. Global strong solution and exponential decay for nonhomogeneous Navier-Stokes and magnetohydrodynamic equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (7) : 3563-3578. doi: 10.3934/dcdsb.2020246
[18]

Quan Hai, Shutang Liu. Mean-square delay-distribution-dependent exponential synchronization of chaotic neural networks with mixed random time-varying delays and restricted disturbances. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3097-3118. doi: 10.3934/dcdsb.2020221
[19]

Lin Yang, Yejuan Wang, Tomás Caraballo. Regularity of global attractors and exponential attractors for $ 2 $D quasi-geostrophic equations with fractional dissipation. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021093

2019 Impact Factor: 0.734

Tools

Article outline

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences