More on exponentiation by squaring - libzahl - big integer library
HTML git clone git://git.suckless.org/libzahl
DIR Log
DIR Files
DIR Refs
DIR README
DIR LICENSE
---
DIR commit f1b60d7365ca1437efd3f6f8c05d2cdc46bd24b6
DIR parent fba103dca7a472eb58159d45ff8700736f89a136
HTML Author: Mattias Andrée <maandree@kth.se>
Date: Thu, 12 May 2016 01:14:52 +0200
More on exponentiation by squaring
Signed-off-by: Mattias Andrée <maandree@kth.se>
Diffstat:
M doc/arithmetic.tex | 55 ++++++++++++++++++++++++++++++-
1 file changed, 54 insertions(+), 1 deletion(-)
---
DIR diff --git 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