An extension of binary threshold sequences from Fermat quotients

Previous Article
A note on diagonal and Hermitian hypersurfaces
AMC Home
This Issue
Next Article
Further results on semi-bent functions in polynomial form

November 2016, 10(4): 743-752. doi: 10.3934/amc.2016038

An extension of binary threshold sequences from Fermat quotients

Xiaoni Du ^1, , Chenhuang Wu ^2, and Wanyin Wei ^1,

1.	College of Mathematics and Statistics, Northwest Normal University, Lanzhou, Gansu 730070, China, China
2.	School of Mathematics, Putian University, Putian, Fujian 351100, China

Received September 2014 Published November 2016

Abstract
Related Papers

We extend the construction of $p^2$-periodic binary threshold sequences derived from Fermat quotients to the $d$-ary case where $d$ is an odd prime divisor of $p-1$, and then by defining cyclotomic classes modulo $p^{2}$, we present exact values of the linear complexity under the condition of $d^{p-1}\not \equiv 1 \pmod {p^2}$. Also, we extend the results to the Euler quotients modulo $p^{r}$ with odd prime $p$ and $r \geq 2$. The linear complexity is very close to the period and is of desired value for cryptographic purpose. The results extend the linear complexity of the corresponding $d$-ary sequences when $d$ is a primitive root modulo $p^2$ in earlier work. Finally, partial results for the linear complexity of the sequences when $d^{p-1} \equiv 1 \pmod {p^2}$ is given.

Keywords: Euler quotients, linear complexity, Fermat quotients, cryptography., pseudorandom sequences.

Mathematics Subject Classification: Primary: 94A55, 94A60; Secondary: 65C1.

Citation: Xiaoni Du, Chenhuang Wu, Wanyin Wei. An extension of binary threshold sequences from Fermat quotients. Advances in Mathematics of Communications, 2016, 10 (4) : 743-752. doi: 10.3934/amc.2016038

References:

[1]	T. Agoh, K. Dilcher and L. Skula, Fermat quotients for composite moduli, J. Number Theory, 66 (1997), 29-50. doi: 10.1006/jnth.1997.2162.
[2]	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.
[3]	Z. Chen, L. Hu and X. Du, Linear complexity of some binary sequences derived from Fermat quotients, China Commun., 9 (2012), 105-108. doi: 10.1007/s10623-012-9608-3.
[4]	Z. Chen, A. Ostafe and A. Winterhof, Structure of pseudorandom numbers derived from Fermat quotients, in Proc. WAIFI 2010, Springer-Verlag, Heidelberg, 2010, 73-85. doi: 10.1007/978-3-642-13797-6_6.
[5]	Z. Chen and A. Winterhof, On the distribution of pseudorandom numbers and vectors derived from Euler-Fermat quotients, Int. J. Number Theory, 8 (2012), 631-641. doi: 10.1142/S1793042112500352.
[6]	R. Crandall, K. Dilcher and C. Pomerance, A search for Wieferich and Wilson primes, Math. Comp., 66 (1997), 433-449. doi: 10.1090/S0025-5718-97-00791-6.
[7]	A. Cunningham, Period-lengths of circulates, Messenger Math., 29 (1900), 145-179.
[8]	X. Du, Z. Chen and L. Hu, Linear complexity of binary sequences derived from Euler quotients with prime-power modulus, Inform. Proc. Letters, 112 (2012), 604-609. doi: 10.1016/j.ipl.2012.04.011.
[9]	X. Du, A. Klapper and Z. Chen, Linear complexity of pseudorandom sequences generated by Fermat quotients and their generalizations, Inform. Proc. Letters, 112 (2012), 233-237. doi: 10.1016/j.ipl.2011.11.017.
[10]	R. Ernvall and T. Metsänkylä, On the p-divisibility of Fermat quotients, Math. Comp., 66 (1997), 1353-1365. doi: 10.1090/S0025-5718-97-00843-0.
[11]	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.
[12]	A. Granville, Some conjectures related to Fermat's Last Theorem, in Number Theory, Walter de Gruyter, Berlin, 1990, 177-192.
[13]	W. Keller and J. Richstein, Prime solutions $p$ of $a^{p-1}\equiv 1$ (mod $p^2$) for prime bases $a$, Math. Comput., 74 (2005), 927-936. doi: 10.1090/S0025-5718-04-01666-7.
[14]	R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, Reading, MA, 1983.
[15]	J. L. Massey, Shift register synthesis and BCH decoding, IEEE Trans. Inform. Theory, 15 (1969), 122-127.
[16]	A. Ostafe and I. E. Shparlinski, Pseudorandomness and dynamics of Fermat quotients, SIAM J. Discrete Math., 25 (2011), 50-71. doi: 10.1137/100798466.
[17]	A. Winterhof, Linear complexity and related complexity measures, in Selected Topics in Information and Coding Theory, World Scientic, 2010, 3-40. doi: 10.1142/9789812837172_0001.
[18]	M. Sha, The arithmetic of Carmichael quotients, preprint, arXiv:1108.2579 doi: 10.1007/s10998-014-0079-3.
[19]	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.
[20]	I. E. Shparlinski, Character sums with Fermat quotients, Quart. J. Math., 62 (2011), 1031-1043. doi: 10.1093/qmath/haq028.
[21]	I. E. Shparlinski, Fermat quotients: Exponential sums, value set and primitive roots, Bull. London Math. Soc., 43 (2011), 1228-1238. doi: 10.1112/blms/bdr058.
[22]	I. E. Shparlinski, On the value set of Fermat quotients, Proc. Amer. Math. Soc., 140 (2012), 1199-1206. doi: 10.1090/S0002-9939-2011-11203-6.

show all references

References:

[1]	T. Agoh, K. Dilcher and L. Skula, Fermat quotients for composite moduli, J. Number Theory, 66 (1997), 29-50. doi: 10.1006/jnth.1997.2162.
[2]	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.
[3]	Z. Chen, L. Hu and X. Du, Linear complexity of some binary sequences derived from Fermat quotients, China Commun., 9 (2012), 105-108. doi: 10.1007/s10623-012-9608-3.
[4]	Z. Chen, A. Ostafe and A. Winterhof, Structure of pseudorandom numbers derived from Fermat quotients, in Proc. WAIFI 2010, Springer-Verlag, Heidelberg, 2010, 73-85. doi: 10.1007/978-3-642-13797-6_6.
[5]	Z. Chen and A. Winterhof, On the distribution of pseudorandom numbers and vectors derived from Euler-Fermat quotients, Int. J. Number Theory, 8 (2012), 631-641. doi: 10.1142/S1793042112500352.
[6]	R. Crandall, K. Dilcher and C. Pomerance, A search for Wieferich and Wilson primes, Math. Comp., 66 (1997), 433-449. doi: 10.1090/S0025-5718-97-00791-6.
[7]	A. Cunningham, Period-lengths of circulates, Messenger Math., 29 (1900), 145-179.
[8]	X. Du, Z. Chen and L. Hu, Linear complexity of binary sequences derived from Euler quotients with prime-power modulus, Inform. Proc. Letters, 112 (2012), 604-609. doi: 10.1016/j.ipl.2012.04.011.
[9]	X. Du, A. Klapper and Z. Chen, Linear complexity of pseudorandom sequences generated by Fermat quotients and their generalizations, Inform. Proc. Letters, 112 (2012), 233-237. doi: 10.1016/j.ipl.2011.11.017.
[10]	R. Ernvall and T. Metsänkylä, On the p-divisibility of Fermat quotients, Math. Comp., 66 (1997), 1353-1365. doi: 10.1090/S0025-5718-97-00843-0.
[11]	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.
[12]	A. Granville, Some conjectures related to Fermat's Last Theorem, in Number Theory, Walter de Gruyter, Berlin, 1990, 177-192.
[13]	W. Keller and J. Richstein, Prime solutions $p$ of $a^{p-1}\equiv 1$ (mod $p^2$) for prime bases $a$, Math. Comput., 74 (2005), 927-936. doi: 10.1090/S0025-5718-04-01666-7.
[14]	R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, Reading, MA, 1983.
[15]	J. L. Massey, Shift register synthesis and BCH decoding, IEEE Trans. Inform. Theory, 15 (1969), 122-127.
[16]	A. Ostafe and I. E. Shparlinski, Pseudorandomness and dynamics of Fermat quotients, SIAM J. Discrete Math., 25 (2011), 50-71. doi: 10.1137/100798466.
[17]	A. Winterhof, Linear complexity and related complexity measures, in Selected Topics in Information and Coding Theory, World Scientic, 2010, 3-40. doi: 10.1142/9789812837172_0001.
[18]	M. Sha, The arithmetic of Carmichael quotients, preprint, arXiv:1108.2579 doi: 10.1007/s10998-014-0079-3.
[19]	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.
[20]	I. E. Shparlinski, Character sums with Fermat quotients, Quart. J. Math., 62 (2011), 1031-1043. doi: 10.1093/qmath/haq028.
[21]	I. E. Shparlinski, Fermat quotients: Exponential sums, value set and primitive roots, Bull. London Math. Soc., 43 (2011), 1228-1238. doi: 10.1112/blms/bdr058.
[22]	I. E. Shparlinski, On the value set of Fermat quotients, Proc. Amer. Math. Soc., 140 (2012), 1199-1206. doi: 10.1090/S0002-9939-2011-11203-6.

[1]	Zhixiong Chen, Vladimir Edemskiy, Pinhui Ke, Chenhuang Wu. On $k$-error linear complexity of pseudorandom binary sequences derived from Euler quotients. Advances in Mathematics of Communications, 2018, 12 (4) : 805-816. doi: 10.3934/amc.2018047
[2]	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, 2021 doi: 10.3934/amc.2021008
[3]	Alina Ostafe, Igor E. Shparlinski, Arne Winterhof. On the generalized joint linear complexity profile of a class of nonlinear pseudorandom multisequences. Advances in Mathematics of Communications, 2010, 4 (3) : 369-379. doi: 10.3934/amc.2010.4.369
[4]	Grant Cairns, Barry Jessup, Marcel Nicolau. Topologically transitive homeomorphisms of quotients of tori. Discrete and Continuous Dynamical Systems, 1999, 5 (2) : 291-300. doi: 10.3934/dcds.1999.5.291
[5]	Gilberto Bini, Margarida Melo, Filippo Viviani. On GIT quotients of Hilbert and Chow schemes of curves. Electronic Research Announcements, 2012, 19: 33-40. doi: 10.3934/era.2012.19.33
[6]	R. V. Gurjar, Mariusz Koras and Peter Russell. Two dimensional quotients of $CC^n$ by a reductive group. Electronic Research Announcements, 2008, 15: 62-64. doi: 10.3934/era.2008.15.62
[7]	Eckhard Meinrenken. Quotients of double vector bundles and multigraded bundles. Journal of Geometric Mechanics, 2022, 14 (2) : 307-329. doi: 10.3934/jgm.2021027
[8]	Liqin Hu, Qin Yue, Fengmei Liu. Linear complexity of cyclotomic sequences of order six and BCH codes over GF(3). Advances in Mathematics of Communications, 2014, 8 (3) : 297-312. doi: 10.3934/amc.2014.8.297
[9]	Jianqin Zhou, Wanquan Liu, Xifeng Wang. Structure analysis on the k-error linear complexity for 2ⁿ-periodic binary sequences. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1743-1757. doi: 10.3934/jimo.2017016
[10]	Lin Yi, Xiangyong Zeng, Zhimin Sun, Shasha Zhang. On the linear complexity and autocorrelation of generalized cyclotomic binary sequences with period $ 4p^n $. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021019
[11]	Jérôme Ducoat, Frédérique Oggier. On skew polynomial codes and lattices from quotients of cyclic division algebras. Advances in Mathematics of Communications, 2016, 10 (1) : 79-94. doi: 10.3934/amc.2016.10.79
[12]	Stéphane Sabourau. Growth of quotients of groups acting by isometries on Gromov-hyperbolic spaces. Journal of Modern Dynamics, 2013, 7 (2) : 269-290. doi: 10.3934/jmd.2013.7.269
[13]	Marco Zambon, Chenchang Zhu. Distributions and quotients on degree $1$ NQ-manifolds and Lie algebroids. Journal of Geometric Mechanics, 2012, 4 (4) : 469-485. doi: 10.3934/jgm.2012.4.469
[14]	Frédérique Oggier, B. A. Sethuraman. Quotients of orders in cyclic algebras and space-time codes. Advances in Mathematics of Communications, 2013, 7 (4) : 441-461. doi: 10.3934/amc.2013.7.441
[15]	Siyuan Tang. New time-changes of unipotent flows on quotients of Lorentz groups. Journal of Modern Dynamics, 2022, 18: 13-67. doi: 10.3934/jmd.2022002
[16]	Jianqin Zhou, Wanquan Liu, Xifeng Wang. Complete characterization of the first descent point distribution for the k-error linear complexity of 2ⁿ-periodic binary sequences. Advances in Mathematics of Communications, 2017, 11 (3) : 429-444. doi: 10.3934/amc.2017036
[17]	Jianqin Zhou, Wanquan Liu, Xifeng Wang, Guanglu Zhou. On the $ k $-error linear complexity for $ p^n $-periodic binary sequences via hypercube theory. Mathematical Foundations of Computing, 2019, 2 (4) : 279-297. doi: 10.3934/mfc.2019018
[18]	Jiarong Peng, Xiangyong Zeng, Zhimin Sun. Finite length sequences with large nonlinear complexity. Advances in Mathematics of Communications, 2018, 12 (1) : 215-230. doi: 10.3934/amc.2018015
[19]	Huaning Liu, Yixin Ren. On the pseudorandom properties of $ k $-ary Sidel'nikov sequences. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021038
[20]	Cheng Zheng. Sparse equidistribution of unipotent orbits in finite-volume quotients of $\text{PSL}(2,\mathbb R)$. Journal of Modern Dynamics, 2016, 10: 1-21. doi: 10.3934/jmd.2016.10.1

2021 Impact Factor: 1.015

Tools

Metrics

Other articles
by authors

on AIMS
Xiaoni Du Chenhuang Wu Wanyin Wei
on Google Scholar
Xiaoni Du Chenhuang Wu Wanyin Wei

[Back to Top]