Repeated Squaring

For the primality test we need to compute $a^{X-1} \pmod X$. There are two problems with the straightforward method (multiplying $X-1$ copies of $a$ and reducing modulo $X$). First, the resulting number $a^{X-1}$ has exponentially many digits (nearly $2^n$ binary digits if $X$ has $n$ binary digits and $a=2$). The space requirement can be reduced to linear in the bit-length of the input by doing all operations modulo $X$. Second, an exponential number of modular multiplications is needed, namely $X-2 \approx 2^n$. We can reduce this number to $\approx n$ by ``repeated squaring'' - see the ``Pseudocodes for basic algorithms in Number Theory'' handout.