We often need to compute x^n, for large integers n, in many applications (e.g., modular arithmetic in cryptography, add

[answerhappygod]

We often need to compute x^n, for large integers
n, in many applications (e.g., modular arithmetic in
cryptography, additive semigroups like elliptic curves, powering of
matrices, shortest path computations in large graphs); the
simplistic O(n) algorithm of repeated multiplications is slow.
Design a logarithmic algorithm (that needs only log n
multiplications) for exponentiation where n is a positive integer.
You need to prove your claim.