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

Calculating (a power b) mod p
Автор devarshi09, история, 6 лет назад, По-английски

How to calculate (a power b) mod p correctly if b is exceeding long long integer limit in c++.

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

O(log2(b))?

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

Let b = b1b2.....bn(concatenated) By induction, Let x = a ^ (b1b2...bk) (mod p)

a ^ (b1b2....b(k+1)) = ( a^(b1b2....bk) ) ^ 10 * (a ^ b(k+1)) = x^10 * a^b(k+1)

now you can calculate modulo without overflow

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

first i need to store b. But b is exceeding the integer limit! How can i store b so that i correctly calculate (a power b) mod p. p is prime.

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

    If b is in the form of a string, then we can calculate with the following code:

    ll B = 0;
for (char c: b) {
    B = (10*B+(c-'0'))%(p-1);
}

    Now assuming that a is nonzero.

    EDIT: This is exactly what DongwonShin wrote above. If b is being calculated via a DP table, then you can just take all values mod p - 1 and there won't be overflow.

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

      got it. thanks!

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

      but why p-1?

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

        Fermat's theorem tells us that if (a, p) = 1. So we can take the power by the modulo.

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

          Thanks man!

          → Ответить
          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится +2 Проголосовать: не нравится

            In general if you have two co prime integers m and n, then m^p modulo n = m^(p%f(n)) modulo n, where f(n) is Euler totient function This.

            For any prime n, f(n)=n-1.So, the Fermat's theorem follows from this.

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

              I am using precomputed factorial and inverse factorial array to calculate b so should i use n-1 as the mod there also?

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

      What if b is being calculated through nCr using precomputed factorial and inverse modulo arrays?Then also we've to use same mod p-1 ?

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

        As long as your base(b) and p are co prime, I don't see why it can't be done. So, yes use same mod (p-1).

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

          I tried but then for example 11*(inv[11)) didn't turn out to be 1 when i used p-1 as mod but while using p as mod it did show 1. here inv[11] = power(11,mod-2,mod) where power is fast exponential function.

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

      What if b is calculated as a-c and c requires division operation?Then while using inverse modulo for division i should use which mod?I am confused.Please help.

      → Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Refer https://www.geeksforgeeks.org/find-abm-where-b-is-very-large/

→ Ответить