VIIIIIIVX's blog

A Hard Task?
By VIIIIIIVX, history, 8 years ago, In English

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.

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

Comments Comments (7)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

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

    This is valid only if a and n are co — prime,and he has not mentioned so in the blog

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

      True that. If that's not true, then that's some real trouble. Maybe this helps in that case.

      → Reply
»
8 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply