Slowest Decryption writeup (En)

This is mathematical derivation of 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})<n.

Then, the sum over $ (p_i)_{i=0}^{n-1}not satisfying condition (2.) will be$ \sum_{i=2}^{\left\lfloor(n-1)/k\right\rfloor}f(ki).

3.$ \gcd(p_0,p_1,\ldots,p_{n-1})\neq0

Using $ \gcd(p_0,p_1,\ldots,p_{n-1})=0\iff p_0=p_1=\cdots=p_{n-1}=0, the sum over $ (p_i)_{i=0}^{n-1} not satisfying condition (3.) will be$ \frac{n(n-1)}{2}a_0.

from the above, $ f(k)=\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}-\sum_{i=2}^{\left\lfloor(n-1)/k\right\rfloor}f(ki)-\frac{n(n-1)}{2}a_0.

Time Complexity

Calculating$ \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}is$ O\left(\log n+\frac{n}{k}\right)time.

With calculating $ f(k)in the order of$ k=n-1,\ldots,2,1,$ \sum_{i=2}^{\left\lfloor(n-1)/k\right\rfloor}f(ki)will be calculated in$ O\left(\frac{n}{k}\right)time.

Only Calculate$ \frac{n(n-1)}{2}a_0, in$ O(1)time.

Therefore, the answer will be calculated in$ O\left(\sum_{k=1}^{n-1}\left(\log n+\frac{n}{k}\right)\right)=O\left(n\log n\right)time complexity.

appendix; for speed junkie

with further optimization, it can be solved with$ O(n\log\log n)time. should we set the problem with$ n=2000000? lol