By ZeyadKhattab, history, 14 months ago,

I would appreciate it if someone explains the solution for 102055K - Mr. Panda and Kakin

I tried reading AC solutions, but I could not understand them.

• +4

 » 14 months ago, # | ← Rev. 3 →   +11 You know that $a^{(p - 1)(q - 1)} \equiv 1$ $mod$ $pq$, from Euler's Theorem. You can now get modular inverse of $(2^{30} + 3)$ $mod$ $(p - 1)(q - 1)$ using extended gcd algorithm. Calculate $c^{\frac{1}{2^{30} + 3}} = FLAG$, using fast exponential.
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 Thank you for your answer, however, I want to ask 2 questions: How did you arrive at the formula that flag = $c^{{1}/{2^{30}+3}}$ How can we using fast exponentiation here? the value of c*c will overflow 64 bits?
•  » » » 14 months ago, # ^ |   +3 We just raise both sides of $FLAG^{2^{30} + 3} = c$ to the power of $\frac{1}{2^{30} + 3}$ This part is tricky, we can calculate $x*x$ $mod$ $m$ where $m^2$ overflows at 64bits in $O(logx)$ time in a simillar way we do fast exponential, but adding numbers instead of multiplying them, or do it in $O(1)$ time using this function that i don't really know how is working: long long mul(long long a, long long b, long long mod) { return (a * b - (long long)((long double) a * b / mod) * mod + mod) % mod; } 
•  » » » » 14 months ago, # ^ |   0 Why did we find the inverse of 2^30 +3 mod (p-1) * (q-1) in particular and not mod n for example ?
•  » » » » » 14 months ago, # ^ |   0 $a^b$ $mod$ $n \equiv a^{b \; mod \; \varphi(n)}$ $mod$ $n$, from the Euler's Theorem, as $a^{\varphi(n)} \equiv 1$ $mod$ $n$, we can substract multiples of $\varphi(n)$ from the exponent.
•  » » 14 months ago, # ^ |   0 Can you please provide details for the following subroutines used in your approach: $1. \,$ Proof for $a^{(p - 1)(q - 1)} \equiv 1 \,mod \,pq$ given that $a$, $p$ are coprime and $a$, $q$ are coprime from $a^{\phi(n)} \equiv 1 \,mod \,n$ (where $a$ and $n$ are coprime) $i.e.$ from Euler's Theorem. $2.$ If $b^{-1}\,mod\,n$ is known then how to evaluate $a^{\frac{1}{b}} \,mod\,n$.
•  » » » 14 months ago, # ^ | ← Rev. 2 →   0 We know, that $n = pq$, and can calculate them easily — we just iterate from $\sqrt{n}$ down and find the largest number that divides $n$ — it's $p$. Euler Theorem: $a^{\varphi(n)} \equiv 1$ $mod$ $n$. $\varphi(p) = p - 1$ and the function is multiplicative, so $\varphi(n) = (p - 1)(q - 1)$. Actually, we can't. If we want to calculate $a^{\frac{1}{b}}$ $mod$ $n$, we need to know value of $\frac{1}{b}$ $mod$ $\varphi(n)$, again, from the Euler's Theorem, if we know it, we can safely raise $a$ to it's power.