From 87e84a9167666022bba7c73b5447791bf9f6797b Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Fri, 21 Oct 2016 05:20:55 +0200 Subject: Add exercise: [M13] The totient from factorisation MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- doc/exercises.tex | 57 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 57 insertions(+) (limited to 'doc') diff --git a/doc/exercises.tex b/doc/exercises.tex index 73711f9..0dcab4b 100644 --- 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. -- cgit v1.2.3-70-g09d2