Блог пользователя ZeyadKhattab

Help in A Number Theory Problem
Автор ZeyadKhattab, история, 5 лет назад, По-английски

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
  • Проголосовать: не нравится

»
5 лет назад, # |
← 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.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      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; 
}
      → Ответить
      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 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.

          → Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 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$$$.

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      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.
      → Ответить