%% This document created by Scientific Notebook (R) Version 3.0


\documentclass[12pt,thmsa]{article}
\usepackage{amssymb}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{makeidx}
\usepackage{sw20jart}

%TCIDATA{TCIstyle=article/art4.lat,jart,sw20jart}

%TCIDATA{<META NAME="ViewSettings" CONTENT="31">}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="Title" CONTENT="Other Systems Modulo m">}
%TCIDATA{Created=Mon Aug 19 14:52:24 1996}
%TCIDATA{LastRevised=Thu Feb 13 16:57:33 1997}
%TCIDATA{Language=American English}
%TCIDATA{CSTFile=MathHelp.cst}
%TCIDATA{<LINK REL="begin" HREF="DM12-1.tex">}
%TCIDATA{<LINK REL="contents" HREF="DM0-0.tex">}
%TCIDATA{<LINK REL="end" HREF="DM12-6.tex">}
%TCIDATA{<LINK REL="next" HREF="DM12-4.tex">}
%TCIDATA{<LINK REL="parent" HREF="DM12.tex">}
%TCIDATA{<LINK REL="previous" HREF="DM12-2.tex">}
%TCIDATA{<LINK REL="top" HREF="DM0-0.tex">}

\input{tcilatex}
\begin{document}


\section{\label{Matrices modulo m}Other Systems Modulo m}

The mod function also works with matrices and with polynomials.

\subsection{\ Matrices Modulo m}

To reduce a matrix $A$ modulo $m$, enter the expression $A\limfunc{mod}m$
and evaluate it.\medskip

\begin{quote}
$\blacktriangleright $ \textsf{Evaluate}
\end{quote}

\begin{quotation}
$\left[ 
\begin{array}{cc}
5 & 8 \\ 
9 & 4
\end{array}
\right] \limfunc{mod}3=\allowbreak \left[ 
\begin{array}{cc}
2 & 2 \\ 
0 & 1
\end{array}
\right] $

\ 

$\left( 
\begin{array}{ccc}
3 & 7 & 5 \\ 
5 & 4 & 8 \\ 
2 & 0 & 5
\end{array}
\right) ^{-1}\limfunc{mod}11=\allowbreak \left( 
\begin{array}{ccc}
9 & 9 & 3 \\ 
2 & 5 & 1 \\ 
3 & 3 & 10
\end{array}
\right) $

\ 

$\left( 
\begin{array}{ccc}
3 & 7 & 5 \\ 
5 & 4 & 8 \\ 
2 & 0 & 5
\end{array}
\right) \,\left( 
\begin{array}{ccc}
9 & 9 & 3 \\ 
2 & 5 & 1 \\ 
3 & 3 & 10
\end{array}
\right) \limfunc{mod}11=\allowbreak \left( 
\begin{array}{ccc}
1 & 0 & 0 \\ 
0 & 1 & 0 \\ 
0 & 0 & 1
\end{array}
\right) \medskip $
\end{quotation}

\ 

\begin{example}
The 
\index{Hamming code@Hamming code}Hamming\label{Hamming code} (7,4) code
operates on 4-bit 
\index{Message word@Message word}message words (half a 
\index{Byte@Byte}byte, \label{Byte}and hence a 
\index{Nibble@Nibble}\textsl{nibble}) \label{Nibble}and generates 7-bit 
\index{Code word@Code word}code words.\label{Code word}

\textsf{Define }$H=\left[ 
\begin{array}{ccccccc}
1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 
1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 
0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 
1 & 1 & 0 & 1 & 0 & 0 & 1
\end{array}
\right] 
\vspace{14pt}$

Given a message word $\mathbf{m}$, the corresponding code word is given by $%
\mathbf{m}H\limfunc{mod}2=\mathbf{c}$. Thus, 
\[
\left[ 
\begin{array}{cccc}
1 & 0 & 1 & 1
\end{array}
\right] \left[ 
\begin{array}{ccccccc}
1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 
1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 
0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 
1 & 1 & 0 & 1 & 0 & 0 & 1
\end{array}
\right] \limfunc{mod}2=\left[ 
\begin{array}{ccccccc}
0 & 1 & 1 & 0 & 0 & 1 & 1
\end{array}
\right] 
\]
The message word 
\index{Message word@Message word} appears in bits \label{Message word}3, 5,
6, and 7. The remaining 3 bits can be thought of as generalized parity bits.
The code word is then transmitted. At the receiving end, another matrix
multiplication is done to check for errors.

\textsf{Define }$P=\left[ 
\begin{array}{ccc}
0 & 0 & 1 \\ 
0 & 1 & 0 \\ 
0 & 1 & 1 \\ 
1 & 0 & 0 \\ 
1 & 0 & 1 \\ 
1 & 1 & 0 \\ 
1 & 1 & 1
\end{array}
\right] \bigskip $
\end{example}

\begin{example}
The matrix product $\mathbf{c}P%
\limfunc{mod}2=\left[ 
\begin{array}{ccc}
0 & 0 & 0
\end{array}
\right] $ indicates that no errors were detected and the message word $%
\mathbf{m}$ is taken to be bits 3, 5, 6, and 7 of the code word. However, if
the code word is corrupted and $\mathbf{c}=\left[ 
\begin{array}{ccccccc}
0 & 0 & 1 & 0 & 0 & 1 & 1
\end{array}
\right] $ is received, then $\mathbf{c}P\limfunc{mod}2=\left[ 
\begin{array}{ccc}
0 & 1 & 0
\end{array}
\right] $, which is the binary equivalent of 2, and hence an error occurred
in the second bit. Thus, the correct code word is $\left[ 
\begin{array}{ccccccc}
0 & 1 & 1 & 0 & 0 & 1 & 1
\end{array}
\right] $. The message word from columns 3, 5, 6, and 7 is then $\left[ 
\begin{array}{cccc}
1 & 0 & 1 & 1
\end{array}
\right] $.\bigskip
\end{example}

\begin{example}
A \textsl{two-by-two } 
\index{Block cipher@Block cipher}\textsl{block cipher} is given by\label%
{Block cipher} 
\[
\left[ 
\begin{array}{c}
y_{1} \\ 
y_{2}
\end{array}
\right] =\left[ 
\begin{array}{cc}
a_{11} & a_{12} \\ 
a_{21} & a_{22}
\end{array}
\right] \left[ 
\begin{array}{c}
x_{1} \\ 
x_{2}
\end{array}
\right] 
\limfunc{mod}26 
\]
where the $x_{i}$s represent plaintext, the $y_{i}$s represent ciphertext,
and the matrix entries are integers. For example, $\left[ 
\begin{array}{cc}
5 & 8 \\ 
2 & 7
\end{array}
\right] \left[ 
\begin{array}{c}
4 \\ 
11
\end{array}
\right] \limfunc{mod}26=\,\left[ 
\begin{array}{c}
4 \\ 
7
\end{array}
\right] $means that the plaintext pair $[E,L]$ (two adjacent letters in the
secret message ``Elroy was here'') gets mapped to the ciphertext pair $[E,H]$%
, using the correspondence $A\leftrightarrow 0,$ $B\leftrightarrow 1,$ $%
C\leftrightarrow 2,\ldots ,$ $Z\leftrightarrow 25.$

Given the ciphertext, you can recover the plaintext by computing the inverse
of the two-by-two matrix modulo 26. For example, 
\[
\left[ 
\begin{array}{cc}
5 & 8 \\ 
2 & 7
\end{array}
\right] ^{-1}\limfunc{mod}26=\left[ 
\begin{array}{cc}
25 & 16 \\ 
4 & 3
\end{array}
\right] 
\]
and hence 
\[
\left[ 
\begin{array}{cc}
25 & 16 \\ 
4 & 3
\end{array}
\right] \left[ 
\begin{array}{c}
4 \\ 
7
\end{array}
\right] \limfunc{mod}26=\left[ 
\begin{array}{c}
4 \\ 
11
\end{array}
\right] 
\]
recovers the original plaintext. You can handle longer messages by replacing
the column vector$\left[ 
\begin{array}{c}
E \\ 
L
\end{array}
\right] $ by the matrix $\left[ 
\begin{array}{cccccc}
E & R & Y & A & H & R \\ 
L & O & W & S & E & E
\end{array}
\right] $ and calculating one matrix product 
\[
\left[ 
\begin{array}{cc}
25 & 16 \\ 
4 & 3
\end{array}
\right] \left[ 
\begin{array}{cccccc}
4 & 17 & 24 & 0 & 7 & 17 \\ 
11 & 14 & 22 & 18 & 4 & 4
\end{array}
\right] \func{mod}26=\left[ 
\begin{array}{cccccc}
16 & 25 & 16 & 2 & 5 & 21 \\ 
23 & 6 & 6 & 2 & 14 & 2
\end{array}
\right] . 
\]
\bigskip \medskip
\end{example}

\subsection{\ \label{Polynomials modulo m}Polynomials Modulo m}

The $\limfunc{mod}$ function can also be combined with polynomials: 
\index{Polynomials @Polynomials !modulo m@modulo m}\medskip

\begin{quote}
$\blacktriangleright $ \textsf{Evaluate}
\end{quote}

\begin{quotation}
$x^{5}+9x^{4}-x^{3}+7x-2%
\limfunc{mod}5=\allowbreak x^{5}+4x^{4}+4x^{3}+2x+3\medskip $
\end{quotation}

Thus \textsf{Evaluate} reduces each of the coefficients modulo $5$.

Given a prime $p$, the set of polynomials with coefficients reduced modulo $%
p $ is a ring, denoted by $GF_p[x]$.\medskip

\begin{quote}
$\blacktriangleright $ To calculate a product of polynomials $a(x)$ and $%
b(x) $ in $GF_{p}[x]$
\end{quote}

\begin{enumerate}
\item[1.]  Expand the product $a(x)b(x).$

\item[2.]  Reduce the product modulo $p.\medskip $
\end{enumerate}

To calculate the product of $4x^5+5x+3$ and $6x^4+x^3+3$ in $GF_7[x]$, do
the following steps.\medskip

\begin{quote}
$\blacktriangleright $ \textsf{Expand}
\end{quote}

\begin{quotation}
$\left( 4x^{5}+5x+3\right) \left( 6x^{4}+x^{3}+3\right)
=\,24x^{9}+4x^{8}+42x^{5}+23x^{4}+3x^{3}+15x+9\medskip $
\end{quotation}

\begin{quote}
$\blacktriangleright $ \textsf{Evaluate}
\end{quote}

\begin{quotation}
$24x^{9}+4x^{8}+42x^{5}+23x^{4}+3x^{3}+15x+9\limfunc{mod}7=\allowbreak
3x^{9}+4x^{8}+2x^{4}+3x^{3}+x+2\medskip $
\end{quotation}

The sum of $4x^{5}+5x+3$ and $6x^{4}+x^{3}+3$ in $GF_{7}[x]$ is slightly
simpler.\medskip

\begin{quote}
$\blacktriangleright $ \textsf{Evaluate}
\end{quote}

\begin{quotation}
$\left( 4x^{5}+5x+3\right) +\left( 6x^{4}+x^{3}+3\right) \limfunc{mod}%
7=\,4x^{5}+6x^{4}+x^{3}+5x+6$
\end{quotation}

\strut

\subsection{\ Related topics}

\hyperref{Solving Equations}{}{}{DM12-1.tex#Integer solutions}

\hyperref{Integers Modulo m}{}{}{DM12-2.tex#Integers modulo m}

\hyperref{Polynomials Modulo Polynomials}{}{}{DM12-4.tex#Polynomials modulo
polynomials}

\hyperref{Linear Programming}{}{}{DM12-5.tex#Linear programming}

\hyperref{Exercises and Solutions}{}{}{DM12-6.tex#Exercises}

\rule{0.67in}{0.01in}

\hyperref{\FRAME{itbpF}{0.5275in}{0.3399in}{0.0519in}{}{}{index.wmf}{\special%
{language "Scientific Word";type "GRAPHIC";display "PICT";valid-file
"F";width 0.5275in;height 0.3399in;depth 0.0519in;original-width
36.875pt;original-height 22.5625pt;cropleft "0";croptop "1";cropright
"1";cropbottom "0";filename 'index.wmf';file-properties "XNPEU";}}}{}{}{%
DMIndex.tex#Math Index}\quad {\small Index entries: \hyperref{Applied modern
algebra}{}{}{DMIndex.tex#Applied modern algebra}, \hyperref{Congruence}{}{}{%
DMIndex.tex#Congruence}, \hyperref{Polynomials}{}{}{DMIndex.tex#Polynomials}%
, \hyperref{Solve}{}{}{DMIndex.tex#Solve}}

\end{document}
