Fermat's theorem as primality tester when powers are too large

Question

As part of cryptography, if I wish to test whether a given number is probably prime I use the formula:

$$ a^{p-1} \equiv 1 \bmod p $$

where $p$ is (potentially) a prime number.

However, when it comes to testing a number such as 2341, i.e. $$2^{2341} \mod 2342$$ ... the numbers are two big for a calculator. I'm required as part of a course to generate a random 9 digit number and test for primality using the formula above.

Can I use congruence to reduce the numbers involved without invalidating the test?

Not sure how since shrinking the powers I'm shrinking the RHS of the equation and therefore testing another number completely for primality.

A better (stricter) test is for whether $p$ is a strong pseudo-prime, and this takes about the same time as the pseudo-prime test you describe when implemented as @Element118 suggests below. See the Prime Pages note on strong probable-primality for additional details. — hardmath, Jan 02 '16 at 14:19

score 2 · Accepted Answer · answered Jan 02 '16 at 14:09

The short answer is yes.

This reduces to the problem of finding $a^b\pmod c$, for arbitrary nonnegative integers $a, b, c$, which can be done by Exponentiation by squaring.

If $b$ is even, we have $a^b=a^{2\times\frac{b}{2}}=\left(a^2\right)^\frac{b}{2}$.

If $b$ is odd, we have $a^b=a\times a^{b-1}=a\times\left(a^2\right)^\frac{b-1}{2}$

Since if $a\equiv a'\pmod c$ we have $a^b\equiv a'^b\pmod c$, we can reduce the base of the exponentiation $\pmod c$. As the power goes down by half, the algorithm will terminate in $O(\log b)$ steps.

Fermat's theorem as primality tester when powers are too large

1 Answers1