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

Metrics

  • PDF downloads (5)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]