I took a crypto class at the University of Minnesota. We covered a neat algorithm that can be found here. If I remember correctly, it's O(log(n)). You should be able to extend it to use Math::BigInt objects should you desire.

thor