libzahl

big integer library
git clone git://git.suckless.org/libzahl
Log | Files | Refs | README | LICENSE

commit 87e84a9167666022bba7c73b5447791bf9f6797b
parent 18a0e23b2f2e37c56c4f0f9a3dd56c1c619a4468
Author: Mattias Andrée <maandree@kth.se>
Date:   Fri, 21 Oct 2016 05:20:55 +0200

Add exercise: [M13] The totient from factorisation

Signed-off-by: Mattias Andrée <maandree@kth.se>

Diffstat:
doc/exercises.tex | 57+++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 57 insertions(+), 0 deletions(-)

diff --git a/doc/exercises.tex b/doc/exercises.tex @@ -271,6 +271,38 @@ and $\varphi(1) = 1$. +\item {[\textit{M13}]} \textbf{The totient from factorisation} + +Implement the function + +\vspace{-1em} +\begin{alltt} + void totient_fact(z_t t, z_t *P, + unsigned long long int *K, size_t n); +\end{alltt} +\vspace{-1em} + +\noindent +which calculates the totient $t = \varphi(n)$, where +$n = \displaystyle{\prod_{i = 1}^n P_i^{K_i}} > 0$, +and $P_i = \texttt{P[i - 1]} \in \textbf{P}$, +$K_i = \texttt{K[i - 1]} \ge 1$. All values \texttt{P}. +\texttt{P} and \texttt{K} make up the prime factorisation +of $n$. + +You can use the following rules: + +\( \displaystyle{ + \begin{array}{ll} + \varphi(1) = 1 & \\ + \varphi(p) = p - 1 & \text{if } p \in \textbf{P} \\ + \varphi(nm) = \varphi(n)\varphi(m) & \text{if } \gcd(n, m) = 1 \\ + n^a\varphi(n) = \varphi(n^{a + 1}) & + \end{array} +}\) + + + \item {[\textit{HMP32}]} \textbf{Modular tetration} Implement the function @@ -711,6 +743,31 @@ then, $\varphi(n) = \varphi|n|$. +\item \textbf{The totient from factorisation} + +\vspace{-1em} +\begin{alltt} +void +totient_fact(z_t t, z_t *P, + unsigned long long *K, size_t n) +\{ + z_t a, one; + zinit(a), zinit(one); + zseti(t, 1); + zseti(one, 1); + while (n--) \{ + zpowu(a, P[n], K[n] - 1); + zmul(t, t, a); + zsub(a, P[n], one); + zmul(t, t, a); + \} + zfree(a), zfree(one); +\} +\end{alltt} +\vspace{-1em} + + + \item \textbf{Modular tetration} Let \texttt{totient} be Euler's totient function.