We often need to compute x^n, for large integers n, in many applications (e.g., modular arithmetic in cryptography, add
Posted: Thu May 05, 2022 1:20 pm
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.
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.