RUS  ENG
Full version
JOURNALS // Problemy Peredachi Informatsii // Archive

Probl. Peredachi Inf., 2023 Volume 59, Issue 2, Pages 102–119 (Mi ppi2400)

Information Protection

Existence of sequences satisfying bilinear type recurrence relations

A. A. Illarionovab

a Higher School of Economics—National Research University, Moscow, Russia
b Khabarovsk Branch of the Institute of Applied Mathematics of the Far East Branch of the Russian Academy of Sciences, Khabarovsk, Russia

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
$$ \begin{aligned}& 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), \end{aligned} $$
where $a_1,a_2,b_1,b_2\colon \mathbb{Z}\to\mathbb{F}$. We prove some results concerning the existence and unique ness 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)$.

Keywords: nonlinear recurrence sequences, Somos sequences, public-key cryptography.

UDC: 621.391 : 519.719.2

Received: 19.01.2023
Revised: 11.05.2023
Accepted: 11.05.2023

DOI: 10.31857/S0555292323020079


 English version:
Problems of Information Transmission, 2023, 59:2, 163–180


© Steklov Math. Inst. of RAS, 2025