commit f1b60d7365ca1437efd3f6f8c05d2cdc46bd24b6
Author: Mattias Andrée <[email protected]>
AuthorDate: Thu May 12 01:14:52 2016 +0200
Commit: Mattias Andrée <[email protected]>
CommitDate: Thu May 12 01:17:07 2016 +0200
More on exponentiation by squaring
Signed-off-by: Mattias Andrée <[email protected]>
diff --git a/doc/arithmetic.tex b/doc/arithmetic.tex
index 6835c43..45097e2 100644
--- a/doc/arithmetic.tex
+++ b/doc/arithmetic.tex
@@ -187,9 +187,62 @@ can be expressed as a simple formula
\vspace{-1em}
\[ \hspace*{-0.4cm}
a^b = \prod_{i = 0}^{\lceil \log_2 b \rceil}
- a^{2^i} \left \lfloor {b \over 2^i} \hspace*{-1ex} \mod 2 \right \rfloor
+ \left ( a^{2^i} \right )^{\left \lfloor {\displaystyle{b \over 2^i}}
\hspace*{-1ex} \mod 2 \right \rfloor}
\]
+\noindent
+This is a natural extension to the observations
+
+\vspace{-1em}
+\[ \hspace*{-0.4cm}
+ \forall n \in \textbf{Z}_{+} \exists B \subset \textbf{Z}_{+} : b =
\sum_{i \in B} 2^i
+ ~~~~ \textrm{and} ~~~~
+ a^{\sum x} = \prod a^x.
+\]
+
+\noindent
+The algorithm can be expressed in psuedocode as
+
+\vspace{1em}
+\hspace{-2.8ex}
+\begin{minipage}{\linewidth}
+\begin{algorithmic}
+ \STATE $r \gets 1$
+ \STATE $f \gets a$
+ \WHILE{$b \neq 0$}
+ \IF{$b \equiv 1 ~(\textrm{Mod}~ 2)$}
+ \STATE $r \gets r \cdot f$
+ \ENDIF
+ \STATE $f \gets f^2$ \qquad \textcolor{c}{\{$f \gets f \cdot f$\}}
+ \STATE $b \gets \lfloor b / 2 \rfloor$
+ \ENDWHILE
+ \RETURN $r$
+\end{algorithmic}
+\end{minipage}
+\vspace{1em}
+
+\noindent
+Modular exponentiation ($a^b \mod m$) by squaring can be
+expressed as
+
+\vspace{1em}
+\hspace{-2.8ex}
+\begin{minipage}{\linewidth}
+\begin{algorithmic}
+ \STATE $r \gets 1$
+ \STATE $f \gets a$
+ \WHILE{$b \neq 0$}
+ \IF{$b \equiv 1 ~(\textrm{Mod}~ 2)$}
+ \STATE $r \gets r \cdot f \hspace*{-1ex}~ \mod m$
+ \ENDIF
+ \STATE $f \gets f^2 \hspace*{-1ex}~ \mod m$
+ \STATE $b \gets \lfloor b / 2 \rfloor$
+ \ENDWHILE
+ \RETURN $r$
+\end{algorithmic}
+\end{minipage}
+\vspace{1em}
+
{\tt zmodpow} does \emph{not} calculate the
modular inverse if the exponent is negative,
rather, you should expect the result to be
