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

Автор Usu, история, 6 лет назад, По-английски

Hey! I have a question. If I have to calculate a pow b modulo mod, with b>mod, is it the same with a pow (b % (mod-1)?

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

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +42 Проголосовать: не нравится

By Euler's Theorem, if gcd(a, n) = 1, . If m happens to be a prime, then phi(m) = m - 1.

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

Even when gcd(a, n) > 1, the following holds: If b ≥ φ(m), . When m is large and you cannot efficiently factor it to compute φ(m) and b is given in decimal form, you can still use fast exponentiation. Process digits of b one by one starting from the most significant one and use a10b + c = (ab)10 × ac.