\documentclass[reqno]{amsart}
\usepackage{hyperref}
\usepackage{algorithm}

\AtBeginDocument{{\noindent\small
\emph{Electronic Journal of Differential Equations},
Vol. 2015 (2015), No. 303, pp. 1--7.\newline
ISSN: 1072-6691. URL: http://ejde.math.txstate.edu or http://ejde.math.unt.edu
\newline ftp ejde.math.txstate.edu}
\thanks{\copyright 2015 Texas State University.}
\vspace{9mm}}

\begin{document}
\title[\hfilneg EJDE-2015/303\hfil Elliptic curves on PDEs]
{Differential operators over particular elliptic curves spaces with cryptographic
applications}

\author[O. Adriana \c{T}icleanu \hfil EJDE-2015/303\hfilneg]
{Oana Adriana \c{T}icleanu}

\address{Oana Adriana \c{T}icleanu \newline
University of Craiova, Street: A.I. Cuza 13, 200585 Craiova, Romania}
\email{oana.ticleanu@inf.ucv.ro}

\thanks{Submitted September 12, 2015. Published December 11, 2015.}
\subjclass[2010]{35H20, 35S15, 12H20, 11G07}
\keywords{Elliptic curves; cryptography; differential equation}

\begin{abstract}
 Finding optimal implementations to solve differential equations
 in the case of boundary conditions is an open problem.
 In the particular case of using nonsupersingular elliptic curves there
 are applications in the asymmetric encryption field.
 Starting from the general implementations, we constructed solutions
 for the nonsupersingular elliptic curves case. Our developments
 are of high interest in the domain of nonlinear cryptography and have
 a good resistance for differential cryptanalysis.
\end{abstract}

\maketitle
\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\allowdisplaybreaks

\section{Introduction}

The study of elliptical curves has a rich history and proves once again 
the beauty of pure, theoretical mathematics and the way its applicability 
emerges in time.

Some properties of systems based on elliptical spaces date from the previous century.
Foundations in this sense were dated long before, by the study of diophantine 
equations (3th century, Hellenic mathematician A. Diophantus).
This domain was highlighted with articles of mathematicians
 Koblitz (\cite{nk87}) and  Miller (\cite{vm86}) which gave a brand new 
applicability of those equations in the domain of asymmetric cryptosystems.

\section{Elliptic equations analysis}

We start by defining a set of elliptic curves given by Weierstrass's equation
\begin{equation}\label{eqW1_1}
  E:y^2=a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6
 \end{equation}
where $a_i\in K$ and $K$ is the space where curve $E$ is defined.

Those curves can be divided in two classes namely: 
supersingular and nonsupersingular (\cite{amv93}).
Modern applicability of this concepts can be found in \cite{jkcctOT}.
\begin{enumerate}
 \item A supersingular curve (zero $j$-invariant)
 is the solution set of equation:
 \begin{equation}\label{eq:super_1}
  y^2=x^3+ax+b
 \end{equation}
 where $a,b\in GF(2^k)$, and the discriminant is $\Delta=4a^3+27b^2\neq 0$, 
together with the point $\mathcal{O}$ at infinite.

 \item A nonsupersingular elliptical curve (nonzero $j$-invariant) is 
the solution set of equation
 \begin{equation}\label{eq:nons_1}
  y^2+xy=x^3+ax^2+b
 \end{equation}
 where $a,b\in GF(2^k)$, and the discriminant is $\Delta \neq 0$, 
together with the point $\mathcal{O}$ at infinite.
\end{enumerate}

The pairs of points which are found on this kind of curves that have 
a particular set of properties, together with a scalar, are the asymmetric 
keys used in modern cryptography. Given this fact many mathematicians have 
studied ways to obtain spaces with properties in this sense 
\cite{amv93,ser79,st01} and model optimizations, by adding new boundary 
conditions for nonlinear equations systems (\cite{acr14}).

Essentially, beyond optimal implementations, algorithmic complexity and 
computing power, it is a proven fact that the only models which are resistant 
to cryptographic attacks were those that had a mathematical outfit based 
on the construction of subspaces with particularities. Those subspaces 
have a solution set characterized by a diferential equation system which 
is defined over elliptic curves through the Frobenius isomorphisms 
\cite{analeOT,smart99}.

There are existing methods available to compute the involved parameters 
and isomorphisms that define parts of the models. In the domain described 
above we studied, build, developed and implemented proprietary solutions 
for unsolved problems from the field of applied mathematics in cryptography,
 which rely on nonsupersingular elliptic curves.

\section{Nonlinearities on elliptic curves. 
Study implementation for nonsupersingular case}

After classifying the construction methods of the fields over which 
are defined classical elliptical curves, we will describe optimized 
personal solutions to compute the parameter $p$ of an elliptical 
curve (algorithm \ref{subrutinamy}).

Let $\Gamma$ be a subset of points over an elliptical curve for which the 
inverse was computed, $\chi$ the inverse of a number $\phi$, $t$ 
the differentiation level (which defines the safety degree of the generated system).

\begin{algorithm}[htp]
  \caption{Differential calculation of the parameter $p$ of an elliptic curve}
\label{subrutinamy}
\begin{enumerate}
   \item $\phi_0\leftarrow\lfloor \chi/b^t\rfloor$, 
$\phi_0\leftarrow \phi-\theta_{0} b^t$, $\phi\leftarrow \phi_0$,
$i\leftarrow 0$, $\xi \leftarrow \phi_0$
   \item while $\xi>0$ do
   \item \quad $\theta_{i+1}\leftarrow\lfloor \theta_i/\xi^t\rfloor$,
$\phi_{i+1}\leftarrow \theta_i a-\theta_{i+1}\frac{b^t}{\xi}$
   \item \quad $i\leftarrow i+1$, $\phi\leftarrow \phi+\phi_i$, 
$\xi \leftarrow \lfloor\frac{b^t}{\phi_i}\rfloor$
   \item while $\phi\geq p$ do $\phi\leftarrow \phi-\lfloor\frac{p}{\chi}\rfloor$
  \end{enumerate}
\end{algorithm}

\section{Boundary solutions on particular subspaces on nonsupersingular
 elliptic curves}

To have an increased resistance to differential attacks in cryptography 
it is necessary to perform an optimal number of operations over elliptic curves, 
which were achieved in the implementation \ref{subrutinamy}.

For the developed models we studied endomorphisms over finite fields and 
the implications given by the differential equations involved in the 
nonlinear analysis of the cryptographic system \cite{DBLPOT}.


\subsection{Transformation of nonsupersingular elliptic curve $\mathbb{Z}_q^p$
 for invariant $j$} 

From equations described by \cite{lst64} can be concluded that Jacobian 
matrix is invertible over field $\mathbb{Z}_q$ and 
$\delta=((D\Theta)^{-1}\Theta)(x_0,x_1,\ldots, x_{n-1})\in\mathbb{Z}^{n}_{q}$, 
because
$$
(D\Theta)(x_0,\ldots, x_{n-1})\pmod{p}
$$
is the matrix's diagonal with nonzero elements. 
It is obvious that the Gauss method can be applied in order to solve the equation
$$
(D\Theta)(x_0,\ldots,x_{n-1})\delta=\Theta(x_0,\ldots,x_{n-1})
$$
because diagonal elements are reversible.
It will be computed on each line, by moving the low-left item, 
$\Phi'_p(x_0,x_{n-1})$, to right. After performing $k$ operations 
of this kind, the item can be written as:
$$
(-1)^k\Phi'_p(x_0,x_{n-1}) \prod_{i=0}^{k-1}
\frac{\Phi'_p(x_{i+1},x_i)}{\Phi'_p(x_i,x_{i+1})}\,,
$$
and it can be proven that it is divisible with $p^k$ from 
$\Phi'_p(x_{i+1},x_i)\equiv 0\pmod{p}$.  The transformation of 
the nonsupersingular elliptic curve is described in algorithm \ref{algTrjOT}.

\begin{algorithm}[htp]
  \caption{Transformation of nonsupersingular elliptic curve $\mathbb{Z}_q^p$}
 \label{algTrjOT}

\begin{itemize}
 \item[Input:]  System $j^P_i\in\mathbb{F}^{P}_{q}\backslash \mathbb{F}_{p^2}$
 with $\Phi_p(j^P_i,j^P_{i+1})\equiv 0\pmod{p}$ for $0\leq i\leq n'$ 
with precision $[m/n]$.
 \item[Output:] System $j^q_i\in\mathbb{Z}_q$ with 
$\Phi_p(J^P_i,J^P_{i+1})\equiv 0\pmod{p^m}$ and $J^q_i\equiv j_i\pmod{p}$
for any $0\leq i<n'$.
\end{itemize}

\begin{enumerate}
 \item for $m=1$ to $n'$ do
 \item   \quad if $j^m_i\neq 0$ then
 \item     \qquad $J_i\leftarrow j^m_i$
 \item   \quad else
 \item     \qquad $m'\leftarrow\lceil \frac{m}{2}\rceil\cdot\lceil 
 \frac{p}{2}\rceil,M\leftarrow m'$, $M'\leftarrow\frac{P}{q}$.
 \item     \qquad $(J^P_0,\ldots,J^P_{n'-1})$ will be determined by the 
canonical inverse of $((j^P_0,\ldots,j^P_{n'-1}),m')$.
 \item     \qquad for $i=0$ to $n'-2$ do
 \item       \quad\qquad $t\leftarrow \Phi'_p(J^P_i,J^P_{i+1})^{-1}\pmod{p^M}$; 
$D_i\leftarrow t\Phi'_p(J^P_{i+1},J^P_i)\pmod{p^M}$.
 \item       \quad\qquad $P_i\leftarrow t((\Phi_p(J^P_i,J^P_{i+1})
 \pmod{p^m})/p^{M}\cdot\frac{1}{p^{M'}})\pmod{p^M}$
 \item     \qquad $R\leftarrow\Phi'_p(J^P_0,J^P_{n-1})\pmod{p^{M'}}$.
 \item     \qquad $S\leftarrow(((\Phi_p(J^P_{n-1},J^P_0)\pmod{p^{M'}}))/p^{M'})
 \pmod{p^M}$.
 \item     \qquad if $S\neq 0$ then
 \item       \quad\qquad for $i=n'-2$ to $0$ by step $-1$ do
 \item         \qquad\qquad $\varphi_i\leftarrow\varphi_i-D_i
\ P^P_{i+1}\pmod{p^{M'}}$
 \item     \qquad else
 \item       \quad\qquad for $i=0$ to $m'-1$ do $J^P_i\rightarrow 
J^P_i-p^{M'}P^P_i\pmod{p^{M'}}$
 \item return ($J^P_0,\ldots,J^P_{n'-1}$).
\end{enumerate}
\end{algorithm}

\section{Nonlinear method for computing the number of points with 
cryptographic proprieties - SatOT } 

Starting from the proof of Satoh's model, we developed a computing method 
for elliptic curves subspaces with parameter $p$ and a number of points 
characterized by 
$\overline{F_{OT}}:\overline{E}(\overline{\mathbb{F}}_q)
\rightarrow\overline{E}(\overline{\mathbb{F}}_q):(x,y)\longmapsto(x_p^q,y_p^q)$.
 We define cryptographic points of degree 1 as the set of potential keys 
for ECC systems. The method ensures that a subspace has a lower computational 
complexity to generate such points, furthermore, it keeps the attack 
complexity on ECDLP at the same level with the general case 
(implementation \ref{SatOT}).

\begin{algorithm}[htp]
  \caption{Nonlinear method to compute the number of points with 
cryptographic properties - SatOT}
 \label{SatOT}

 \begin{itemize}
  \item[Input:]  Nonsupersingular elliptic curve $\overline{E}_p$, derived 
from $\overline{E}:y^2=x^3+ax+b$ defined over subspace $\mathbb{F}^q_{p^n}$, 
$j(\overline{E}_{OT})\notin\mathbb{F}_{p^2}$.
  \item[Output:] Cryptographic points of degree 1 from a nonsupersingular 
elliptic curve $\overline{E}(\mathbb{F}^q_{p^n})$.
 \end{itemize}

 \begin{enumerate}
  \item For each point from $\overline{E}$, compute subset $\overline{E}_p$,  as an isomorphism, using algorithm \ref{algTrjOT}.
  \item if $m$ has value $1$ then
  \item   \quad For $i=0$ to $n-1$ do
  \item     \qquad $J_i\leftarrow j^q_i$
  \item else
  \item   \quad $m'\leftarrow\lceil \frac{m}{2}\rceil\ \lceil \frac{p}{2}\rceil$,\\
           $M'\leftarrow(m-m')\pmod{q}$.
  \item $(J^q_0,\ldots,J^q_{n-1})\xleftarrow{\ \ref{algTrjOT}\ }
 ((j^q_0,\ldots,j^q_{n-1}),M')$.
  \item For $i=0$ to $n-2$ do
  \item   \quad $t\leftarrow\Phi'_p(J^q_i,J^q_{i+1})^{-1}\pmod{p^{M'}}$.
  \item   \quad $D_i\leftarrow t\Phi'_p(J^q_{i+1},J^q_i)\pmod{p^{M'}}$.
  \item   \quad $P_i\leftarrow t((\Phi_p(J^q_i,J^q_{i+1})\pmod{p^{M'}})
 \pmod{p^m})$.
  \item $R\leftarrow\Phi'_p(J^q_0,J^q_{n-1})\pmod{p^{M'}}$.
  \item $S\leftarrow(((\Phi_p(J^q_{n-1},J^q_0)\pmod{p^{M'}}))/p^m)\pmod{p^M}$.
  \item If either $D_i$ is determined by a point from outside of 
the nonsupersingular elliptic curve, that point will be eliminated.
  \item For $i=0$ to $min(M',n-2)$ do
  \item   \quad $S\leftarrow S-RP_i\pmod{p^{M'}}$
  \item   \quad $R\leftarrow-RD'_i\pmod{p^{M'}}$
  \item $R^q\leftarrow R+\Phi'_p(J^q_{n-1},J^q_0)\pmod{p^{M'}}$.
  \item $P^q_{n-1}\leftarrow SR^{-1}\pmod{p^{M'}}$.
  \item If any $P$ characterizes a point from outside of the 
 nonsupersingular elliptic curve, resumes at step 7.
  \item For $i=n-2$ to $0$ by step -1 do
  \item   \quad $P_i\leftarrow P_i-D_i\ P^q_{i+1}\pmod{p^{M'}}$.
  \item For $i=0$ to $n-1$ do
  \item   \quad $J^q_i\leftarrow J^q_i-p^{M'}\cdot P_i/D'_i\pmod{p^{M'}}$.
  \item Return $(J^q_0,\ldots,J^q_{n-1})$.
 \end{enumerate}
\end{algorithm}


\subsection{Transformation of the first invariant $j$}

The repeated application of Vercauteren's property can be used 
on nonsupersingular elliptic curves spaces $F^q_p$ to compute the invariants
 $j^q$ (implementation \ref{algFjOT}).

\begin{algorithm}[htp]
  \caption{Converting the first invariant $j$}
 \label{algFjOT}

 \begin{itemize}
  \item[Input:] $j^q$, invariant $j\in\mathbb{F}^{q}_{p^n}/\mathbb{F}_{p^2}$ 
and precision $m'$ according to the algorithm \ref{algTrjOT}.
  \item[Output:] $J^q\in\mathbb{Z}_q$ with $J^q\equiv j^{p^{m-1}}\pmod{p}$
 and $\Phi_p(J^q,\Sigma(J^q))\equiv 0\pmod{p^m}$.
 \end{itemize}

 \begin{enumerate}
  \item $J^q\leftarrow j m'\ \pmod{p}$.
  \item For $i=2$ to $m$ do
  \item\quad $J^q\leftarrow$ Newton\_Iteration $(\Phi_p(X,J),J^p J^q \pmod{p},i)$.
    \item If $J^q$ have characteristics from outside the nonsupersingular 
elliptic curve then
  \item   \quad Resume from step 1.
  \item Return $J^q$.
 \end{enumerate}
\end{algorithm}


\section{Simplified version of SST for nonsupersingular elliptic curve 
$\mathbb{F}^{q}_{p}$} 

The inverse substitution of Frobenius $\Sigma^{-1}$  has as solving method:
$$
\Sigma^{-1}(\alpha)=\Sigma^{-1}
\Big(\overset{n-1}{\underset{\mathrm{i=0}}\sum}\alpha_it^i\Big)
=\overset{p-1}{\underset{\mathrm{j=0}}\sum}
\Big({\underset{\mathrm{0\leq pk+j<n}}\sum}\alpha_{pk+j}t^k\Big)C_j(t),
$$
where $C_j(t)=\Sigma^{-1}(t^j)\equiv t^{jp^{n-1}}(mod\ f(t))$. 
If we first compute $C_j(t)$ for $j=0,\ldots,p-1$ then $\Sigma^{-1}(\alpha)$ 
for $\alpha\in\mathbb{Z}_q$ will contain only $p-1$ multiplications in 
$\mathbb{Z}_q$.

Starting from those,  Kim et all \cite{kpcpk04} highlighted the possibility 
to use some finite fields with a Gaussian Normal Base (GNB) of small type. 
This base can be converted to $\mathbb{Z}_q$, thus, optimizing the computations 
on Frobenius iterations because $B$ from $\mathbb{Q}_q/\mathbb{Q}_p$ 
is normal if $\exists \beta\in\mathbb{Q}_q$ such that 
$B=\{\Lambda(\beta)|\Lambda\in Gal(\mathbb{Q}_q/\mathbb{Q}_p)\}$. 
From here can be deduced the next sentence \cite{kpcpk04}.

\begin{proposition}\label{prop2const}
 Let $p$ be a prime number and ($n,t$) two positive integers such that $(nt+1)$ 
is prime and other than $p$. Let $\gamma$ be a primitive root of order
 $(nt+1)$ of the unit in an extension of field $\mathbb{Q}_p$. If $gcd(nt/e,n)=1$, 
with order $e$ of $(p$ mod $(nt+1))$, then every primitive root of order 
$t$ of the unit $\tau$ in $\mathbb{Z}/(nt+1)\mathbb{Z}$ can be written as
 $$
\beta=\overset{t-1}{\underset{\mathrm{i=0}}\sum}\gamma^{\tau^i}.
$$
 It is an ordinary element and $[\mathbb{Q}_p(\beta):\mathbb{Q}_p]=n$. 
Such a base is called Gaussian Normal Base of type $t$.
\end{proposition}

In  \cite{kpcpk04} there are  values for $\mathbb{Z}_q$ as being elements 
from the  ring
$$
\mathbb{Z}_p[x]/(x^{nt+1}-1).
$$
The multiplication of two elements from $\mathbb{Z}_q/(p^m\mathbb{Z}_q)$ 
will require a number of operations with $O((nmt)^{\mu})$ complexity, 
which according to the proposition \ref{prop2const} can be optimized at $t\leq 2$.

For $t=1$ we have $\beta=\tau$ and the minimal polynomial of $\beta$ is
$$
f(x)=\frac{x^{n+1}-1}{x-1}=x^n+x^{n-1}+\ldots+x+1.
$$
It is possible to reduce the complexity of the computation from the 
Frobenius substitution by using a redundant representation based 
on an inclusion ($\mathbb{Z}_q$ from $\mathbb{Z}_p[x]/(x^{n+1}-1)$) 
which concludes in $\alpha=\overset{n-1}{\underset{\mathrm{i=0}}\sum}\alpha_i\beta^i$ 
and $\alpha(x)=\overset{n-1}{\underset{\mathrm{i=0}}\sum}\alpha_ix^i+0x^n$. 
Then $\Sigma^k(\beta)=\beta^{p^k}$ leads to
$$
\Sigma^k(\alpha(x))=\overset{n}{\underset{\mathrm{i=0}}
\sum}\alpha_ix^{ip^k}=a_0+\overset{n}{\underset{\mathrm{j=1}}\sum}
\alpha_{j/p^k}(mod\ (n+1))^{x^j}.
$$
The obtained result will lead to $\Sigma^k(\alpha)$ operations by 
permuting its coefficients $\alpha(x)$. This determines the computation 
method for Satoh-Skjernaa-Taguchi-systems types over elliptical curves 
which contain cryptographic points of degree 1.

If we consider $\Gamma(X,\Sigma(X))=0$, and $x\in\mathbb{Z}_q$ 
a root for $\Gamma(X,Y)\in\mathbb{Z}_q[X,Y]$, we compute an 
approximation $x_m\equiv x\pmod{p^m}$ and define $\delta_m=(x-x_m)/p^m$.
 By constructing the Taylor series expansion for $x_m$, will result:
\begin{equation}\label{eqvi14}
\begin{aligned}
 0&= \Gamma(x,\Sigma(x))=\Gamma(x_m+p^m\delta_m,\Sigma(x_m+p^m\delta_m))\\
 &\equiv \Gamma(x_m,\Sigma(x_m))+p^m(\delta_n\Delta_x+\Sigma(\delta_m)\Delta_y)
\pmod{p^{2m}},
\end{aligned}
\end{equation}
where
\begin{gather*}
\Delta_x\equiv\frac{\partial\Gamma}{\partial X}(x_m,\Sigma(x_m))\pmod{p^m},\\
\Delta_y\equiv\frac{\partial\Gamma}{\partial Y}(x_m,\Sigma(x_m))\pmod{p^m}
\Gamma(x_m,\Sigma(x_m))\equiv 0\pmod{p^m}
\end{gather*}
 Simplifying with $p^m$ we obtain the relation
\begin{equation}\label{eqgamma}
 \frac{\Gamma(x_m,\Sigma(x_m))}{p^m}+\delta_m\Delta_x
+\Sigma(\delta_m)\Delta_y\equiv 0\pmod{p^m}
\end{equation}
for $\delta_m$ mod $p^m$.

To obtain first degree points it is sufficient to have
 $\operatorname{ord}_p(\Delta_y)=0$, which means that $\Delta_y$ 
is a unit in $\mathbb{Z}_q$ and $ord_p(\Delta_x)>0$.
 Performing the reduction operation modulo $p$ for equation \eqref{eqgamma}
 we get the next result:
\begin{equation}
 \delta^p_m=-\frac{\Gamma(x_m,\Sigma(x_m))}{p^m\Delta_y}\pmod{p}
\end{equation}
which has a unique root of order $p$: $\delta_m\in\mathbb{F}_q$. 
This is an approximation of $x$, given by 
$x_m+p^m\delta_m\equiv x(mod\ p^{m+1})$. The root of order $p$ 
has a compute complexity of a grater order. There were given simplified 
solutions from Satoh, Skjernaa and Taguchi, by replacing the equation 
$\Gamma(X,\Sigma(X))=0$ with $\Gamma(\Sigma^{-1}(X),X)=0$. Thus, 
$\delta_m$ will be defined as:
$$
\delta_m\equiv-\frac{\Gamma(\Sigma^{-1}(x_m),x_m)}{p^m\frac{\partial\Gamma}
{\partial Y}(\Sigma^{-1}(x_m),x_m)}\pmod{p}.
$$
From $\Gamma(\Sigma^{-1}(x_m),x_m)\equiv 0\pmod{p^m}$ it is necessary only 
to compute the inverse of $(\frac{\partial\Gamma}{\partial Y}(\Sigma^{-1}(x_m),x_m)$ 
mod $p)$. Therefore, it can replace Satoh's classical method \cite{satoh02} 
for nonsupersingular elliptic curve $\mathbb{F}^{q}_{p}$ 
(our solution can be found in the algorithm \ref{algSSTnOT}).

\begin{algorithm}[htp]
 \caption{SST's simplified version for nonsupersingular elliptic curve 
$\mathbb{F}^{q}_{p}$}
  \label{algSSTnOT}

  \begin{itemize}
   \item[Input:]  Polynomial $\Gamma(X,Y)\in\mathbb{Z}_q$, 
item $x_0\in\mathbb{Z}_q$ which satisfies 
$\Gamma(\Sigma^{-1}(x_0),x_0)\equiv 0\pmod{p}$ and the precision $m$.
   \item[Output:] Item $x_m\in\mathbb{Z}_q$ with 
$\Gamma(\Sigma^{-1}(x_m),x_m)\equiv 0\pmod{p^m}$ and $x_m\equiv x_0\pmod{p}$.
  \end{itemize}

  \begin{enumerate}
    \item For $i=2$ to $m$ do
   \item   \quad $x^q_m(i)\leftarrow$ ALG \ref{algFjOT}($x_m,m$)
   \item If $x^q_m(i)$ is not included in the nonsupersingular elliptic curve then
  \item   \quad resumes on step 1
   \item $d\leftarrow \left(\frac{\partial\Gamma}{\partial Y}(\Sigma^{-1}(x_0),x_0)\right)^{-1}\ \pmod{p}$.
   \item $y\leftarrow x_0\pmod{p}.$
   \item For i=0 to m do
   \item   \quad $x\leftarrow \lfloor \frac{\Sigma^{-1}(y)\pmod{p^i}}{x^q_m(i)} \rfloor.$
   \item   \quad $y\leftarrow y-d\Gamma(x,y)\pmod{p^i}$.
   \item Return $y$.
  \end{enumerate}
\end{algorithm}

The complexity of the classic algorithm is given by the recalculation of 
$\Gamma(x,y)$ after every iteration. Therefore, the values of $x$ and $y$ 
at step $i+1$ are very close to the values from step $i$. On the other hand, 
the result given in algorithm \ref{algSSTnOT} uses an approximation 
of the two parameters which simplify the computations.
After determining $x_W\equiv x\pmod{p^W}$ associated to a point $W$,
 we select the elements $s\in\mathbb{N}$, for which
\begin{equation}\label{eqvi15}
 \Gamma(\Sigma^{-1}(x_{sW+i}),x_{sW+i})\equiv \Gamma(\Sigma^{-1}(x_{sW}),x_{sW})
+\Delta(mod\ p^{(s+1)W})
\end{equation}
with
$$
\Delta=p^{sW}\Big(\frac{\partial\Gamma}{\partial X}(\Sigma^{-1}(x_{sW}),x_{sW})
\Sigma^{-1}(\delta)+\frac{\partial\Gamma}{\partial Y}
(\Sigma^{-1}(x_{sW}),x_{sW})\delta\Big).
$$

 Finally, to obtain the solution, we compute the partial derivatives
$$
\frac{\partial\Gamma}{\partial X}(\Sigma^{-1}(x_{sW}),x_{sW})\quad
 \mbox{and}\quad
 \frac{\partial\Gamma}{\partial Y}(\Sigma^{-1}(x_{sW}),x_{sW})
$$
in $\pmod{p^W}$ case.

For $\Gamma(\Sigma^{-1}(x_{sW}),x_{sW})$ and $i<W$ can be determined 
$\Gamma(\Sigma^{-1}(x_{sW+i}),x_{sW+i})$, by using  \eqref{eqvi15}.

\subsection{A variant of SatSk-Taguchi's algorithm for nonsupersingular 
elliptic curves defined over $\mathbb{F}_{q}$}

Starting from the parameter description of the nonsupersingular elliptic 
curves (algorithm \ref{algTrjOT}) and the method to compute the points 
of degree 1, we determined an implementation to compute the elements $x_m$. 
This is implemented for the subspaces of invariants which cannot be deduced 
directly from cryptographic analysis of the ANG system 
(illustrated in algorithm \ref{algSSTOT}).

\begin{algorithm}[htp]
  \caption{Variant of SatSk-Taguchi's algorithm for nonsupersingular elliptic 
curves defined over $\mathbb{F}_{q}$}
  \label{algSSTOT}

  \begin{itemize}
   \item[Input:]  Polynomial $\Gamma(X,Y)\in\mathbb{Z}_q$, item 
$x_0\in\mathbb{Z}_q$ which satisfy $\Gamma(\Sigma^{-1}(x_0),x_0)\equiv 0\pmod{p}$ 
and precision $m$. Canonical system ($J^q_0,\ldots,J^q_{n-1}$), obtained 
using algorithm \ref{algTrjOT}.
   \item[Output:] Item $x^q_m\in\mathbb{Z}_q$, with 
$\Gamma(\Sigma^{-1}(x^q_m),x^q_m)\equiv 0\pmod{p^m}$ and 
$x^q_m\equiv x_0\pmod{p}$.
  \end{itemize}

  \begin{enumerate}
   \item $y\leftarrow$ ALG \ref{algSSTnOT}$(x_0,W)$.
   \item $x\leftarrow\Sigma^{-1}\pmod{p^W}$.
   \item $\Delta_x\leftarrow\frac{\partial \Gamma}{\partial X}(x,y)\pmod{p^W}$.
   \item $\Delta_y\leftarrow\frac{\partial \Gamma}{\partial Y}(x,y)\pmod{p^W}$.
   \item For $s=1$ to $\lfloor (m-1)/W\rfloor$ do
   \item   \quad $x\leftarrow\Sigma^{-1}(y)(mod\ p^{(s+1)W})$.
   \item   \quad $V\leftarrow\Gamma(x,y)(mod\ p^{(s+1)W})$.
   \item   \quad For $i=0$ to $W-1$ do
   \item     \qquad $\delta_y\leftarrow-dp^{-(sW+1)}V\pmod{p}$.
   \item     \qquad $\delta_x\leftarrow\Sigma^{-1}(\delta_y)(mod\ p^{W-i})$.
   \item     \qquad $y\leftarrow y+p^{sW+i}\delta_y(mod\ p^{(s+1)W})$.
   \item     \qquad $V\leftarrow V+p^{(sW+i)}
(\Delta_x\delta_x+\Delta_y\delta_y)(mod\ p^{(s+1)W})$.
   \item Return $y$.
  \end{enumerate}
\end{algorithm}

For optimal implementations it is necessary to use only the $W$ points 
which are multiples of the processor registry size.

\section{Implementation}

Based on the illustrated algorithms, we can construct the encryption 
system for the case of nonsupersingular elliptic curves. Starting 
from the Koblitz's general case solution (\cite{nk94}), a particular 
algorithm is developed with respect to Hensel's theorem conditions.

Let be the parameters $(\mathcal{F},\phi,\alpha_E,\beta_E,\Gamma,\rho,\xi)$, 
$\eta$ and $\mu=\mu_{1}, \dots,\mu_{n}$ the plain message.
 For each $\mu_{j},\ j=1, \dots, n$, the necessary steps are:
\begin{enumerate}
 \item Let $\mu_{j}$ be an integer which respects the condition: 
$0\leq \mu_{j}\leq \frac{p}{\eta}-1$
 \item Let $x_i=\eta \mu_{j}+i$ where $i=0,1,2\ldots, (\eta - 1)$
 \item Compute $c_i=x_i^3+\alpha_E x_i+ \beta_E$ using recursive operations 
until $c_i^{\frac{\phi-1}{2}}\equiv 1(mod\ \phi)$
 \item ALG \ref{algSSTOT}($\Gamma$, $c_i$)
 \item Compute $y_i=\sqrt{c_i}$
 \item $\mathcal{M}(x_i,y_i)=(x_i,y_i^{(\phi+1)/4})$ is 
the point on the elliptical curve that corresponds to the message $\mu_{j}$.
\end{enumerate}


\subsection*{Conclusions}

In the present paper, starting from the classical algorithms which 
offer solutions in the general cases, we developed our own solutions 
for the particular case of boundary conditions which are determined by
 models based on nonsupersingular elliptic curves.

This model is resistant to differential analysis due to Frobenius'
 isomorphism that was used to the implementation.

Further research will consist in reducing the computation complexity 
of partial differential equations which are involved in the algorithms.

\subsection*{Acknowledgments}
The author acknowledges the support through Grant of The Executive 
Council for Funding Higher Education, Research and Innovation, 
Romania-UEFISCDI, Project Type: Advanced Collaborative Research Projects 
- PCCA, Number 23/2014.

\begin{thebibliography}{00}

\bibitem{amv93} G. B. Agnew, R. C. Mullin, S.A. Vastone;
An implementation of elliptic curve cryptosystems over $f_{2^{155}}$, 
\emph{IEEE Journal on Selected areas in Communications}, \textbf{5} no. 11 (1993), 
804--813.

\bibitem{acr14} R. Alsaedi, N. Constantinescu, V. Radulescu;
Nonlinearities in Elliptic Curve Authentication, \emph{Entropy},  
\textbf{16} no.9 (2014), 5144--5158.

\bibitem{kpcpk04} H.Y. Kim, J. Y. Park, J. H. Cheon, J. H. Park, J. H. Kim,
 S. G. Hahn;
 Fast elliptic curve point counting using Gaussian Normal Basis, 
\emph{Algorithmic Number Theory, Lecture Notes in Computer Science, 
Springer Berlin Heidelberg}, \textbf{3076} (2004), 292--307.

\bibitem{nk87} N. Koblitz;
 Elliptic curve cryptosystems, \emph{Mathematics of Computation},
\textbf{48} no. 177 (1987), 203--209.

\bibitem{nk94} N. Koblitz;
\emph{A Course in Number theory and Cryptography}, New York. Springer, 1994.

\bibitem{lst64} J. Lubin, J.-P. Serre, J. Tate;
 Elliptic curves and formal groups, \emph{Lecture notes prepared in
 connection with the seminars held at the Summer Institute on Algebraic Geometry, 
Woods Hole}, American Mathematical Society (1964).

\bibitem{vm86} V. S. Miller;
 Use of elliptic curves in cryptography, 
\emph{Advances in Cryptology  CRYPTO 85 Proceedings, 
Lecture Notes in Computer Science, Springer}, \textbf{218} (1986), 417--426.

\bibitem{satoh02} T. Satoh;
 On p-adic point counting algorithms for elliptic curves over finite fields, 
\emph{Algorithmic Number Theory, Lecture Notes in Computer Science Springer},
\textbf{2369} (2002), 43--66.

\bibitem{ser79} J. P. Serre;
\emph{Local Fields}, Springer-Verlag, GTM 67, 1979.

\bibitem{smart99} N. P. Smart;
 Elliptic curves over small fields of odd characteristic, 
\emph{Journal of Cryptography}, \textbf{12} no. 2 (1999), 141--151.

\bibitem{st01} A. Stein;
 Sharp upper bounds for arithmetics in hyperelliptic function fields, 
\emph{Journal of the Ramanujan Mathematical Society}, \textbf{16} (2001), 1--86.

\bibitem{DBLPOT} O. A. \c{T}icleanu, N. Constantinescu, D. Eb{\^{a}}nca;
 Intelligent data retrieval with hierarchically structured information, 
\emph{Intelligent Interactive Multimedia Systems and Services 
- Proceedings of the 6th International Conference on Intelligent 
Interactive Multimedia Systems and Services, {IIMSS} 2013, Sesimbra, Portugal},
 doi: 10.3233/978-1-61499-262-2-345 (2013), 345--351.

\bibitem{jkcctOT} O. A. \c{T}icleanu;
 Mathematical Models in Cryptography, \emph{Journal of Knowledge
 Communication and Computing Technologies}, \textbf{4} (2013), 1--9.

\bibitem{analeOT} O. A. \c{T}icleanu;
 Nonlinear analysis on elliptic curves subspaces with cryptographic 
applications, \emph{Annals of the University of Craiova, Mathematics
 and Computer Science Series}, \textbf{41} no. 2 (2014), 292--299.

\end{thebibliography}

\end{document}