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

A Hard Task?
Автор VIIIIIIVX, история, 8 лет назад, По-английски

Hi everyone!

Some days ago, I confronted to a hard problem and I could not solve it. Can you help me?

The problem was: Given a and n(1 <= a, n <= 1000). And b = (a ^ a) ^ (a ^ a). And return b mod n.

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

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

Auto comment: topic has been updated by VIIIIIIVX (previous revision, new revision, compare).

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

Use a^phi(n) is 1 mod n. Find a^a mod n, and a^a mod phi(n).

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

Incase a, n are co-prime, I guess this will work.

You can use Euler's Theorem for xy % n even when gcd(x, n) ≠ 1. This requires that the residue used in the exponentiation is equal or bigger than the highest power of the prime powers shared by x and n. So in such case, find y % φ(n) until the value is the smallest value greater or equal to the highest power of the prime factors shared by x and n.

Having said this, in above case the highest shared power is  ≤ 10. So calculations then can fit in long long.

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

A simple way is to compute the values 1, a, a2, a3, ... modulo n until you find a loop. Due to non-coprimeness issues, it may not end in 1, so it has the so-called ρ structure (a tail and a cycle). Still, we know the start of the cycle and its period, so we can reduce the exponent modulo this period.

So now we have to compute the exponent . This can be done straightforwardly or using fast exponentiation.

→ Ответить