Recently I've been working a bit with modular arithmetic and big numbers. An incredibly useful tool for that is modular exponentiation by repeated squaring, implemented using power_mod function. Earlier I was using Julia for that (together with BigInt there), and I was quite disappointed to find out that in Sage modular exponentiation is noticably slower for (very) large moduli - slowdown by a factor of 3 modulo 10^5000 and by a factor of almost 10 modulo 10^50000 (I didn't test larger ones). I don't know if the reason for this is that Julia uses some faster modular exponentiation algorithm (I didn't manage to find how it is implemented), or whether it is because the BigInt makes it that significantly easier for CPU to work with these.
So my question is, is there some way to speed up the modular exponentiation in Sage?
