how to run fermat test on large numbers

Question

fermat test is a primality test, says that:

if $a^{N-1} \equiv 1\mod N$,

then N in is probably prime, but I have searched for any program that allows me to run this test on large numbers (about 1 million digits), and I have found no programs that can deal with these large numbers, so:

could any body tell me what to do ? and I am sorry if this question is duplicated.

Note that the factories of $N-1$ are known.

Answer 1

Write a simple C program using gmp (link) for manipulating large integers. This is a well-maintained library for these kind of operations. Of course get a C-compiler too (there are many free ones), using Linux is the easiest option, and get enough RAM for your PC. gmp already has a pseudo-prime test as a library function that does more than just Fermat tests.

Answer 2

You need to combine exponentiation by squaring with multiplication using Fast Fourier Transform. The first of these is relatively easy to implement; the second is difficult. But without FFT multiplication your program will be impossibly slow.