# Slowest Decryption writeup (En)This is mathematical derivation of [Slowest Decryption Solver Script](https://scrapbox.io/tsgctf2-writeup-naan/Slowest_Decryption_Solver_Script). Reading the program first may help your understanding.
## Problem StatementFor given$a_0,a_1,\ldots,a_{n-1}$, and for all$p_0,p_1,\ldots,p_{n-1}\in\{0,1,\ldots,n-1\}$, calculate sum of$\gcd(p_0,p_1,\ldots,p_{n-1})\sum_{i=0}^{n-1}ia_{p_i}$
## SubproblemConsider the problem summing $\sum_{i=0}^{n-1}ia_{p_i}$ in the same situation.There are$n^{n-1}$ possible $(p_i)_{i=0}^{n-1}$which satisfies $p_0=0$, and the same logic can apply to any$p_i=j$.Then, the answer will be$\frac{n^n(n-1)}{2}\sum_{i=0}^{n-1}a_i$.
## Main Problem$\gcd(p_0,p_1,\ldots,p_{n-1})=k\ (k=1,\ldots,n-1)$ means$k\,|\gcd(p_0,p_1,\ldots,p_{n-1})$ ($\gcd(p_0,p_1,\ldots,p_{n-1})$is a product of$k$) $\land$$\gcd(p_0,p_1,\ldots,p_{n-1})\neq mk\ (m\in\mathbb{N}_{>1})$ $\land$ $\gcd(p_0,p_1,\ldots,p_{n-1})\neq 0$.
We shall define $f(k)$ as a summation of$\sum_{i=0}^{n-1}ia_{p_i}$ over $(p_i)_{i=0}^{n-1}$ which satisfies $\gcd(p_0,p_1,\ldots,p_{n-1})=k$
### 1. $k\mid\gcd(p_0,p_1,\ldots,p_{n-1})$$k\mid\gcd(p_0,p_1,\ldots,p_{n-1})$ is $^\forall i=0,1,\ldots,n-1.\,k\mid p_i$.With the same logic as subproblem, we find the sum (over $(p_i)_{i=0}^{n-1}$ which satisfies condition (1.)) is $\left\lceil\frac{n}{k}\right\rceil^{n-1}\frac{n(n-1)}{2}\sum_{i=0}^{\left\lfloor(n-1)/k\right\rfloor}a_{ki}$.
### 2. $\gcd(p_0,p_1,\ldots,p_{n-1})\neq mk\ (m\in\mathbb{N}_{>1})$Since $^\forall i=0,1,\ldots,n-1.\gcd(p_0,p_1,\ldots,p_{n-1})\leq p_i$, $\gcd(p_0,p_1,\ldots,p_{n-1})