# American Institute of Mathematical Sciences

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

## An extension of binary threshold sequences from Fermat quotients

 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

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.
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, ().  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, ().  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, 2021  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 2n-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 2n-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] 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 [20] Felipe A. Ramírez. Cocycles over higher-rank abelian actions on quotients of semisimple Lie groups. Journal of Modern Dynamics, 2009, 3 (3) : 335-357. doi: 10.3934/jmd.2009.3.335

2020 Impact Factor: 0.935