Ignore this.
I now have some appropriate reading material (Chapter 14 of Handbook of Applied Cryptography (HAC)).
"Efficient Implementation" detailing how to do powmod, mulmod, Chinese-Remainder-Theorem and GCD quickly.
That covers over 99% of the code that a siever performs. Woo.