the number one optimization for fast primality testing: Montgomery multiplication. It forms the basis of fast practical modular exponentiation implementations. - HN

Montgomery modular multiplication relies on a special representation of numbers called Montgomery form. The algorithm uses the Montgomery forms of a and b to efficiently compute the Montgomery form of ab mod N.