How do you test whether a number is a prime number? Trial division is in use since antiquity and is easy to understand. This is the process of dividing the number in question by each prime number that is smaller than it. If a smaller factor is found, then it is not a prime number (i.e. is a composite number). If no smaller factors can be found, then the number is a prime numbers. However numbers routinely used in encryption algorithms today have hundreds or even thousands of decimal digits. Factoring such large numbers is really a hard problem. If we just want to know whether a number is prime or not, the answer can be obtained very quickly. In this post we showcase a calculation that can be used for checking whether a whole number is prime or composite without actually finding any factor. This method is based on a theorem of Fermat and can be implemented using the fast powering algorithm.
___________________________________________________________________________
Examples
Example 1
The author of a recent article came across the following 204digit number that he incorrectly asserted as a prime number.
34526903293921580314641092817369674040684481568423
96721012992064214519445919256941544565276067662360
10874972724155570842527652727868776362959519620872
73561220060103650687168112461098659687818073890148
6527
It turns out that showing the number is composite is not difficult. The idea is what can be called the Fermat2 test: if is a prime number, then , meaning that is divisible by , or equivalently the remainder is 1 when is divided by . Using the fast powering algorithm, the exponentiation modulo is turned into a series of squarings and multiplying. The result is that where is the following 203digit number:
33345811005959530251539697392827903173946066773819
70645616725285996925661000056829272733579262095715
97827398131150054514508640724258354848985651127636
92970799269335402819507605691622173717318335512037
458
If were a prime number, then modulo is 1. But modulo is clearly not 1. Therefore must be composite. We do not show the steps that produce the 203digit number . In carrying out the squareandmultiply algorithm, there are 676 squarings and 327 multiplications. The process runs quickly when it is implemented on a computer. In the next example, we work a small example to illustrate how the fast powering algorithm works.
Example 2
Let’s do a smaller example to demonstrate the idea of the Fermat2 test and the calculation of the fast powering algorithm (also called the squareandmultiply algorithm). Consider the number 55289. Is it a prime number?
We show that . So 55289 is not a prime (otherwise would be 1 modulo 55289). To show , the first step is to express the exponent 55288 in its binary expansion.
Step 2 is to perform a series of 15 squarings (15 is the highest power of 2 in the binary expansion of the exponent 55288). Step 3 is to perform a series of multiplications. Both steps are shown in the following table.
Example 2 Results
The column for squaring starts with 2, the base of the exponentiation . Each number in that column is the square of the preceding number and is reduced modulo 55289. The numbers with asterisks refer to the positions that are 1s in the binary expansion of 55288. The third column shows the multiplications of the numbers with asterisks in the second column.
Example 3
Consider the following 309digit number:

RSA1024
13506641086599522334960321627880596993888147560566
70275244851438515265106048595338339402871505719094
41798207282164471551373680419703964191743046496589
27425623934102086438320211037295872576235850964311
05640735015081875106765946292055636855294752135008
52879416377328533906109750544334999811150056977236
890927563
This example is an RSA number called RSA1024. It is a 1024bit (309digit in decimal). It is a product of two prime numbers and thus is not a prime number. Indeed, where is RSA1024 and is the following number:
12093909443203361586765059535295699686754009846358
89512389028083675567339322020593385334853414711666
28419681241072885123739040710771394053528488357104
98409193003137847878952260296151232848795137981274
06300472693925500331497519103479951096634123177725
21248297950196643140069546889855131459759160570963
857373851
Clearly, RSA1024 does not pass the Fermat2 test and is thus a composite number. Yet RSA1024 has not yet been factored. It is not expected to be factored in decades to come barring a dramatic breakthrough in computing technology. This example points to the principle on which the RSA cryptosystem is based, that

It is relatively easy to decide whether or not a number is prime. But it is hard to find the prime factors of a given composite number.
In short, primality testing is easy while factoring is hard. In any case, the examples of RSA1024 and other RSA numbers are empirical evidence that factoring is a hard problem.
___________________________________________________________________________
Remarks
The Fermat2 test used here is based on Fermat’s Little Theorem, which is discussed in the next post.
___________________________________________________________________________
Pingback: A fast way to do modular exponentiation  All Math Considered
Pingback: Fermat’s Little Theorem as a primality testing  All Math Considered