Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

ZeyadKhattab's blog

Help in A Number Theory Problem
By ZeyadKhattab, history, 7 years ago, In English

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.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
7 years ago, hide # |
← Rev. 3  
Vote: I like it +11 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    Thank you for your answer, however, I want to ask 2 questions:

    1. How did you arrive at the formula that flag = $$$c^{{1}/{2^{30}+3}}$$$

    2. How can we using fast exponentiation here? the value of c*c will overflow 64 bits?

    → Reply
    • »
      »
      »
      7 years ago, hide # ^ |
       
      Vote: I like it +3 Vote: I do not like it
      1. We just raise both sides of $$$FLAG^{2^{30} + 3} = c$$$ to the power of $$$\frac{1}{2^{30} + 3}$$$
      2. 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; 
}
      → Reply
      • »
        »
        »
        »
        7 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        Why did we find the inverse of 2^30 +3 mod (p-1) * (q-1) in particular and not mod n for example ?

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          $$$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.

          → Reply
  • »
    »
    7 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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$$$.

    → Reply
    • »
      »
      »
      7 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it
      1. 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)$$$.
      2. 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.
      → Reply