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.  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-323. 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-108. 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, Springer-Verlag, Heidelberg, 2010, 73-85. 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-641. 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-449. doi: 10.1090/S0025-5718-97-00791-6.  Google Scholar

[7]

A. Cunningham, Period-lengths of circulates, Messenger Math., 29 (1900), 145-179. 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-609. 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-237. 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-1365. 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-168. doi: 10.1007/s10998-012-3747-1.  Google Scholar

[12]

A. Granville, Some conjectures related to Fermat's Last Theorem, in Number Theory, Walter de Gruyter, Berlin, 1990, 177-192.  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-936. doi: 10.1090/S0025-5718-04-01666-7.  Google Scholar

[14]

R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, Reading, MA, 1983.  Google Scholar

[15]

J. L. Massey, Shift register synthesis and BCH decoding, IEEE Trans. Inform. Theory, 15 (1969), 122-127.  Google Scholar

[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.  Google Scholar

[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.  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-462. doi: 10.1017/S000497271000198X.  Google Scholar

[20]

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

[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.  Google Scholar

[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.  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-50. 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-323. 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-108. 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, Springer-Verlag, Heidelberg, 2010, 73-85. 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-641. 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-449. doi: 10.1090/S0025-5718-97-00791-6.  Google Scholar

[7]

A. Cunningham, Period-lengths of circulates, Messenger Math., 29 (1900), 145-179. 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-609. 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-237. 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-1365. 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-168. doi: 10.1007/s10998-012-3747-1.  Google Scholar

[12]

A. Granville, Some conjectures related to Fermat's Last Theorem, in Number Theory, Walter de Gruyter, Berlin, 1990, 177-192.  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-936. doi: 10.1090/S0025-5718-04-01666-7.  Google Scholar

[14]

R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, Reading, MA, 1983.  Google Scholar

[15]

J. L. Massey, Shift register synthesis and BCH decoding, IEEE Trans. Inform. Theory, 15 (1969), 122-127.  Google Scholar

[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.  Google Scholar

[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.  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-462. doi: 10.1017/S000497271000198X.  Google Scholar

[20]

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

[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.  Google Scholar

[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.  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]

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 & 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 & 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]

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

Gabriele Link. Hopf-Tsuji-Sullivan dichotomy for quotients of Hadamard spaces with a rank one isometry. Discrete & Continuous Dynamical Systems, 2018, 38 (11) : 5577-5613. doi: 10.3934/dcds.2018245

2020 Impact Factor: 0.935

Metrics

  • PDF downloads (167)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]