Tags: ppc
Rating:
# 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 Statement
For 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}$
## Subproblem
Consider 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})
