# 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. doi: 10.1006/jnth.1997.2162. Google Scholar [2] Z. Chen and X. Du, On the linear complexity of binary threshold sequences derived from Fermat quotients,, Des. Codes Cryptogr., 67 (2013), 317. doi: 10.1007/s10623-012-9608-3. Google Scholar [3] Z. Chen, L. Hu and X. Du, Linear complexity of some binary sequences derived from Fermat quotients,, China Commun., 9 (2012), 105. doi: 10.1007/s10623-012-9608-3. Google Scholar [4] Z. Chen, A. Ostafe and A. Winterhof, Structure of pseudorandom numbers derived from Fermat quotients,, in Proc. WAIFI 2010, (2010), 73. doi: 10.1007/978-3-642-13797-6_6. Google Scholar [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. doi: 10.1142/S1793042112500352. Google Scholar [6] R. Crandall, K. Dilcher and C. Pomerance, A search for Wieferich and Wilson primes,, Math. Comp., 66 (1997), 433. doi: 10.1090/S0025-5718-97-00791-6. Google Scholar [7] A. Cunningham, Period-lengths of circulates,, Messenger Math., 29 (1900), 145. Google Scholar [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. doi: 10.1016/j.ipl.2012.04.011. Google Scholar [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. doi: 10.1016/j.ipl.2011.11.017. Google Scholar [10] R. Ernvall and T. Metsänkylä, On the p-divisibility of Fermat quotients,, Math. Comp., 66 (1997), 1353. doi: 10.1090/S0025-5718-97-00843-0. Google Scholar [11] D. Gomez and A. Winterhof, Multiplicative character sums of Fermat quotients and pseudorandom sequences,, Period. Math. Hungar., 64 (2012), 161. doi: 10.1007/s10998-012-3747-1. Google Scholar [12] A. Granville, Some conjectures related to Fermat's Last Theorem,, in Number Theory, (1990), 177. Google Scholar [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. doi: 10.1090/S0025-5718-04-01666-7. Google Scholar [14] R. Lidl and H. Niederreiter, Finite Fields,, Addison-Wesley, (1983). Google Scholar [15] J. L. Massey, Shift register synthesis and BCH decoding,, IEEE Trans. Inform. Theory, 15 (1969), 122. Google Scholar [16] A. Ostafe and I. E. Shparlinski, Pseudorandomness and dynamics of Fermat quotients,, SIAM J. Discrete Math., 25 (2011), 50. doi: 10.1137/100798466. Google Scholar [17] A. Winterhof, Linear complexity and related complexity measures,, in Selected Topics in Information and Coding Theory, (2010), 3. doi: 10.1142/9789812837172_0001. Google Scholar [18] M. Sha, The arithmetic of Carmichael quotients,, preprint, (). doi: 10.1007/s10998-014-0079-3. Google Scholar [19] I. E. Shparlinski, Bounds of multiplicative character sums with Fermat quotients of primes,, Bull. Aust. Math. Soc., 83 (2011), 456. doi: 10.1017/S000497271000198X. Google Scholar [20] I. E. Shparlinski, Character sums with Fermat quotients,, Quart. J. Math., 62 (2011), 1031. doi: 10.1093/qmath/haq028. Google Scholar [21] I. E. Shparlinski, Fermat quotients: Exponential sums, value set and primitive roots,, Bull. London Math. Soc., (2011), 1228. doi: 10.1112/blms/bdr058. Google Scholar [22] I. E. Shparlinski, On the value set of Fermat quotients,, Proc. Amer. Math. Soc., 140 (2012), 1199. doi: 10.1090/S0002-9939-2011-11203-6. Google Scholar

show all references

##### References:
 [1] T. Agoh, K. Dilcher and L. Skula, Fermat quotients for composite moduli,, J. Number Theory, 66 (1997), 29. doi: 10.1006/jnth.1997.2162. Google Scholar [2] Z. Chen and X. Du, On the linear complexity of binary threshold sequences derived from Fermat quotients,, Des. Codes Cryptogr., 67 (2013), 317. doi: 10.1007/s10623-012-9608-3. Google Scholar [3] Z. Chen, L. Hu and X. Du, Linear complexity of some binary sequences derived from Fermat quotients,, China Commun., 9 (2012), 105. doi: 10.1007/s10623-012-9608-3. Google Scholar [4] Z. Chen, A. Ostafe and A. Winterhof, Structure of pseudorandom numbers derived from Fermat quotients,, in Proc. WAIFI 2010, (2010), 73. doi: 10.1007/978-3-642-13797-6_6. Google Scholar [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. doi: 10.1142/S1793042112500352. Google Scholar [6] R. Crandall, K. Dilcher and C. Pomerance, A search for Wieferich and Wilson primes,, Math. Comp., 66 (1997), 433. doi: 10.1090/S0025-5718-97-00791-6. Google Scholar [7] A. Cunningham, Period-lengths of circulates,, Messenger Math., 29 (1900), 145. Google Scholar [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. doi: 10.1016/j.ipl.2012.04.011. Google Scholar [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. doi: 10.1016/j.ipl.2011.11.017. Google Scholar [10] R. Ernvall and T. Metsänkylä, On the p-divisibility of Fermat quotients,, Math. Comp., 66 (1997), 1353. doi: 10.1090/S0025-5718-97-00843-0. Google Scholar [11] D. Gomez and A. Winterhof, Multiplicative character sums of Fermat quotients and pseudorandom sequences,, Period. Math. Hungar., 64 (2012), 161. doi: 10.1007/s10998-012-3747-1. Google Scholar [12] A. Granville, Some conjectures related to Fermat's Last Theorem,, in Number Theory, (1990), 177. Google Scholar [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. doi: 10.1090/S0025-5718-04-01666-7. Google Scholar [14] R. Lidl and H. Niederreiter, Finite Fields,, Addison-Wesley, (1983). Google Scholar [15] J. L. Massey, Shift register synthesis and BCH decoding,, IEEE Trans. Inform. Theory, 15 (1969), 122. Google Scholar [16] A. Ostafe and I. E. Shparlinski, Pseudorandomness and dynamics of Fermat quotients,, SIAM J. Discrete Math., 25 (2011), 50. doi: 10.1137/100798466. Google Scholar [17] A. Winterhof, Linear complexity and related complexity measures,, in Selected Topics in Information and Coding Theory, (2010), 3. doi: 10.1142/9789812837172_0001. Google Scholar [18] M. Sha, The arithmetic of Carmichael quotients,, preprint, (). doi: 10.1007/s10998-014-0079-3. Google Scholar [19] I. E. Shparlinski, Bounds of multiplicative character sums with Fermat quotients of primes,, Bull. Aust. Math. Soc., 83 (2011), 456. doi: 10.1017/S000497271000198X. Google Scholar [20] I. E. Shparlinski, Character sums with Fermat quotients,, Quart. J. Math., 62 (2011), 1031. doi: 10.1093/qmath/haq028. Google Scholar [21] I. E. Shparlinski, Fermat quotients: Exponential sums, value set and primitive roots,, Bull. London Math. Soc., (2011), 1228. doi: 10.1112/blms/bdr058. Google Scholar [22] I. E. Shparlinski, On the value set of Fermat quotients,, Proc. Amer. Math. Soc., 140 (2012), 1199. doi: 10.1090/S0002-9939-2011-11203-6. Google Scholar
 [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] 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 [3] Grant Cairns, Barry Jessup, Marcel Nicolau. Topologically transitive homeomorphisms of quotients of tori. Discrete & Continuous Dynamical Systems - A, 1999, 5 (2) : 291-300. doi: 10.3934/dcds.1999.5.291 [4] 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 [5] 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 [6] 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 [7] Jianqin Zhou, Wanquan Liu, Xifeng Wang. Structure analysis on the k-error linear complexity for 2n-periodic binary sequences. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1743-1757. doi: 10.3934/jimo.2017016 [8] 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 [9] 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 [10] 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 [11] 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 [12] 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 [13] 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 [14] 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 [15] 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 [16] Gabriele Link. Hopf-Tsuji-Sullivan dichotomy for quotients of Hadamard spaces with a rank one isometry. Discrete & Continuous Dynamical Systems - A, 2018, 38 (11) : 5577-5613. doi: 10.3934/dcds.2018245 [17] Samuel C. Edwards. On the rate of equidistribution of expanding horospheres in finite-volume quotients of SL(2, ${\mathbb{C}}$). Journal of Modern Dynamics, 2017, 11: 155-188. doi: 10.3934/jmd.2017008 [18] Santos González, Llorenç Huguet, Consuelo Martínez, Hugo Villafañe. Discrete logarithm like problems and linear recurring sequences. Advances in Mathematics of Communications, 2013, 7 (2) : 187-195. doi: 10.3934/amc.2013.7.187 [19] Marcela Mejía, J. Urías. An asymptotically perfect pseudorandom generator. Discrete & Continuous Dynamical Systems - A, 2001, 7 (1) : 115-126. doi: 10.3934/dcds.2001.7.115 [20] Pinhui Ke, Yueqin Jiang, Zhixiong Chen. On the linear complexities of two classes of quaternary sequences of even length with optimal autocorrelation. Advances in Mathematics of Communications, 2018, 12 (3) : 525-539. doi: 10.3934/amc.2018031

2018 Impact Factor: 0.879