
\documentclass[10pt]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}

\def\udcs{004.75} %Здесь автор определяет УДК своей работы
\def\mscs{68M14} %Здесь автор определяет классификаторы AMS своей работы
\setcounter{page}{144}

\newtheorem{lemma}{Лемма}
\newtheorem{theorem}{Теорема}
\newtheorem{definition}{Определение}
\newtheorem{corollary}{Следствие}
\newtheorem{proposition}{Предложение}

\def\logo{{\bf\huge S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}

\def\semrtop
     {
  \vbox{
     \noindent\logo
     \hspace{80mm}\raisebox{1ex}{ISSN 1813-3304 }

     \vspace{5mm}

     \begin{center}
     {\huge СИБИРСКИЕ \ ЭЛЕКТРОННЫЕ} \\[2mm]
     {\huge МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ} \\[2mm]
     {\large Siberian Electronic Mathematical Reports} \\[1mm]
     {\LARGE\tt{http://semr.math.nsc.ru}}\\[0.5mm]
%     {\small Институт математики им. С.Л.Соболева СО РАН}\\[-1mm]
%     {\small Sobolev Institute of Mathematics SB RAS}
     \end{center}
     \vspace{-3mm}
     \noindent
     \begin{tabular}{c}
     \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa} \\
     \hline\hline
     \end{tabular}

     \vspace{1mm}
     {\flushleft\it Том 16, стр. 144--144 (2019) \hspace{65mm}{\rm\small УДК \udcs}}
     \newline
     	{\rm\small DOI~10.33048/semi.2019.16.xxx}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa}{\rm\small MSC\ \ \mscs }
  }%\vbox
}

\begin{document}
\renewcommand{\refname}{References}


\thispagestyle{empty}

\title[Интерполяция функции сравнения]{Интерполяция функции сравнения чисел над конечными полями}
\author{{М.Г. Бабенко}}%
\address{Babenko Mikhail Grigorievich  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} North-Caucasus Federal University,
\newline\hphantom{iii} Pushkin Street, 1,
\newline\hphantom{iii} 355017, Stavropol, Russia}%
\email{mgbabenko@ncfu.ru}%

\author{{Н.Н. Кучеров}}%
\address{Kucherov Nikolay Nikolaevich  % Контактные данные всех авторов и место работы указываются только на английском языке
	\newline\hphantom{iii} North-Caucasus Federal University,
	\newline\hphantom{iii} Pushkin Street, 1,
	\newline\hphantom{iii} 355017, Stavropol, Russia}%
\email{nkucherov@ncfu.ru}%

\author{{Н.В. Хунг}}%
\address{Nguyen	Viet Hung  % Контактные данные всех авторов и место работы указываются только на английском языке
	\newline\hphantom{iii} Le Quy Don Technical University,
	\newline\hphantom{iii} 236 Hoang Quoc Viet,
	\newline\hphantom{iii} Hanoi, Vietnam}%
\email{hungnv@lqdtu.edu.vn}%

\thanks{\sc Babenko M.G., Kucherov N.N., Hung N.V.,
Comparison function interpolation over finite fields}
\thanks{\copyright \ 2021 Бабенко М.Г., Кучеров Н.Н., Hung N.V.}
\thanks{\rm Работа выполнена при поддержки гранта Министерства науки и высшего образования Российской Федерации 075-15-2021-1010 (13.2251.21.0064)}
\thanks{\it Поступила 1 января 2015 г., опубликована 31 декабря 2015 г.}%


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\sc Abstract. } The computational complexity of the algorithm for comparing encrypted numbers using homomorphic integer ciphers depends on the number of arithmetic addition operations that must be multiplied to calculate the interpolation polynomial. When implementing the scheme of homomorphic comparison of numbers, the multiplicative depth of the algorithm for comparison of numbers is necessary, since integer homomorphic ciphers support a limited number of multiplications. The paper estimates the degree of the interpolation polynomial of the function for comparing encrypted numbers from the work \cite {2}.\medskip

\noindent{\bf Keywords:} interpolation, finite fields, comparison of numbers.
 \end{quote}
}


\section{Введение}

В данной статье нами производится оценка степени интерполяционного многочлена функции сравнения зашифрованных чисел представленного в работе \cite{2}.

Пусть $\mathbb{Z}_{m^d}=\mathbb{Z}_m\left[x\right]/\left(f\left(x\right)\right)$, где $f\left(x\right)$ неприводимый многочлен над $\mathbf{Z}_m$ и $\deg{f\left(x\right)}=d$. Зададим отображение $\mathbb{Z}_{m^d}$ в $\mathbb{Z}_m$ используя абсолютный след $\alpha$:
\begin{equation}
\text{Tr}_{\mathbb{Z}_{m^d}/\mathbb{Z}_m}
\left(\beta\alpha\right)=\alpha+\alpha^m+\cdot+\alpha^{m^{d-1}}
\end{equation}
\noindent где $\alpha\in\mathbb{Z}_{m^d}$

Тогда используя теорему 2.24 из работы \cite{1}[стр. 75] определим линейное отображение $L_{\beta}\left(\alpha\right)$:

\begin{theorem}\cite{1}[стр. 75, теорема 2.24]\label{theorem-lidl}
	Пусть $\mathbf{Z}_{m^d}$ -- конечное расширение конечного поля $\mathbb{Z}_m$. Тогда линейными отображениями из $\mathbb{Z}_{m^d}$  в $\mathbb{Z}_m$ являются отображения $L_{\beta}, \beta\in\mathbb{Z}_{m^d}$, определяемые условием $L_{\beta}\left(\alpha\right)=\text{Tr}_{\mathbb{Z}_{m^d}/\mathbb{Z}_m}
	\left(\beta\alpha\right)$ для всех $\alpha\in\mathbb{Z}_{m^d}$, и только они. При этом если $\beta$ и $\gamma$ -- различные элементы поля $\mathbb{Z}_{m^d}$, то 
	$L_{\beta}\neq L_{\alpha}$. 
\end{theorem}

Из теоремы~\ref{theorem-lidl}, можно сделать вывод о том, что отображения $L_{\alpha}$ является инъективным  и может быть использования для сравнения чисел. Таким образом задача сравнения чисел в целочисленных гомоморфных шифрах сводиться к задаче сравнения чисел заданных над простым полем. 

Функцию сравнения чисел над простым полем $\mathbb{Z}_m$ определим следующим образом:
\begin{equation}
	\mathrm{comp}_m\left(x,y\right)=
	\begin{cases}
	1&\text{if $x>0$}\\
	0&\text{if $x=y$}\\
	-1&\text{if $x<0$}
	\end{cases}
\end{equation}
\noindent где $m$ -- простое число и $x,y\in\mathbb{Z}_m$. Еесли $m$--составное число, то не существует многочлена от двух переменных над $\mathbb{Z}_m$ определяющего функцию сравнения чисел. В работе \cite{2} используется интерполяционные многочлен Лагранжа от двух переменных построил функцию для сравнения чисел над $\mathbb{Z}_m$. 

Метод \cite{2} позволяет сравнивать целые числа в зашифрованном виде. Вычислительная сложность метода зависит от степени многочлена $c\left(x,y\right)$. Учитывая, что степень многочлена $c\left(x,y\right)$ меньше либо равна $2m-2$.  В работе, мы проведем уточнение оценки для степени интерполяционного многочлена $c\left(x,y\right)$ из \cite{2} и покажем, что $\deg{c\left(x,y\right)}=m$. 

\section{Матрица и их свойство}

Рассмотрим матрицы $D_x$ вида $D_x=x\cdot E$ над $\mathbf{Z}_m$, где $E$ -- единичная матрица порядка $m-1$ и $m$--простое число. Обратим внимание, что матрицы обладают следующими свойствами:

\textbf{Свойство 1.}
	\begin{enumerate}
		\item $D_{x\cdot y}=x\cdot y\cdot E=x\cdot E\cdot y\cdot E=D_x\cdot D_y$.
		\item $D_{x+y}=\left(x+y\right)\cdot E=x\cdot E+y\cdot E=D_x+D_y$.
		\item $\forall x\in\mathbb{Z}_m^\ast: D_x^{-1}=D_{\frac{1}{x}}=\frac{1}{x}\cdot E$.
		\item  $\forall x\in\mathbb{Z}_m^\ast: \det{D_x} =x^{m-1}\equiv1\pmod{m}$
	\end{enumerate}

\begin{lemma}\label{lem-1-comp-over-F_p}
Если $m$ -- простое число, то $\det\bar{D}\in\left\{-1,0,1\right\}$ над $\mathbb{Z}_m$,	где
\begin{equation}
	\bar{D}=\left(
	\begin{matrix}
	D_{d_{1,1}}& D_{d_{1,2}}&\cdots&D_{d_{1,n}}\\
	D_{d_{2,1}}& D_{d_{2,2}}&\cdotp&D_{d_{2,n}}\\\
	\vdots&\vdots&\ddots\vdots\\
	D_{d_{n,1}}&D_{d_{n,2}}&\cdots&D_{d_{n,n}}
	\end{matrix}
	\right)
\end{equation}
\end{lemma}
\begin{proof}
Используя преобразования строк матрицы 1--го типа, сохраняющих значение определителя \cite{3}[стр. 80, Предложение 2] и свойства~1 матрицы $D_x$, приведем матрицу $\bar{D}$  к квазитреугольному виду:
\begin{equation}
	\bar{D}'_{\oplus}=\begin{pmatrix}
	D_{d'_{1,1}}&D_{d'_{1,2}}&\cdots&D_{d'_{1,n}}\\
	D_{d'_{2,1}}&D_{d'_{2,2}}&\cdots&D_{d'_{2,n}}\\
	\vdots&\vdots&\ddots&\vdots\\
	D_{d'_{n,1}}&D_{d'_{n,2}}&\cdot&D_{d'_{n,n}}
	\end{pmatrix}
\end{equation}
\noindent или
\begin{equation}
	\bar{D}'_{\ominus}=-\begin{pmatrix}
	D_{d'_{1,1}}&D_{d'_{1,2}}&\cdots&D_{d'_{1,n}}\\
	D_{d'_{2,1}}&D_{d'_{2,2}}&\cdots&D_{d'_{2,n}}\\
	\vdots&\vdots&\ddots&\vdots\\
	D_{d'_{n,1}}&D_{d'_{n,2}}&\cdot&D_{d'_{n,n}}
	\end{pmatrix}
\end{equation}

Используя теорему 4 \cite{3}[стр. 82] вычислим значения определителя квазитреугольных матриц $\bar{D}'_{\oplus}$ и $\bar{D}_{\ominus}$, получим:
\begin{equation}
	\det{\bar{D}'_{\oplus}}=-\det{\bar{D}'_{\ominus}}=\prod_{i=1}^{n}\det{D_{d'_{i,i}}}
\end{equation}
	
Учитывая, что
\begin{equation}
	\forall i\in\overline{1,n}: \det{D_{d'_{i,i}}}=\begin{cases}
	1&\text{if $d'_{i,i}\mathbf{Z}_m^\ast$},\\
	0&\text{if $d'_{i,i}\equiv0\pmod{m}$},
	\end{cases}
\end{equation}
\noindent следовательно, $\prod_{i=1}^{n}\det{D_{d'_{i,i}}}$ может принимать два значения $\prod_{i=1}^{n}\det{D_{d'_{i,i}}}=1$ если $\forall i\in\overline{1,n}: d'_{i,i}\in\mathbf{Z}_m^\ast$ и $\prod_{i=1}^{n}\det{D_{d'_{i,i}}}=0$ если $\exists i\in\overline{1,n}: d'_{i,i}=0$, значит, $\det\bar{D}\in\left\{-1,0,1\right\}$.
\end{proof}

\begin{lemma}\label{lem-2-comp_over_F_p}
	Если $m$ -- простое число, то $\det{\bar{D}}$ над $\mathbb{Z}_m$ равно нулю тогда и только тогда, когда $\det{\tilde{D}}$ над $\mathbb{Z}_m$, где $\tilde{D}=\left(d_{i,j}\right)_{n\times n}$.
\end{lemma}
\begin{proof}
	Покажем, что если $\det{\tilde{D}}=0$, то $\det{\bar{D}}=0$. Для этого предположим, что  $\det{\tilde{D}}=0$ то строки матрицы $\tilde{D}$ линейно зависимы, следовательно существуют такие числа $\alpha_i$ не все равные нулю одновременно удовлетворяющие условию: $\sum_{i=1}^{n}\alpha_i\cdot\vec{d}_i=0$, значит будет существовать такой номер $j\in\overline{1,n}: \alpha_j\neq0$ и удовлетворяющий $\vec{d}_j=\sum_{i=1, i\neq j}^{n} \alpha'_i\vec{d}_i$, где $\forall i\in\overline{1,n}: \alpha'_i=-\frac{\alpha_i}{\alpha_j}$ и $\forall i\in\overline{1,n}: \vec{d}_i=\left(d_{i,1}, d_{i,2},\cdots, d_{i,n}\right)$. Обозначим через $\vec{D}_i$ вектор элементами которого являются блочные матрицы $D_{d_{i,j}}$:  $\vec{D}_i=\left(D_{d_{i,1}}, D_{d_{i,2}},\cdots,D_{d_{i,n}}\right)$.  
	
	Вычислим значение  $\sum_{i=1, i\neq j}^{n} \alpha'_i\vec{D}_i$ используя свойства~1, получим:
\begin{equation}
	\begin{split}
		\sum_{i=1, i\neq j}^{n} \alpha'_i\vec{D}_i & = \left( \sum_{i=1, i\neq j}^{n}\alpha'_i\cdot D_{d_{i,1}}, \sum_{i=1, i\neq j}^{n}\alpha'_i\cdot D_{d_{i,2}}, \cdots, \sum_{i=1, i\neq j}^{n}\alpha'_i\cdot D_{d_{i,n}}, \right) = \\
		& = \left( \sum_{i=1, i\neq j}^{n} D_{\alpha'_i\cdot d_{i,1}}, \sum_{i=1, i\neq j}^{n}D_{\alpha'_i\cdot d_{i,2}}, \cdots, \sum_{i=1, i\neq j}^{n}D_{\alpha'_i\cdot d_{i,n}}, \right) = \\
		& =	\left( D_{\sum_{i=1, i\neq j}^{n} \alpha'_i\cdot d_{i,1}}, D_{\sum_{i=1, i\neq j}^{n} \alpha'_i\cdot d_{i,2}}, \cdots, D_{\sum_{i=1, i\neq j}^{n}\alpha'_i\cdot d_{i,n}},	\right) = \\
		& = \vec{D}_j
	\label{eq-t-1-comp-over-F-p}
	\end{split}
\end{equation}
	
Из \eqref{eq-t-1-comp-over-F-p}, следует, что линейные строки матриц $\bar{D}$ линейно зависимы следовательно, $\det{\bar{D}}=0$.
	
Покажем, что если $\det{\bar{D}}=0$, то $\det{\tilde{D}}=0$. Предположим: что $\det{\bar{D}}=0$ равен нулю, тогда строки матрицы линейно зависимы и существуют такие числа $\alpha_i$ не все равные нулю одновременно удовлетворяющие условию: $\sum_{i=1}^{n}\alpha_i\vec{D}_i=0$, значит существует такое $j\neq0$ удовлетворяющая условию: $\vec{D}_j=\sum_{i=1, i\neq j}^{n}\alpha'_i\vec{D}_i$.
	
Вычислим значение $\vec{D}_j=\sum_{i=1, i\neq j}^{n}\alpha'_i\vec{D}_i$ используя свойства~1, получим:
\begin{equation}
	\begin{split}
		\vec{D}_j & = \sum_{i=1, i\neq j}^{n}\alpha'_i\vec{D}_i =\\
		& = \left(\sum_{i=1, i\neq j}^{n}\alpha'_i\cdot D_{d_{i,1}}, \sum_{i=1, i\neq j}^{n}\alpha'_i\cdot D_{d_{i,2}}, \cdots, \sum_{i=1, i\neq j}^{n}\alpha'_i\cdot D_{d_{i,n}}, \right) =\\
		& = \left(\sum_{i=1, i\neq j}^{n} D_{\alpha'_i\cdot d_{i,1}}, \sum_{i=1, i\neq j}^{n}D_{\alpha'_i\cdot d_{i,2}}, \cdots, \sum_{i=1, i\neq j}^{n}D_{\alpha'_i\cdot d_{i,n}}, \right) = \\
		& = \left( D_{\sum_{i=1, i\neq j}^{n} \alpha'_i\cdot d_{i,1}}, D_{\sum_{i=1, i\neq j}^{n} \alpha'_i\cdot d_{i,2}}, \cdots, D_{\sum_{i=1, i\neq j}^{n}\alpha'_i\cdot d_{i,n}}, \right)
		\label{eq-t-2-comp-F-p}
	\end{split}
\end{equation}
	
Из \ref{eq-t-2-comp-F-p}, следует, что $\vec{d}_j=\sum_{i=1, i\neq j}^{n} \alpha'_i\vec{d}_i$, значит строки матрицы $\tilde{D}$ линейно зависимы и $\det{\tilde{D}}=0$. Так как равенство выполняется в обе стороны, то лемма доказана.
\end{proof}

\begin{lemma}\label{lem-3-over_F_p}
	Если $m$ -- простое число, то $\det{D_V}\neq0$ над $\mathbb{Z}_m$, где
\begin{equation}
	D_V=\begin{pmatrix}
	D_1&D_{1^2}&\cdots&D_{1^{m-1}}\\
	D_2&D_{2^2}&\cdots&D_{2^{m-1}}\\
	\vdots&\vdots&\ddots&\vdots\\
	D_{m-1}&D_{\left(m-1\right)^2}&\cdots&D_{\left(m-1\right)^{m-1}}
	\end{pmatrix}
\end{equation}
\end{lemma}
\begin{proof}
	Рассмотрим матрицу Вандермонда $V$ равную:
\begin{equation}
	V=\begin{pmatrix}
	1&1^2&\cdots&1^{m-1}\\
	2&2^2&\cdots&2^{m-1}\\
	\vdots&\vdots&\ddots&\vdots\\
	m-1&\left(m-1\right)^2&\cdots&\left(m-1\right)^{m-1}
	\end{pmatrix}
\end{equation}
	
Определитель матрицы $V$ равен
\begin{equation}
	\det{V}=\prod_{i\leq j<i\leq m-1}\left(i-j\right)=\prod_{i=1}^{m-1}i^{m-i}\not\equiv0\pmod{m}
\end{equation}
	
Из Леммы~\ref{lem-2-comp_over_F_p} следует, что $\det{D_V}\neq0$.
\end{proof}

\section{Полиномиальная интерполяция функции сравнения чисел над простым полем}
\begin{theorem}\label{theor-4-over-F-p}
Если $m$--простое число и $m\geq3$, то в поле $\mathbb{Z}_m\left[x\right]$ существует многочлен $c\left(x,y\right)\in\mathbb{Z}_m\left[x,y\right]$ для которого многочлен $b\left(x,y\right)\in\mathbb{Z}_m\left[x,y\right]$ определяется единственным образом, такой что 	$\forall x,y\in\mathbb{Z}_m: \mathrm{comp}_m \left(x,y\right)\equiv c(x,y)\pmod{m}$ и $\deg{c\left(x,y\right)}\leq 2m-2$, где
\begin{equation}
	c\left(x,y\right)=x^{m-1}-y^{m-1} + \sum_{t=1}^{m-1}\sum_{k=1}^{m-1}b_{t,k}\cdot x^t\cdot y^k
\end{equation}
\noindent где 
\begin{eqnarray}
	\forall 1\leqslant t<k\leqslant m-1: \nonumber\\
	b_{t,k}&=&\sum_{1\leq i<j\leq m-1}\left(i^{m-1-k}\cdot j^{m-1-t}-i^{m-1-t}\cdot j^{m-1-k}\right)\nonumber\\
	b_{k,t}&=&-b_{t,k}\nonumber\\
	b\left(x,y\right)&=&\sum_{t=1}^{m-1}\sum_{k=1}^{m-1}b_{t,k}\cdot x^t\cdot y^k.
	\end{eqnarray}
\end{theorem}

\begin{proof}
Пусть существует многочлен $c\left(x,y\right)\in\mathbb{Z}_m\left[x,y\right]$ такой что $\forall x,y\in\mathbb{Z}_m: \mathrm{comp}_m\left(x,y\right)=c\left(x,y\right)$, тогда его можно представить в виде:
\begin{equation}
	c\left(x,y\right)=\alpha+\eta\left(x\right)+\xi\left(y\right)+b\left(x,y\right)
\end{equation}
\noindent где $\alpha\in\mathbb{Z}_m$, $\eta\left(x\right)\in\mathbb{Z}_m\left[x\right]$ и $x|\eta\left(x\right)$,	$\xi\left(y\right)\in\mathbb{Z}_m\left[y\right]$ и $y|\xi\left(y\right)$, $b\left(x,y\right)\in\mathbb{Z}_m\left[x,y\right]$ и $\left(x\cdot y\right)|b\left(x,y\right)$
	
Так как $\mathrm{comp}_m\left(0,0\right)=0$, то $c\left(0,0\right)=\alpha=0$. Учитывая, что $\forall x\in\mathbb{Z}_m^\ast:\mathrm{comp}_m\left(x,0\right)=1$, то $c\left(x,0\right)=\eta(x)\equiv1\pmod{m}$, следовательно, $\forall a\in\mathbb{Z}_m: \left(x-a\right)|\left(\eta\left(x\right)-1\right)$, значит, $\left(x^{m-1}-1\right)|\left(\eta\left(x\right)-1\right)$.  Выбирая в качестве $\eta\left(x\right)$ многочлен наименьшей степени, удовлетворяющий условиям $x|\eta\left(x\right)$ и \newline
$\left(x^{m-1}-1\right)|\left(\eta\left(x\right)-1\right)$, получим $\eta\left(x\right)=x^{m-1}$.
	
Вычислим $\forall a\in\mathbb{Z}_m^\ast: \mathrm{comp}_m\left(0,y\right)=-1$, получим: $\forall a\in\mathbb{Z}_m^\ast: c\left(0,a\right)=\xi\left(y\right)\equiv-1\pmod{m}$, рассуждая аналогично $\eta\left(x\right)$, получим $\xi\left(y\right)=-y^{m-1}$. Таким образом $с\left(x,y\right)$ примет следующий вид: 
\begin{equation}
	c\left(x,y\right) = x^{m-1}-y^{m-1}+b\left(x,y\right) = x^{m-1}-y^{m-1} + \sum_{i=1}^{m-1}\sum_{j=1}^{m-1}b_{i,j}x^i\cdot y^j
\end{equation}
	
Покажем, что $\forall x,y\in\mathbb{Z}_m^\ast$ существует единственный многочлен     $b\left(x,y\right)=\sum_{i=1}^{m-1}\sum_{j=1}^{m-1}b_{i,j}x^{i}\cdot y^{j}$ , удовлетворяющий условию: $b\left(x,y\right)=c\left(x,y\right)$.
\begin{equation}
	H\times
	\begin{pmatrix}
	b_{1,1}\\
	b_{1,2}\\
	\vdots\\
	b_{m-1,m-1}
	\end{pmatrix}
	=\begin{pmatrix}
	\mathrm{comp}_m\left(1,1\right)\\
	\mathrm{comp}_m\left(1,2\right)\\
	\vdots\\
	\mathrm{comp}_m\left(m-1,m-1\right)
	\end{pmatrix}
\end{equation}
\noindent где 
\begin{equation}
	H=
	\begin{pmatrix}
	1^1\cdot1^1&\cdots&1^{m-1}\cdot1^{m-1}\\
	1^1\cdot2^1&\cdots&1^{m-1}\cdot2^{m-1}\\
	\vdots&\ddots&\vdots\\
	\left(m-1\right)^1\cdot\left(m-1\right)^1&
	\cdots &\left(m-1\right)^{m-1}\cdot\left(m-1\right)^{m-1}
	\end{pmatrix}
\end{equation}
	
Матрицу $H$ можно представить в следующем виде:
	
\begin{equation}
	H=D_V\times\begin{pmatrix}
	V&D_0&\cdots&D_0\\
	D_0&V&\cdots&D_0\\
	\vdots&\vdots&\ddots&\vdots\\
	D_0&D_0&\cdots&V
	\end{pmatrix}
\end{equation}
	
Используя теорему~6 из работы \cite{3}[стр.  85] вычислим значение определителя матрицы $H$, получим 
\begin{equation}
 \begin{split}
	\det{H} & = \det{D_V}\cdot\det{
		\begin{pmatrix}
			V&D_0&\cdots&D_0\\
			D_0&V&\cdots&D_0\\
			\vdots&\vdots&\ddots&\vdots\\
			D_0&D_0&\cdots&V
		\end{pmatrix}}\\
	& =\det{D_V}\cdot\left(\det{V}\right)^{m-1}\\
	& \equiv \det{D_V}\pmod{m}
 \end{split}
\end{equation}
	
Из леммы~\ref{lem-3-over_F_p}, следует $\det{H}\not\equiv0\pmod{m}$, значит существует единственное решение матричного уравнения и многочлен $b\left(x,y\right)\in\mathbb{Z}_m^\ast\left[x,y\right]$ определяется единственным образом.
	
Вычислим, многочлен $b\left(x,y\right)$ используя интерполяционный многочлен \newline Лагранжа от двух переменных. Вычислим базисные многочлены.
\begin{equation}
	L_{i,j}\left(x,y\right)=\frac{g_i\left(x\right)}{g_i\left(i\right)}\cdot
	\frac{g_j\left(y\right)}{g_j\left(j\right)}
\end{equation} 
\noindent где  $g_i\left(x\right)=\sum_{t=1}^{m-1}i^{m-1-t}\cdot x^t$. Вычислим значение $g_i\left(i\right)$, получим:
\begin{eqnarray}
	g_i\left(i\right)=\sum_{t=1}^{m-1}i^{m-1-t}\cdot i^t
	=\sum_{t=1}^{m-1}i^{m-1}\equiv m-1\pmod{m}
\end{eqnarray}
	
Следовательно, 
\begin{equation}
 \begin{split}
	L_{i,j}\left(x,y\right) & \equiv  g_i\left(x\right)\cdot g_j\left(y\right) \\
	& \equiv \left(\sum_{t=1}^{m-1}i^{m-1-t}\cdot x^t\right) \left(\sum_{k=1}^{m-1}i^{m-1-k}\cdot y^k\right) \pmod{m}
 \end{split}
\end{equation}
	
Используя \cite{4}[стр. 57, формула 2.34]  
\begin{multline}
	\left(\sum_{k=1}^{m-1}a_k\right)\left(\sum_{t=1}^{m-1}b_t\right) = \\
	= \left(m-1\right)\sum_{k=1}^{m-1}a_k\cdot b_k
	-\sum_{i\leq t<k\leq m-1}\left(a_k-a_t\right)\left(b_k-b_t\right)
\end{multline}
\noindent вычислим значение $L_{i,j}\left(x,y\right)$, учитывая, что $a_k=i^{m-1-k}\cdot x^k$ и $b_k=j^{m-1-k}\cdot y^k$, получим:
\begin{multline}
		L_{i,j}\left(x,y\right) = \left(m-1\right)\sum_{k=1}^{m-1}i^{m-1-k}\cdot x^k\cdot j^{m-1-k}\cdot y^k -\\
		- \sum_{1\leq t<k\leq m-1}\left( i^{m-1-k}\cdot x^k-i^{m-1-t}\cdot x^t \right)\left( j^{m-1-k}\cdot y^k-j^{m-1-t}\cdot y^t \right)
\end{multline}
	
Так как $\forall i,j,x,y\in\mathbb{Z}_m^\ast$:
\begin{eqnarray}
	i^{m-1-k}\cdot x^k\cdot j^{m-1-k}\cdot y^k&=&\left(\frac{x\cdot y}{i\cdot j}\right)^k,\\
	i^{m-1-k}\cdot x^k-i^{m-1-t}\cdot x^t&=&x^t\cdot i^{-k}
	\left(x^{k-t}-i^{k-t}\right)\\
	j^{m-1-k}\cdot y^k-j^{m-1-t}\cdot y^t&=&y^t\cdot j^{-k}\left(y^{k-t}-j^{k-t}\right)
\end{eqnarray}
\noindent то $L_{i,j}\left(x,y\right)$ преобразуется к следующему виду:
\begin{multline}
	L_{i,j}\left(x,y\right) = \left(m-1\right)\sum_{k=1}^{m-1}\left(\frac{x\cdot y}{i\cdot j}\right)^k - \\
	- \sum_{1\leq t<k\leq m-1}\left(x\cdot y\right)^t
	\cdot\left(i\cdot j\right)^{-k}\left(x^{k-t}-i^{k-t}\right)\left(y^{k-t}-j^{k-t}\right)
\end{multline}
	
Вычислим разность $L_{i,j}\left(x,y\right)-L_{j,i}\left(x,y\right)$:
\begin{multline}
	L_{i,j}\left(x,y\right)-L_{j,i}\left(x,y\right) = \\
	= \sum_{1\leq t<k\leq m-1}\left(x\cdot y\right)^t\cdot\left(i\cdot j\right)^{-k} \left(x^{k-t}-j^{k-t}\right)\left(y^{k-t}-i^{k-t}\right) - \\
	- \sum_{1\leq t<k\leq m-1}\left(x\cdot y\right)^t\cdot\left(i\cdot j\right)^{-k} \left(x^{k-t}-i^{k-t}\right) \left(y^{k-t}-j^{k-t}\right) \nonumber
\end{multline}
	
Используя сочетательный закон \cite{4}[стр. 48, формула 2.16] преобразуем \newline	$L_{i,j}\left(x,y\right)-L_{j,i}\left(x,y\right)$ к следующему виду:
\begin{multline}
	L_{i,j}\left(x,y\right)-L_{j,i}\left(x,y\right)= \sum_{1\leq t<k\leq m-1} \left(x\cdot y\right)^t\cdot\left(i\cdot j\right)^{k} \times \\
	\times \left( \left(x^{k-t}-j^{k-t}\right)\left(y^{k-t}-i^{k-t}\right)-\left(x^{k-t}-i^{k-t}\right)\left(y^{k-t}-j^{k-t}\right) \right)\nonumber
\end{multline}
	
Учитывая, что 
\begin{eqnarray}
	\left(x^{k-t}-j^{k-t}\right)\left(y^{k-t}-i^{k-t}\right)&-&
	\left(x^{k-t}-i^{k-t}\right)\left(y^{k-t}-j^{k-t}\right) = \nonumber\\
	&=&\left(x^{k-t}-y^{k-t}\right)\cdot\left(j^{k-t}-i^{k-t}\right)\nonumber
\end{eqnarray}
\noindent то
\begin{eqnarray}
	L_{i,j}\left(x,y\right)-L_{j,i}\left(x,y\right)=
	\sum_{1\leq t<k\leq m-1}
	\left(x\cdot y\right)^t\cdot\left(i\cdot j\right)^{-k}\left(x^{k-t}-y^{k-t}\right)\cdot
	\left(j^{k-t}-i^{k-t}\right)\nonumber
\end{eqnarray}
	
Таким образом используя интерполяционную функцию Лагранжа, вычислим многочлен $b\left(x,y\right)$:
\begin{eqnarray}
	b\left(x,y\right)&=&-
	\sum_{1\leq i<j\leq m-1}\left(L_{i,j}\left(x,y\right)-L_{j,i}\left(x,y\right)\right)\nonumber\\
	&=&
	-\sum_{1\leq i<j\leq m-1}
	\sum_{1\leq t<k\leq m-1}
	\left(x\cdot y\right)^t\cdot\left(i\cdot j\right)^{-k}
	\left(x^{k-t}-y^{k-t}\right)\cdot\left(j^{k-t}-i^{k-t}\right)\nonumber
\end{eqnarray}
	
Используя правило изменения порядка суммирования и обобщающий сочетательный закон \cite{4}[стр.  53, формула 2.27], получим:
\begin{eqnarray}
	b\left(x,y\right) =-\sum_{1\leq t<k\leq m-1} \left(x\cdot y\right)^t\cdot\left(	x^{k-t}-y^{k-t}	\right)	\sum_{1\leq i<j\leq m-1}	\left(i\cdot j\right)^{-k}	\cdot\left(	j^{k-t}-i^{k-t}	\right)\nonumber
\end{eqnarray}
	
Таким образом, мы можем сделать вывод о том, что, если $1\leq t<k\leq m-1: b_{t,k}=\sum_{1\leq i<j\leq m-1}\left(i\cdot j\right)^{-k}\cdot\left(j^{k-t}-i^{k-t}\right)$ и $b_{k,t}=-b_{t,k}$.
	
Вычислим $\forall 1\leq t<k\leq m-1$ значение $b_{t,k}$, получим:
\begin{eqnarray}
	b_{t,k}&=&\sum_{1\leq i<j\leq m-1}
	\left(i\cdot j\right)^{-k}\cdot\left(j^{k-t}-i^{k-t}\right)\nonumber\\
	&=&\sum_{1\leq i<j\leq m-1}\left(i^{m-1-k}\cdot j^{m-1-t}-i^{m-1-t}\cdot j^{m-1-k}\right) 	
\end{eqnarray}
\end{proof}

\section{Свойства}

В предыдущем разделе мы определили формулу для интерполяции функции сравнения чисел с помощью интерполяционной формулы Лагранжа.  В этом разделе мы рассмотрим свойства коэффициентов многочлена $b\left(x,y\right)$.

\textbf{Свойство 2.}
	\begin{enumerate}
		\item 	Если $t+k$ -- четное число, то $b_{t,k}=0$.
		\item  	Если $t$--четное и $k$--нечетное, то
		\begin{equation}
		b_{t,k}=2\cdot\sum_{i=1}^{m-2}i^{m-1-k}
		\cdot\sum_{j=1}^{m-i-}j^{m-1-t}
		\end{equation} 
		\item 	Если $t$--нечетное и $k$--четное, то
		\begin{equation}
		b_{t,k}=-2\cdot\sum_{i=1}^{m-2}i^{m-1-k}\cdot\sum_{j=1}^{m-i-1}j^{m-1-t}
		\end{equation} 
	\end{enumerate}

\begin{proof}
	Используя теореме~\ref{theor-4-over-F-p}  вычислим значения коэффициента $b_{t,k}$
\begin{eqnarray}
	b_{t,k}&=&\sum_{1\leq i<j\leq m-1}\left(i^{m-1-k}\cdot j^{m-1-t}-i^{m-1-t}\cdot j^{m-1-k}\right)\\
	&=&\sum_{i=1}^{m-2}\sum_{j=i+1}^{m-1}\left(i^{m-1-k}\cdot
	j^{m-1-t}-i^{m-1-t}\cdot j^{m-1-k}\right) 
\end{eqnarray}
	
Используя сочетательный закон \cite{4}[стр. 48, формула 2.16], получим:
\begin{equation}
	b_{t,k}=\sum_{i=1}^{m-2}\sum_{j=i+1}^{m-1}i^{m-1-k}\cdot j^{m-1-t} -\sum_{i=1}^{m-2}\sum_{j=i+1}^{m-1}i^{m-1-t}\cdot j^{m-1-k}
\end{equation}
	
Заменим $j$ на $m-j$,
\begin{equation}
	b_{t,k}=\sum_{i=1}^{m-2}\sum_{j=1}^{m-i-1}i^{m-1-k}\cdot\left(m-j\right)^{m-1-t}
	-\sum_{i=1}^{m-2}\sum_{j=1}^{m-i-1}i^{m-1-t}\cdot\left(m-j\right)^{m-1-k}
\end{equation}
	
Так как 
$$\left(m-j\right)^{m-1-t}\equiv\left(-1\right)^{m-1-t}j^{m-1-t}\pmod{m}$$
и
$$\left(m-j\right)^{m-1-k}\equiv\left(-1\right)^{m-1-k}j^{m-1-k}\pmod{m},$$
то
$$
	b_{t,k}=\left(-1\right)^{m-1-t} \sum_{i=1}^{m-2}\sum_{j=1}^{m-i-1}i^{m-1-k}\cdot j^{m-1-t} 
	-\left(-1\right)^{m-1-k}\sum_{i=1}^{m-2}\sum_{j=1}^{m-i-1}i^{m-1-t}\cdot j^{m-1-k}\nonumber
$$

Используя распределительный закон  \cite{4}[стр. 48, формула 2.16] преобразуем сумм к следующему виду:
\begin{multline}
	b_{t,k} = \left( -1 \right)^{m - 1 - t} \sum_{i = 1}^{m - 2} i^{m - 1 - k} \times \\
	\times \sum_{j = 1}^{m - i - 1} j^{m - 1 - t} - \left( -1 \right)^{m - 1 - k} \sum_{i = 1}^{m - 2} i^{m - 1 - t} \times \sum_{j = 1}^{m - i - 1} j^{m - 1 - k}
\end{multline}
	
Учитывая, что: 
\begin{equation}
	\sum_{i=1}^{m-2}i^{m-1-t}\sum_{j=1}^{m-i-1}j^{m-1-k}
	=\sum_{i=1}^{m-2}i^{m-1-k}\cdot\sum_{j=1}^{m-i-1}j^{m-1-t}
\end{equation}
то
\begin{equation}
	b_{t,k}=
	\left(\left(-1\right)^{m-1-t}-\left(-1\right)^{m-1-k}\right) \cdot\sum_{i=1}^{m-2}i^{m-1-k}\cdot\sum_{j=1}^{m-i-1}j^{m-1-t}
\end{equation}
	
Рассмотрим четыре случая:

\textit{Случай 1}. Если $t$--четное и $k$--четное, то $m-1-t$ -- четное и $(m-1-k)$ -- четное,
	следовательно:
\begin{equation}
	b_{t,k}=0
\end{equation}
	
\textit{Случай 2}. Если $t$--четное и $k$--нечетное, то $(m-1-t)$ -- четное и $(m-1-k)$ -- нечетное, следовательно:
\begin{equation}
	b_{t,k}=2\cdot\sum_{i=1}^{m-2}i^{m-1-k}\sum_{j=1}^{m-i-1}j^{m-1-t}
\end{equation}
	
\textit{Случай 3}. Если $t$--нечетное и $k$--нечетное, то $(m-1-t)$ -- нечетное и $(m-1-k)$ -- нечетное, следовательно:
\begin{equation}
	b_{t,k}=0
\end{equation}
	
\textit{Случай 4.} Если $t$--нечетное и $k$--четное, то $(m-1-t)$ -- нечетное и $(m-1-k)$ -- четное, следовательно:
\begin{equation}
	b_{t,k}=-2\cdot\sum_{i=1}^{m-2}i^{m-1-k}\cdot\sum_{j=1}^{m-i-1}j^{m-1-t}
\end{equation}
	
Из Случая 1 и 3 можно сделать вывод о том, что если $t+k$ -- четное число, то $b_{t,k}=0$.
\end{proof}

\textbf{Свойство 3.}
\begin{equation}
	b_{m-1,2\cdot k+1}=
	\begin{cases}
	2&\text{если $k=0$},\\
	0&\text{ иначе }
	\end{cases}
\end{equation}

\begin{proof}
Так как по условию теоремы~\ref{theor-4-over-F-p} $m$ -- простое число и $m\geq3$, то $m$ -- нечетное число, следовательно, $m-1$ -- четное число. Число вида $2\cdot k+1$ всегда нечётное число, значит значение $b_{m-1,2\cdot k+1}$ вычисляется свойству~2 случай 2:
\begin{equation}
	b_{m-1,2\cdot k+1}=2\cdot\sum_{i=1}^{m-2}i^{m-2-2\cdot k}\cdot\sum_{j=1}^{m-i-1}j^0
\end{equation}
	
Учитывая, что $\sum_{j=1}^{m-i-1}j^0 =\sum_{j=1}^{m-i-1}1=m-i-1$, то
\begin{equation}
 \begin{split}
	b_{m-1,2\cdot k+1} & = 2\cdot\sum_{i=1}^{m-2}i^{m-2-2\cdot k}\cdot\left(m-i-1\right) \equiv \\ 
	& \equiv-2\sum_{i=1}^{m-2}i^{m-1-2\cdot k} -2\cdot\sum_{i=1}^{m-2}i^{m-2-2\cdot k}
	\pmod{m}
 \end{split}
\end{equation}
	
Представим
\begin{equation}
 \begin{split}
	\sum_{i=1}^{m-2}i^{m-1-2\cdot k} & = -\left(m-1\right)^{m-1-2\cdot k}+\sum_{i=1}^{m-1}i^{m-1-2\cdot k} \equiv \\
	&\equiv -\left(-1\right)^{m-1-2\cdot k}+\sum_{i=1}^{m-1}i^{m-1-2\cdot k} \pmod{m}\\
 \end{split}
\end{equation}

\begin{equation}
 \begin{split}
	\sum_{i=1}^{m-2}i^{m-2-2\cdot k} & = -\left(m-1\right)^{m-2-2\cdot k}+\sum_{i=1}^{m-1}i^{m-2-2\cdot k} \equiv \\
	&\equiv -\left(-1\right)^{m-2-2\cdot k}+\sum_{i=1}^{m-1}i^{m-2-2\cdot k}\pmod{m}
 \end{split}
\end{equation}

\noindent получим
\begin{equation}
 \begin{split}
	b_{m-1,2\cdot k+1} & = 2\left(\left(-1\right)^{m-1-2\cdot k}+\left(-1\right)^{m-2-2\cdot k}\right) - \\ 
	& - 2\sum_{i=1}^{m-1}i^{m-1-2\cdot k} -2\cdot\sum_{i=1}^{m-1}i^{m-2-2\cdot k} = \\
	& = -2\sum_{i=1}^{m-1}i^{m-1-2\cdot k} -2\cdot\sum_{i=1}^{m-1}i^{m-2-2\cdot k}
 \end{split}
\end{equation}
	
Так как 
$\forall k=\overline{0,\frac{m-1}{2}}:\gcd{m-2\cdot k-1,m}=1$ и $\forall k=\overline{1,\frac{m-1}{2}}:\gcd{m-2\cdot k,m}=1$, то используя формулу Бернулли из работы \cite{4}[стр. 314, формула 6.78] вычислим значение $\left|\sum_{i=1}^{m-1}i^{m-1-2\cdot k}\right|_m$, получим:
\begin{equation}
\begin{split}
	\left|\sum_{i=1}^{m-1}i^{m-1-2\cdot k}\right|_m & = \left|\frac{1}{m-2\cdot k}\sum_{s=0}^{m-1-2k} \binom{m-2\cdot k}{s}B_s\cdot m^{m-2\cdot k-s} \right|_m = \\
	& = \begin{cases}
	\left|\binom{m}{m-1}B_{m-1}\right|_m& \text{$k=0$}\\
	0& \text{ иначе }
	\end{cases}
 \end{split}
\end{equation}
\noindent где $B_s$ -- числа Бернулли.
Вычислим, значение $\left|\sum_{i=1}^{m-1}i^{m-1-2\cdot k}\right|_m$ в случае если $k=0$, получим:
\begin{equation}
	\left|\sum_{i=1}^{m-1}i^{m-1}\right|_m\equiv\left|\sum_{i=1}^{m-1}1\right|_m
	\equiv-1\pmod{m}
\end{equation}
	
\noindent следовательно:
\begin{equation}
	b_{m-1,2\cdot k+1}=\begin{cases}
	2&\text{если $k=0$}\\
	0& \text{ иначе }
	\end{cases}
\end{equation}
\end{proof}

\textbf{Свойство 4.}
	Если $t+k>m$, то $b_{t,k}=0$

\begin{proof}	
Воспользуемся формулой Бернулли	\cite{4}[стр. 314, формула 6.78] и вычислим значение выражения:
\begin{equation}
	\sum_{i=1}^{m-2}i^{m-1-k}\cdot\sum_{j=1}^{m-i-1}j^{m-1-t}
\end{equation}
	
\noindent получим
\begin{equation}
	\sum_{j=1}^{m-i-1}j^{m-1-t} =\frac{1}{m-t}\sum_{s=0}^{m-1-t}
	\binom{m-t}{s}B_s\left(m-i\right)^{m-t-s}
\end{equation}
	
Так как $\forall t\in\mathbf{Z}_m^\ast$  и $t\neq m-1:\gcd{m-t,m}=1$, то
\begin{multline}
	\frac{1}{m-t}\sum_{s=0}^{m-1-t}\binom{m-t}{s}B_s\left(m-i\right)^{m-t-s} \equiv \\
	\equiv -\frac{1}{t}\sum_{s=0}^{m-1-t}\binom{m-t}{s}B_s
	\left(-i\right)^{m-t-s}\pmod{m}
\end{multline}
	
Следовательно
\begin{multline}
	\sum_{i=1}^{m-2}i^{m-1-k}\cdot\sum_{j=1}^{m-i-1}j^{m-1-t} \equiv\\
	\equiv \sum_{i=1}^{m-2}i^{m-1-k}\cdot\left(-\frac{1}{t}\sum_{s=0}^{m-1-t}
	\binom{m-t}{s}B_s\left(-i\right)^{m-t-s}\right)
\end{multline}
	
Используя распределительный закон \cite{4}[стр. 48, формула 2.15], получим:
	
\begin{multline}
	\sum_{i=1}^{m-2}i^{m-1-k}\cdot\sum_{j=1}^{m-i-1}j^{m-1-t} = \\
	= \frac{\left(-1\right)^{m-1-t}}{t} \sum_{i=1}^{m-2}i^{m-1-k}\cdot \sum_{s=0}^{m-1-t}\left(-1\right)^s\binom{m-t}{s}B_s i^{m-t-s} = \\
	= \frac{\left(-1\right)^{m-1-t}}{t} \sum_{i=1}^{m-2}i^{m-1-k}\cdot\sum_{s=0}^{m-1-t} \left(-1\right)^s\binom{m-t}{s}B_s\cdot t^{m-t-s} = \\
	= \frac{\left(-1\right)^{m-1-t}}{t} \sum_{s=0}^{m-1-t}\left(-1\right)^s 	\binom{m-t}{s}B_s\sum_{i=1}^{m-2}i^{2m-t-k-s-1}.
\end{multline}
	
Представим $\sum_{i=1}^{m-2}i^{2m-t-k-s-1}$  в следующем виде, получим:
\begin{equation}
	\sum_{i=1}^{m-2}i^{2m-t-k-s-1}=
	-\left(m-1\right)^{2m-t-k-s-1} 
	\sum_{i=1}^{m-1}i^{2m-t-k-s-1} 
\end{equation}
	
Так как по условию $t+k>m$, то $1\leq 2m-t-k-s<m$, следовательно $\gcd{2m-t-k-s,m}=1$ и
\begin{multline}
	\left|\sum_{i=1}^{m-2}i^{2m-t-k-s-1}\right|_m \equiv - \left(-1\right)^{2m-t-k-s-1} + \\
	+ \frac{1}{2m-t-k-s} \sum_{j=0}^{2m-t-k-s-1} \binom{2m-t-k-s}{j}B_jm^{2m-t-k-s-j} \equiv \\
	\equiv \left(-1\right)^{2m-t-k-s}\pmod{m}
\end{multline}
	
\noindent Следовательно, 
\begin{multline}
	\sum_{i=1}^{m-2}i^{m-1-k}\cdot\sum_{j=1}^{m-i-1}j^{m-1-t} \equiv \\
	\equiv \frac{\left(-1\right)^{m-1-t}}{t} \sum_{s=0}^{m-1-t}\left(-1\right)^s\binom{m-t}{s}B_s\left(-1\right)^{2m-t-k-s} \equiv \\
	\equiv \frac{\left(-1\right)^{m-1-t}\left(-1\right)^{2m-t-k}}{t} \sum_{s=0}^{m-1-t}\binom{m-t}{s}B_s
\end{multline}
	
Учитывая, что $\forall t\in\mathbb{Z}_m^\ast$  и $t\neq m-1: m-1-t>0$, 	то используя \cite{4}[стр. 314, формула 2.79] 
\begin{equation}
	\sum_{s=0}^{m-1-t}\binom{m-t}{s}B_s=0
\end{equation} 
	
Таким образом согласно свойству~2, если $t+k$ -- четное число, то $b_{t,k}=0$. Если $t$--четное, $k$--нечетное, $t+k>m$ и $t\neq m-1$, то
\begin{equation}
	b_{t,k}=2\cdot\sum_{i=1}^{m-2}i^{m-1-k}\cdot\sum_{j=1}^{m-i-1}j^{m-1-t}=2\cdot0=0
\end{equation} 
	
Если $t$--нечетное, $k$--четное, $t+k>m$ и $t\neq m-1$, то
\begin{equation}
	b_{t,k}=-2\cdot\sum_{i=1}^{m-2}i^{m-1-k}\cdot
	\sum_{j=1}^{m-i-1}j^{m-1-t}=-2\cdot0=0
\end{equation}
	
Из свойства~3 следует, что если $t=m-1$, $t+k$ -- нечетное число и $t+k>m$, то $b_{t,k}=0$	Следовательно, если $t+k>m$, то $b_{t,k}=0$.
\end{proof}

Из свойства~4 следует, что степень многочлена $c\left(x,y\right)\leq m$, с другой стороны, согласно свойству~3 $b_{m-1,1}=2$, следовательно коэффициент при $x^{m-1}y$ не равен нулю, значит $\deg{c\left(x,y\right)}=m$.Таким образом мы уточнили оценку степени многочлена из работы \cite{2} с $2m-2$ до $m$.

\textbf{Пример.} Вычислить многочлен $с\left(x,y\right)$ над $\mathbb{Z}_5$.

Используя свойство~3, вычислим, значения коэффициентов $b_{t,k}$, получим:
\begin{gather}
	b_{2,1} = \left|2\cdot\sum_{i=1}^3i^3\cdot\sum_{j=1}^{4-i}j^2\right|_m =\left|2\cdot\left(1+4+9+8\cdot1+8\cdot4+27\cdot1\right)\right|_5=2 \\
	b_{3,2} = \left|-2\cdot\sum_{i=1}^3i^2\cdot\sum_{j=1}^{4-i}j^2\right|_m
	 = \left|-2\cdot\left(1+2+3+4\cdot1+4\cdot2+9\cdot1\right)\right|_m=1
\end{gather}
	
Согласно лемме~\ref{lem-1-comp-over-F_p}, $b_{4,1}=2$. 	Используя теорему~\ref{theor-4-over-F-p}, вычислим значения коэффициентов  $b_{1,2}$, $b_{2,3}$ и $b_{1,4}$, получим:
\begin{eqnarray}
	b_{1,2}&=&-b_{2,1}=3\pmod{5}\\
	b_{2,3}&=&-b_{3,2}=4\pmod{5}\\
	b_{1,4}&=&-b_{4,1}=3\pmod{5}
\end{eqnarray}
	
Таким образом многочлен $с\left(x,y\right)$ над $\mathbb{Z}_5$ имеет, следующий вид:
\begin{equation}
	c\left(x,y\right)=x^4-y^4+3\cdot x\cdot y^2+3\cdot x\cdot y^4+4\cdot x^2\cdot y^3+x^3\cdot y^2+2\cdot x^4\cdot y+2\cdot x^2\cdot y
\end{equation}
	
Рассмотрим результат вычисления многочлена $c\left(x,y\right)$ над $\mathbb{Z}_5$. Результаты вычисления приведем в таблице~\ref{tab-1-over-F-p}:
	
\begin{table}[h]
	\caption{Вычисление многочлена $c\left(x,y\right)$ над $\mathbb{Z}_5$}
	\label{tab-1-over-F-p}
	\centering
	\begin{tabular}{|c|c|c|c|c|c|c|}
		\hline
		\multicolumn{2}{|c|}{} &\multicolumn{5}{|c|}{$y$}\\
		\cline{3-7}
		\multicolumn{2}{|c|}{$c\left(x,y\right)$}&0&1&2&3&4\\
		\hline
		&0&0&-1&-1&-1&-1\\
		\cline{2-7}
		&1&1&0&-1&-1&-1\\
		\cline{2-7}
		$x$&2&1&1&0&-1&-1\\
		\cline{2-7}
		&3&1&1&1&0&-1\\
		\cline{2-7}
		&4&1&1&1&1&0\\
		\hline
		\end{tabular}
	\end{table}

\section{Заключение}

Вычислительная сложность алгоритма сравнения зашифрованных чисел c использованием целочисленных гомоморфных шифров зависит от количества арифметических операций сложения, умножения которые необходимо произвести, для вычисления интерполяционного многочлена. При реализации схемы гомоморфного сравнения чисел является мультипликативная глубина алгоритма сравнения чисел, так как целочисленные гомоморфные шифры поддерживают ограниченное число умножений. Как показано в работе \cite{5} мультипликативная глубина вычисления многочлена с помошью алгоритма Paterson--Stockmeyer зависит от степени многочлена.  Мы уточнили оценку степени интерполяционного многочлена функции сравнения зашифрованных чисел   из работы \cite{2} с $2m-2$ до $m$.

\bigskip
\begin{thebibliography}{1} % Ссылки на литературу приводятся только на английском языке (даже если у источника нет англоязычной версии).

\bibitem{1} R. Lidl, H. Niederreiter,
 {\it Finite fields}, M.: Mir, 1988.

\bibitem{2} B.H.M. Tan, H.T. Lee, H. Wang, S.Q. Ren, A.M.M. Khin, 
{\it  Efficient private comparison queries over encrypted databases using fully homomorphic encryption with finite fields}, IEEE Transactions on Dependable and Secure Computing, 2020.

\bibitem{3} E. Vinberg,
 {\it Algebra course}, Litres, 2017.

\bibitem{4} R.L. Graham, D.E. Knuth, O. Patashnik,
 {\it Concrete mathematics: a foundation for computer science}, Addison-Wesley, Reading, MA, 1989.

\bibitem{5} R. Player,
 {\it Parameter selection in lattice-based cryptography},  Doctoral dissertation, Royal Holloway, University of London, 2018.

\end{thebibliography}
\end{document}
