An easy method for detecting composite numbers

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 204-digit number that he incorrectly asserted as a prime number.

    N=
    34526903293921580314641092817369674040684481568423
    96721012992064214519445919256941544565276067662360
    10874972724155570842527652727868776362959519620872
    73561220060103650687168112461098659687818073890148
    6527

It turns out that showing the number N is composite is not difficult. The idea is what can be called the Fermat-2 test: if N is a prime number, then 2^{N-1} \equiv 1 \ (\text{mod} \ N), meaning that 2^{N-1}-1 is divisible by N, or equivalently the remainder is 1 when 2^{N-1} is divided by N. Using the fast powering algorithm, the exponentiation 2^{N-1} modulo N is turned into a series of squarings and multiplying. The result is that 2^{N-1} \equiv W \ (\text{mod} \ N) where W is the following 203-digit number:

    W=
    33345811005959530251539697392827903173946066773819
    70645616725285996925661000056829272733579262095715
    97827398131150054514508640724258354848985651127636
    92970799269335402819507605691622173717318335512037
    458

If N were a prime number, then 2^{N-1} modulo N is 1. But 2^{N-1} modulo N is clearly not 1. Therefore N must be composite. We do not show the steps that produce the 203-digit number W. In carrying out the square-and-multiply 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 Fermat-2 test and the calculation of the fast powering algorithm (also called the square-and-multiply algorithm). Consider the number 55289. Is it a prime number?

We show that 2^{55288} \equiv 8349 \ (\text{mod} \ 55289). So 55289 is not a prime (otherwise 2^{55288} would be 1 modulo 55289). To show 2^{55288} \ (\text{mod} \ 55289), the first step is to express the exponent 55288 in its binary expansion.

    55288=2^3+2^4+2^5+2^6+2^7+2^8+2^9+2^{10}+2^{12}+2^{14}+2^{15}

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

\left[\begin{array}{rrrrr}      i & \text{ } & \text{Squaring} & \text{ } & \text{Multiplying} \\      \text{ } & \text{ } \\      0 & \text{ } & 2 & \text{ } & \text{ } \\      1  & \text{ } & 4 & \text{ } & \text{ } \\      2  & \text{ } & 16 & \text{ } & \text{ } \\      3  & \text{ } & 256* & \text{ } & 256 \\      4  & \text{ } & 10247* & \text{ } & 24649 \\      5  & \text{ } & 7198* & \text{ } & 1101 \\      6  & \text{ } & 5411* & \text{ } & 41588 \\      7  & \text{ } & 31040* & \text{ } & 3948 \\      8  & \text{ } & 15486* & \text{ } & 44383 \\      9  & \text{ } & 27803* & \text{ } & 40647 \\      10  & \text{ } & 11300* & \text{ } & 25377 \\      11  & \text{ } & 27699 & \text{ } & \text{ } \\      12  & \text{ } & 44437* & \text{ } & 3305 \\      13  & \text{ } & 334 & \text{ } & \text{ } \\      14  & \text{ } & 978* & \text{ } & 25528 \\      15  & \text{ } & 16571* & \text{ } & 8349      \end{array}\right]

The column for squaring starts with 2, the base of the exponentiation 2^{55288}. 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 309-digit number:

    RSA-1024
    13506641086599522334960321627880596993888147560566
    70275244851438515265106048595338339402871505719094
    41798207282164471551373680419703964191743046496589
    27425623934102086438320211037295872576235850964311
    05640735015081875106765946292055636855294752135008
    52879416377328533906109750544334999811150056977236
    890927563

This example is an RSA number called RSA-1024. It is a 1024-bit (309-digit in decimal). It is a product of two prime numbers and thus is not a prime number. Indeed, 2^{N-1} \equiv T \ (\text{mod} \ N) where N is RSA-1024 and T is the following number:

    T=
    12093909443203361586765059535295699686754009846358
    89512389028083675567339322020593385334853414711666
    28419681241072885123739040710771394053528488357104
    98409193003137847878952260296151232848795137981274
    06300472693925500331497519103479951096634123177725
    21248297950196643140069546889855131459759160570963
    857373851

Clearly, RSA-1024 does not pass the Fermat-2 test and is thus a composite number. Yet RSA-1024 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 RSA-1024 and other RSA numbers are empirical evidence that factoring is a hard problem.

___________________________________________________________________________

Remarks

The Fermat-2 test used here is based on Fermat’s Little Theorem, which is discussed in the next post.

___________________________________________________________________________
\copyright \ 2015 \text{ by Dan Ma}

Advertisements

A fast way to do modular exponentiation

In number theory and in cryptography, it is often necessary to raise a number a to a number e modulo another number N (the number e here stands for exponent and is not to be confused with the natural log constant). In this post we explain an algorithm that can do such exponentiation efficiently. This algorithm goes by many names. Some of the common ones are fast powering algorithm, fast modular exponentiation, and square and multiply.

The next post shows how the fast powering algorithm is used in the context of primality testing (i.e. checking whether or not a number is prime).

The usual notation for raising a number a to a number e modulo another number N is a^{e} \ (\text{mod} \ N). The answer to this exponentiation is in effect the remainder obtained by dividing the number a^e by N. For example the answer of 2^{6} \ (\text{mod} \ 11) is 9. When 2^6= 64 is divided by 11, the remainder is 9. We use the notation 2^{6} \equiv 9 \ (\text{mod} \ 11) to express this result. In cryptography, the exponent e and the modulo N are large numbers with hundreds or even thousands of decimal digits. For example, it can be verified that c^{d} \equiv m \ (\text{mod} \ N) where

    N=
    11438162575788886766923577997614661201021829672124
    23625625618429357069352457338978305971235639587050
    58989075147599290026879543541

    c=
    96869613754622061477140922254355882905759991124574
    31987469512093081629822514570835693147662288398962
    8013391990551829945157815154

    d=
    10669861436857802444286877132892015478070990663393
    78628012262244966310631259117744708733401685974623
    06553968544513277109053606095

    m=
    20080500130107090300231518041900011805001917210501
    1309190800151919090618010705

The modulus N is a 129-digit number that is used as the modulus of a factoring challenge problem called RSA-129 challenge. The challenge was to factor the number N into its prime factors. Knowing the prime factors of the modulus N means that any message encrypted using that modulus will no longer be secure. The 129-digit N was factored in 1994. So the RSA encryption scheme using any modulus similarly in size is not secure. So the calculation as shown above is actually considered a toy problem, though a more realistic one. The fast powering algorithm (or square-and-multiply algorithm) discussed here can be used to calculate c^{d} \equiv m \ (\text{mod} \ N).

___________________________________________________________________________

Examples

Example 1
To illustrate how fast powering works, we start with a small example. We perform 3^{23} (\text{mod} \ 29). In the fast powering approach, we do not need to raise 3 to 23. Instead, we first find the binary expansion of the exponent 23 to transform the computation of 3^{23} into a series of squarings and multiplications. To this end, we write 23 as a sum of powers of two as follows:

    23=2^0+2^1+2^2+2^{4}

Next we compute 3^{2^0},3^{2^1},3^{2^2},3^{2^3},3^{2^{4}} modulo 29. Note that each term is the square of the preceding term, hence the word square in the name “square-and-multiply”. The following shows the squarings, all modulo 29:

    \displaystyle \begin{aligned} &3^{2^0} \equiv 3 \ * \\&3^{2^1} \equiv 9 \ * \\&3^{2^2} \equiv 9^2 \equiv 23  \ * \\&3^{2^3} \equiv 23^2 \equiv 7 \\&2^{2^{4}} \equiv 7^2 \equiv 20 \ * \end{aligned}

Note that the squarings marked by * are the powers of 2 in the binary expansion of 23. In the above series of squarings, there are 4 multiplications and 4 divisions for the reduction modulo 29. The next step is to multiply the numbers with *. After each multiplication, reduce modulo 29.

    \displaystyle \begin{aligned} 3^{23} &\equiv 3 \cdot 9 \cdot 23 \cdot 20  \\&\equiv 27 \cdot 23 \cdot 20 \\&\equiv 12 \cdot 20 \\&\equiv 8 \ \text{mod} \ 29  \end{aligned}

Thus the answer is 3^{23} \equiv 8 \ (\text{mod} \ 29). To simplify the presentation of the calculation, we use a table such as the one below. The middle column shows the squarings. The asterisks in the squaring column indicate that the results come from the powers of 2 in the binary expansion of the exponent, meaning that these will be the numbers to be multiplied in the third column.

Example 1 Results

\left[\begin{array}{lllll}      i & \text{ } & \text{Squaring} & \text{ } & \text{Multiplying} \\      \text{ } & \text{ } \\      0 & \text{ } & 3* & \text{ } & 3 \\      1  & \text{ } & 9* & \text{ } & 27 \\      2  & \text{ } & 23* & \text{ } & 12 \\      3  & \text{ } & 7 & \text{ } & \text{ } \\      4  & \text{ } & 20* & \text{ } & 8          \end{array}\right]

Example 2
Verify the following

    30120^{17} \equiv 23877 \ (\text{mod} \ 44197)

    23877^{41201} \equiv 30120 \ (\text{mod} \ 44197)

This is a toy example of RSA encryption (the first calculation) and decryption (the second). The modulus N= 44197 and the first exponent 17 are the public key. The first exponentiation turns the message 30120 into the ciphertext 23877. The second exponentiation converts the ciphertext back into the original message. We demonstrate how to do the decryption (the second calculation). First express the exponent 41201 into its binary expansion.

    41201=2^0+2^4+2^5+2^{6}+2^{7}+2^{13}+2^{15}

The following table shows the squarings and multiplications.

Example 2 Results

\left[\begin{array}{lllll}      i & \text{ } & \text{Squaring} & \text{ } & \text{Multiplying} \\      \text{ } & \text{ } \\      0 & \text{ } & 23877* & \text{ } & 23877 \\      1  & \text{ } & 14026 & \text{ } & \text{ } \\      2  & \text{ } & 7829 & \text{ } & \text{ } \\      3  & \text{ } & 36199 & \text{ } & \text{ } \\      4  & \text{ } & 14945* & \text{ } & 39384 \\      5  & \text{ } & 25584* & \text{ } & 41247 \\      6  & \text{ } & 27683* & \text{ } & 11206 \\      7  & \text{ } & 16706* & \text{ } & 33141 \\      8  & \text{ } & 30578 & \text{ } & \text{ } \\      9  & \text{ } & 26549 & \text{ } & \text{ } \\      10  & \text{ } & 39842 & \text{ } & \text{ } \\      11  & \text{ } & 5512 & \text{ } & \text{ } \\      12  & \text{ } & 18805 & \text{ } & \text{ } \\      13  & \text{ } & 7828* & \text{ } & 35555 \\      14  & \text{ } & 20542 & \text{ } & \text{ } \\      15  & \text{ } & 25005* & \text{ } & 30120      \end{array}\right]

The modulus in this example is small enough so that all the reduction modulo N can be done by a hand-held calculator. For example, take the first squaring. The square 23877^2 divided by 44197 leads to the quotient 12899. Then 23877^2-12899 \cdot 44197 produces the remainder 14026. For a larger modulus N, use a calculator or software that can handle multiplication and divisions of larger numbers.

Example 3
This is a slightly larger example that is similar to Example 2. Verify the following

    230914^{17} \equiv 347965 \ (\text{mod} \ 497347)

    347965^{204209} \equiv 230914 \ (\text{mod} \ 497347)

We perform the second exponentiation. The following is the binary expansion of the exponent 204209.

    204209=2^0+2^4+2^5+2^{7}+2^{8}+2^{10}+2^{11}+2^{12}+2^{16}+2^{17}

The following table shows the squarings and multiplications.

Example 3 Results

\left[\begin{array}{lllll}      i & \text{ } & \text{Squaring} & \text{ } & \text{Multiplying} \\      \text{ } & \text{ } \\      0 & \text{ } & 347965* & \text{ } & 347965 \\      1  & \text{ } & 16728 & \text{ } & \text{ } \\      2  & \text{ } & 316970 & \text{ } & \text{ } \\      3  & \text{ } & 416083 & \text{ } & \text{ } \\      4  & \text{ } & 64230* & \text{ } & 12464 \\      5  & \text{ } & 496882* & \text{ } & 172404 \\      6  & \text{ } & 216225 & \text{ } & \text{ } \\      7  & \text{ } & 145890* & \text{ } & 187076 \\      8  & \text{ } & 424582* & \text{ } & 299597 \\      9  & \text{ } & 486410 & \text{ } & \text{ } \\      10  & \text{ } & 254689* & \text{ } & 88899 \\      11  & \text{ } & 4246* & \text{ } & 476128 \\      12  & \text{ } & 124024* & \text{ } & 295068 \\      13  & \text{ } & 4560 & \text{ } & \text{ } \\      14  & \text{ } & 402373 & \text{ } & \text{ } \\      15  & \text{ } & 175484 & \text{ } & \text{ } \\      16  & \text{ } & 400057* & \text{ } & 200467 \\      17  & \text{ } & 333343* & \text{ } & 230914 \\    \end{array}\right]

Example 4
This is the RSA-129 challenge problem mentioned earlier. We do not perform the calculation here. The discussion in the running time section below shows that this example requires at most 258 multiplications even though this example is so much larger than the other three examples. The RSA-129 challenge problem is also discussed in another blog authored by the author of this blog.

___________________________________________________________________________

Steps in the algorithm

To summarize, there are three steps in carry out the fast exponentiation for a^{e} \ (\text{mod} \ N). They are:

  1. Find the binary expansion of the exponent e.
  2. Perform the series of squarings a^{2^0}, a^{2^1}, a^{2^2}, \cdots up to the highest power of 2 in the binary expansion of the exponent. The result of each squaring is immediately reduced modulo N.
  3. Multiply the results of the squarings that correspond to the powers of 2 in the binary expansion of the exponent e. The result of each multiplication is immediately reduced modulo N. The last multiplication result is the answer to the modular exponentiation.

Note that the squarings in the second step are shown in the second column in the above tables. The multiplications are performed in the third column but only for the rows that are the powers of 2 in the binary expansion of the exponent (the rows with *).

___________________________________________________________________________

Running time

Let’s look at the running time of the fast powering algorithm. Suppose that k is the highest power of 2 in the exponent E in the exponentiation a^{E} \ (\text{mod} \ N). So we have:

    \displaystyle 2^k \le E \le 2^{k+1}-1

The above inequality means that the exponent E is a k+1-bit number. The above three examples demonstrate that the squaring step requires exactly k multiplications and that the multiply step requires at most k multiplications. Overall, the algorithm requires at most 2k many multiplications and the same number of divisions to reduce modulo N. Since 2^k \le E, by taking natural log of both sides we have:

    \displaystyle k \le \frac{\text{log}(E)}{\text{log}(2)}

    \displaystyle 2k \le 2 \ \frac{\text{log}(E)}{\text{log}(2)}

This means that the algorithm takes at most \displaystyle 2 \ \frac{\text{log}(E)}{\text{log}(2)} multiplications. In particular, if E is roughly 2^n in size, then the fast powering algorithm requires at most \displaystyle 2 \ \frac{\text{log}(2^{n})}{\text{log}(2)}=2n multiplications. For example, the exponent in Example 4 is roughly 2^{129} in size. Thus the fast powering algorithm will take at most 258 multiplications for that example. Another example is when the exponent E is a 1024-bit number (309 decimal digits) and is thus roughly 2^{1024}. Then the algorithm requires at most 2048 multiplications. Thus the fast powering algorithm is fast and efficient.

The next post shows how the fast powering algorithm is used in the context of primality testing (i.e. checking whether or not a number is prime).

___________________________________________________________________________
\copyright \ 2015 \text{ by Dan Ma}