Existence of sequences satisfying bilinear type recurrence relations

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription or Fee Access

Abstract

We study sequences $\left\{A_n\right\}_{n=-\infty}^{+\infty}$ of elements of an arbitrary field $\mathbb{F}$ that satisfy decompositions of the form $A_{m+n} A_{m-n}=a_1(m) b_1(n)+a_2(m) b_2(n)$, $A_{m+n+1} A_{m-n}=\tilde a_1(m) \tilde b_1(n)+\tilde a_2(m) \tilde b_2(n)$, where $a_1,a_2,b_1,b_2\colon \mathbb{Z}\to\mathbb{F}$. We prove some results concerning the existence and uniqueness of such sequences. The results are used to construct analogs of the Diffie-Hellman and ElGamal cryptographic algorithms. The discrete logarithm problem is considered in the group $(S,+)$, where the set $S$ consists of quadruples $S(n)=(A_{n-1},A_n, A_{n+1}, A_{n+2})$, $n\in\mathbb{Z}$, and $S(n)+S(m)=S(n+m)$.

About the authors

A. A Illarionov

Higher School of Economics-National Research University;Khabarovsk Branch of the Institute of Applied Mathematics of the Far East Branch of the Russian Academy of Sciences

Email: illar_a@list.ru
Moscow, Russia;Khabarovsk, Russia

References

  1. Авдеева М.О., Быковский В.А. Гиперэллиптические системы последовательностей и функций // Дальневост. матем. журн. 2016. Т. 16. № 2. С. 115-122. https://www.mathnet.ru/dvmg326
  2. Илларионов А.А. Гиперэллиптические системы последовательностей ранга 4 // Матем. сб. 2019. Т. 210. № 9. С. 59-88. https://doi.org/10.4213/sm9050
  3. Robinson R.M. Periodicity of Somos Sequences // Proc. Amer. Math. Soc. 1992. V. 116. № 3. P. 613-619. https://doi.org/10.2307/2159426
  4. Shipsey R. Elliptic Divisibility Sequences. PhD Thesis. Goldsmiths College, Univ. London, 2000.
  5. Fomin S., Zelevinsky A. The Laurent Phenomenon // Adv. Appl. Math. 2002. V. 28. № 2. P. 119-144. https://doi.org/10.1006/aama.2001.0770
  6. Swart C.S. Elliptic Curves and Related Sequences. PhD Thesis. Royal Holloway, Univ. London, 2003.
  7. Hone A.N.W. Elliptic Curves and Quadratic Recurrence Sequences // Bull. Lond. Math. Soc. 2005. V. 37. № 2. P. 161-171. https://doi.org/10.1112/S0024609304004163
  8. van der Poorten A.J., Swart C.S. Recurrence Relations for Elliptic Sequences: Every Somos 4 Is a Somos k // Bull. Lond. Math. Soc. 2006. V. 38. № 4. P. 546-554. https://doi.org/10.1112/S0024609306018534
  9. Hone A.N.W. Sigma Function Solution of the Initial Value Problem for Somos 5 Sequences // Trans. Amer. Math. Soc. 2007. V. 359. № 10. P. 5019-5034. https://doi.org/10.1090/S0002-9947-07-04215-8
  10. Hone A.N.W., Swart C.Integrality and the Laurent Phenomenon for Somos 4 and Somos 5 Sequences // Math. Proc. Cambridge Philos. Soc. 2008. V. 145. № 1. P. 65-85. https://doi.org/10.1017/S030500410800114X
  11. Hone A.N.W. Analytic Solutions and Integrability for Bilinear Recurrences of Order Six // Appl. Anal. 2010. V. 89. № 4. P. 473-492. https://doi.org/10.1080/00036810903329977
  12. Fedorov Yu.N., Hone A.N.W. Sigma-Function Solution to the General Somos-6 Recurrence via Hyperelliptic Prym Varieties // J. Integrable Syst. 2016. V. 1. № 1. Art. xyw012 (34 pp.). https://doi.org/10.1093/integr/xyw012
  13. Быковский В.А., Устинов А.В. Сомос-4 и эллиптические системы последовательностей // ДАН. 2016. Т. 471. № 1. С. 7-10. https://doi.org/10.7868/S0869565216310030
  14. Shor P.W. Algorithms for Quantum Computation: Discrete Logarithms and Factoring // Proc. 35th Annu. Symp. on Foundations of Computer Science. Santa Fe, NM, USA. Nov. 20-22, 1994. P. 124-134. https://doi.org/10.1109/SFCS.1994.365700
  15. Илларионов А.А. Асимметричные криптосистемы и гиперэллиптические последовательности // Дальневост. матем. журн. 2019. Т. 19. № 2. С. 185-196. https://www.mathnet.ru/dvmg407
  16. Устинов А.В. Элементарный подход к изучению последовательностей Сомоса // Тр. МИАН. 2019. Т. 305. С. 330-343. https://doi.org/10.4213/tm3990
  17. Ward M. Memoir on Elliptic Divisibility Sequences // Amer. J. Math. 1948. V. 70. № 1. P. 31-74. https://doi.org/10.2307/2371930

Supplementary files

Supplementary Files
Action
1. JATS XML

Copyright (c) 2023 Russian Academy of Sciences