% Abstrat of your communication to the
% ACA2018 Conference (Santiago de Compostela, 2018).
% You must use LaTeX format.


%====================================================
% IMPORTANT: DO NOT MODIFY THE FOLLOWING LINES
%====================================================

\documentclass{article}

\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amssymb,amsthm,amsmath, amsfonts, latexsym}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{times}

\setlength{\oddsidemargin}{1.46cm}
\setlength{\textwidth}{13cm}
\setlength{\topmargin}{0.0cm}
\setlength{\textheight}{20.5cm}

\makeatletter
\newcommand{\TITLE}[2][]{
  \begin{center} \Large \bfseries #2%
  \def\@temp{#1}\ifx\@temp\@empty\relax\else\footnote{#1}\fi\end{center}}

\newcommand{\AUTHOR}[2][]{\textbf{#2}%
  \def\@temp{#1}\ifx\@temp\@empty\relax\else\textsuperscript{#1}\fi}

\newcommand{\ADDRESS}[2]{\noindent
  \textsuperscript{#1}\parbox[t]{0.9\textwidth}{#2} \vspace{6pt}}

\makeatother

\newcommand{\KEYWORDS}[1]{\paragraph{Keywords:} #1}
%\newcommand{\MSCLASSIFICATION}[1]{\paragraph{Mathematics Subject Classification 2010:} #1}

\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\setcounter{footnote}{0}
\pagestyle{empty}

\newcommand{\HEADING}{
{\noindent \small Applications of Computer Algebra -- ACA2018 \\
Santiago de Compostela, June 18--22, 2018} \vspace{10pt}}

%===============================================
% DO NOT MODIFY THE ABOVE LINES
%===============================================

\newcommand{\C}{\mathbb{C}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\hache}{\mathbb{H}}
\newcommand{\I}{\mathbb{I}}
\newcommand{\K}{\mathbb{K}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}

\begin{document}

\HEADING


\TITLE{Conversion of element representations in Galois rings}

% If you need to thank someone next to the title, please use the next line (and delete the previous one)

% \TITLE[thanks]{Title of talk}

% Write the author names in the order you wish them to appear
% and underline the one who will give the talk.
% Identify each one of them with a number
% in order to give their own affiliations later on. 

\begin{center}
 \AUTHOR[1]{\underline{Juan Carlos Ku-Cauich}}, % the author who will give the talk
 \AUTHOR[2]{Guillermo Morales-Luna}
% IF two or more authors have the same affiliation, associate to them the same number.
% For instance, if there are three authors and the first a the second ones have the same affiliation,
% write as follows:
% \AUTHOR[1]{Third Author}
\end{center}

A Galois ring is a finite ring with unity such that the divisors of zero, together with zero itself, form a principal ideal, generated by an element of the form $pe$, where $e$ is the ring unit and $p$ is a prime number. For any prime $p$ and two integers $s,m$, the map 
$$\pi_p:\Z_{p^s}[X] \to \F_p[X]\ ,\ g(X)=\sum_{j=0}^{m-1}a_jX^j\mapsto g(X)\bmod p = \sum_{j=0}^{m-1}(a_j\bmod p)X^j,$$ is a ring homomorphism. 
An irreducible polynomial $h(X)\in\Z_{p^s}[X]$ is basic if $\pi_p(h(X))$ is irreducible in $\F_p[X]$ and in this case $\Z_{p^s}/\langle h(X)\rangle$ is a Galois ring, denoted $GR(p^s,m)$.  Let $\eta=X+ \langle h(X)\rangle\in GR(p^s,m)$, then $h(\eta)=0$ and $\F_{p^m}\approx\left[\Z_p[X]/\langle \pi_p(h(X))\rangle\right]$. Hence, $GR(p^s,m)=\Z_{p^s}[\eta]$ and each element in the Galois ring can be written in an additive form: $\sum_{j=0}^{m-1}a_j\eta^j$, with $a_j\in\Z_{p^s}$.

A polynomial $g(X)\in\Z_{p^s}[X]$ is basic primitive if $\pi_p(g(X))$ is primitive in $\F_p[X]$. It is well known~\cite{w03} that there is an element $\xi\in GR(p^s,m)$ and a basic primitive polynomial $g(X)\in\Z_{p^s}[X]$ of degree $m$ such that $o(\xi)=p^m-1$, $g(\xi)=0$, $g(X)|(X^{{p^m}-1}-1)$ in $\Z_{p^s}[X]$  and the following two properties hold:
\begin{itemize}
\item  $GR(p^s,m)=\Z_{p^s}[\xi]$
\item  Each element in $GR(p^s,m)$ can be written uniquely in a $p$-adic form: $\sum_{k=0}^{s-1}b_k p^k$, with $b_k\in{\cal T}(g(X))$, where ${\cal T}(g(X)) = \{0\}\cup\left(\xi^i\right)_{i=0}^{p^m-2}$ is a Teichm\"uller set. 
\end{itemize}
Each primitive polynomial in $\F_p[X]$ characterizes a set of basic primitive polynomials in $\Z_{p^s}[X]$, namely its inverse image under the projection $\pi_p$. The $p$-adic representation depends on the chosen basic primitive polynomial.

We have developed a series of programs, basically in {\tt sage}, to find monic basic primitive polynomials and convert additive representations into $p$-adic representations of the Galois ring elements, and conversely.

For any $m\in\Z^+$ there is~\cite{lidl96} a monic primitive polynomial $f_{pm}(X)\in\F_p[X]$ dividing $P_{pm}(X)=X^{{p^m}-1}-1$ in $\F_p[X]$. Then, by Hensel Lift~\cite{mc74} there is a monic basic primitive polynomial $f_{psm}(X)\in\Z_{p^s}[X]$ dividing $P_{pm}(X)$ in $\Z_{p^s}[X]$ with projection $f_{pm}(X)$. Since $f_{pm}(X)\in\F_p[X]$ is irreducible with no multiple roots, the polynomial $f_{psm}(X)\in\Z_{p^s}[X]$ is unique~\cite{w03}. Hence, a natural correspondence $f_{pm}(X)\leftrightarrow f_{psm}(X)$ arises, and in most cases it is not the identity, namely $f_{pm}(X)\not= f_{psm}(X)$ in $\Z_{p^s}[X]$.

In the worst case, for small values of $m$ and $s$ the search of the Hensel lift polynomial $f_{psm}(X)\in\Z_{p^s}[X]$ can be done exhaustively. Alternatively, a list~\cite{lidl96} of monic primitive polynomials in the ring $\F_p[X]$ may be provided in order to consider the inverse images of those polynomials under the projection modulus $p$.

The interest in finding effective and efficient representation conversions is due to the implementation of authentication codes based on the Gray transform~\cite{Ku-CauichT13}.


% Write the keywords separated by commas

\KEYWORDS {Galois rings, Teichm\"uller elements, symbolic computation}

% Write the MSC2010 codes corresponding to your communication

%\MSCLASSIFICATION{Code1, Code2}



% Next include the references you need. 
% If your abstract includes no references at all, please delete all the lines
% from \begin{thebibliography} to \end{thebibliography}.

% Please, do not use more than 9 references.

\bibliographystyle{plain}
\bibliography{grsc}

%\begin{thebibliography}{9}
%
%  % Model for references to books.
%  \bibitem{label1} \textsc{Z.-X. Wan; A. Uthor2}, \emph{Lectures on Finite Fields and Galois Rings}.
%    World Scientific, Singapore, 2003.
%  
%  \bibitem{label1} \textsc{B. R. McDonald}, \emph{Finite Rings with Identity}.
%    Marcel Deckker, Inc., New York, 1974.  
%
% %  Model for references to articles
%  \bibitem{label2} \textsc{J. C. Ku-Cauich; H. Tapia-Recillas},
%  \emph{Systematic Authentication Codes Based on a Class of Bent Functions and the Gray Map on a Galois Ring} \textbf{27}(2), 1159--1170  (2013).
%
%  %  Model for references to proceedings. 
%  \bibitem{label3} \textsc{A. Uthor}, Title.
%  In \emph{Title of the proccedings}, names of the editors (eds.),
%   first page--last page. Editorial, City, year of publication.
%
%\end{thebibliography}

\vspace{1cm}

% Full Affiliation of all authors
\ADDRESS{1}{
Computer Science  \\ CINVESTAV-IPN \\
Mexico City, Mexico \\
\texttt{jckc35@hotmail.com}
}

\vspace{.5cm}

\ADDRESS{2}{
Computer Science  \\ CINVESTAV-IPN \\
Mexico City, Mexico \\
\texttt{gmorales@cs.cinvestav.mx}
}


\end{document}
