A tough challenge that requires Efficiency in Algorithms:

Given large numbers , , , compute . (This is a challenge in RSA Algorithm)

A (fast) method for solving:

Note it’s easy to compute if we’ve already computed

  • If n is even, take
  • if n is odd, take
    Thus this is a Recursive Algorithm solution.