# The magic words are squeamish ossifrage

The title of the blog post is the answer to a decryption challenge problem in connection to a factoring problem of a 129-digit number that is known as RSA-129. The challenge problem was posed in 1977. Our goal here is to use this challenge problem to demonstrate how to encrypt and decrypt in the RSA algorithm. The author of this blog recently built a calculator that can handle modular exponentiation involving large numbers. The challenge problem of RSA-129 provides an opportunity to verify the calculator.

In the August 1977, Martin Gardner wrote an article called “A new kind of cipher that would take millions of years to break” in his Mathematical Games column in Scientific American. This article posed a challenge problem created by the inventors of the RSA cryptosystem. Here’s the gist of the problem.

An English sentence is converted into a number according to the rule that maps A to 01, B to 02, C to 03, . . . ,Y to 25, Z to 26, with 00 representing a space between words. Call the resulting number $m$. Then raise $m$ to $e=$ 9007 and then reduce the exponentiation result modulo the following 129-digit number $N$.

$N=$
11438162575788886766923577997614661201021829672124
23625625618429357069352457338978305971235639587050
58989075147599290026879543541

In modular arithmetic, the notation for this calculation is $m^{9007} \equiv c \ (\text{mod} \ N)$, where $c$ is the following number:

$c=$
96869613754622061477140922254355882905759991124574
31987469512093081629822514570835693147662288398962
8013391990551829945157815154

The number $c$ is the ciphertext. What is the plaintext $m$? What is English phrase that is behind $m$?

During the 17 years after the publication of the challenge problem, no one other than the creators of the problem knew the English phrase. In 1994, a team led by Atkins, Graff, Lenstra and Leyland [1] cracked the code and found that the answer is the title of this blog post. The effort that led to the answer was a massive computing project that was distributed over the Internet. Their goal was to factor the 129-digit number $N$ (the modulus) into the two prime factors $p$ and $q$. A more detailed description of the problem can also be found in a piece from MAA (see here).

Once the factors of the modulus are known, the decryption exponent $d$ was calculated using the extended Euclidean algorithm. Then raise the ciphertext $c$ to $d$ and reduce modulo $N$. The result is the plaintext $m$. Using the predetermined rule described earlier, the plaintext $m$ is translated back to the original English phrase. In the remainder of this post, we demonstrate how this process works with the prime factors $p$ and $q$ as a given.

The modulus $N$ is a 129-digit number that is known as RSA-129. It is the product of two prime numbers with 64 and 65 digits. Instead of taking millions of years to factor this modulus as suggested in the title of Martin Gardner’s article, it took a mere 17 years! In 1977, Rivest, one of the creators of the RSA algorithm, estimated that factoring a 125-digit number that is a product of two 63-digit prime numbers would require at least 40 quadrillion years using the best factoring algorithm available. This goes to show that what was considered hard or impossible at one point in time may one day become doable or even easy due to advances in computer power and factoring algorithms. What is considered a secure RSA modulus today (say 1024-bit) may be breakable in the future.

___________________________________________________________________

Decrypting the challenge message

The modulus $N$ as indicated above is a 129-digit number that is known as RSA-129. The number pair $N$ and $e=$ 9007 is an RSA public key. With only the knowledge of public key represented by $N$ and $e$ and the ciphertext $c$, how hard is it to recover the plaintext $m$? An answer emerged only after 17 years of the publication of the challenge. In this post, we demonstrate how to retrieve the plaintext from the ciphertext by using the prime factors $p$ and $q$ of the modulus $N$. Here’s are the factors $p$ and $q$ (found here):

$p=$
3490529510847650949147849619903898133417764638493387843990820577

$q=$
32769132993266709549961988190834461413177642967992942539798288533

As mentioned earlier, we take the prime factors $p$ and $q$ of $N$ as a given. Then compute the product of $p-1$ and $q-1$:

$\phi(N)=(p-1) \times (q-1)$

The function $\phi$ is important one in number theory and goes by a special name, Euler’s phi function. Then the decryption exponent $d$ is the number satisfying the following congruence relationship:

$ed \equiv 1 \ (\text{mod} \ \phi(N))$

where $e=9007$. In other words, the number $d$ is the multiplicative inverse of $e$ modulo $\phi(N)$. The typical approach in finding $d$ is to use the extended Euclidean algorithm. Once $d$ is found, the following modular exponentiation is computed:

$c^d \equiv m \ (\text{mod} \ N)$

We use the predetermined rule to recover the original English phrase. The steps are summarized as follows:

1. Using the Euclidean algorithm to compute $\text{GCD}(e,\phi(N))$, the greatest common divisor (GCD) of $E$ and $\phi(N)=(p-1) \times (q-1)$.
2. The GCD in the previous step should be 1. Performing Euclidean algorithm is so that we can work backward (the extended Euclidean algorithm) to compute $d=e^{-1}$ modulo $\phi(N)$.
3. Use the fast powering algorithm to compute $c^d \equiv m \ (\text{mod} \ N)$.
4. Use the predetermined mapping scheme to obtain the plaintext.

___________________________________________________________________

Step 1. Euclidean algorithm

The following is the product of $p-1$ and $q-1$.

$\phi(N)=$
11438162575788886766923577997614661201021829672124
23625625618428994472727416195373314872857532203455
12393667541112959643090434432

Next, use Euclidean algorithm to find $\text{GCD}(9007,N)$, which should be 1. The point is that we will work backward to find the multiplicative inverse of $e=$ 9007. The Euclidean algorithm consists of a series of divisions until reaching the GCD. The divisions are shown in the following matrix:

$\left[\begin{array}{rrrrrrrr} \phi(N) & = & 9007 & \times & T & + & 5166 & \text{ }\\ 9007 & = & 5166 & \times & 1 & + & 3841 & \text{ } \\ 5166 & = & 3841 & \times & 1 & + & 1325 & \text{ } \\ 3841 & = & 1325 & \times & 2 & + & 1191 & \text{ } \\ 1325 & = & 1191 & \times & 1 & + & 134 & \text{ } \\ 1191 & = & 134 & \times & 8 & + & 119 & \text{ } \\ 134 & = & 119 & \times & 1 & + & 15 & \text{ } \\ 119 & = & 15 & \times & 7 & + & 14 & \text{ } \\ 15 & = & 14 & \times & 1 & + & 1 & \text{*} \\ 14 & = & 1 & \times & 14 & + & 0 & \text{ } \end{array}\right]$

where $T$ is the following number:

$T=$
12699192379026187151019849003680094594228743945957
85084518284033523340432348390555473379435474856728
2379667762974681874441038

The last column in the above table shows the remainders in the divisions. The last non-zero remainder (marked by *) is the GCD of 9007 and $\phi(N)$, in this case 1. Next, we apply extended Euclidean algorithm to solve the following equation:

$9007 \times x + \phi(N) \times y = 1$

The solution $x$ will be the decryption exponent $d$.
___________________________________________________________________

Step 2. Extended Euclidean algorithm

The extended Euclidean algorithm is to take the above table of divisions and perform back substitutions. The process of doing back substitutions is logically clear but can be tedious. We use a tabular formulation of this process as shown below.

$\left[\begin{array}{rrrrrrrrr} \text{divisor} & \text{ } & \text{quotient} & \text{ } & \text{back substitution} & \text{ } & \text{sign} & \text{ }\\ \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ }\\ \phi(N) & \text{ } & \text{ } & \text{ } & W & \text{ } & - & \text{ } & \text{Step 9}\\ 9007 & \text{ } & T & \text{ } & 605 & \text{ } & + & \text{ } & \text{Step 8}\\ 5166 & \text{ } & 1 & \text{ } & 347 & \text{ } & - & \text{ } & \text{Step 7}\\ 3841 & \text{ } & 1 & \text{ } & 258 & \text{ } & + & \text{ } & \text{Step 6}\\ 1325 & \text{ } & 2 & \text{ } & 89 & \text{ } & - & \text{ } & \text{Step 5}\\ 1191 & \text{ } & 1 & \text{ } & 80 & \text{ } & + & \text{ } & \text{Step 4}\\ 134 & \text{ } & 8 & \text{ } & 9 & \text{ } & - & \text{ } & \text{Step 3}\\ 119 & \text{ } & 1 & \text{ } & 8 & \text{ } & + & \text{ } & \text{Step 2}\\ 15 & \text{ } & 7 & \text{ } & 1 & \text{ } & - & \text{ } & \text{Step 1} \\ \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ }\\ 14 & \text{ } & 1 & \text{ } & \bold 1 & \text{ } & + & \text{ }\\ 1 & \text{ } & 14 & \text{ } & \bold 0 & \text{ } & - & \text{ } \end{array}\right]$

where $W$ is the following number:

$W=$
76830113893108432263670086472264572295083900873044
99761335618402816209615707762860613945584622883205
839698996599682534036828337

Let’s explain the table for the back substitution. The first number in the first column is $\phi(N)$. The rest of the numbers in the first column are the divisors in the Euclidean algorithm. Note that the bottom number is always the GCD. The second column consists of the quotients in the Euclidean algorithm. The third column is where the back substitution takes place. It works from bottom up. At the bottom of the third column, the numbers are always 0 and 1 (in bold). To make it clear to see, there is blank row separating the bottom two rows from the rows above. The fourth column has the signs of the back substitution numbers. Starting with minus at the bottom, the signs are alternating: minus, plus, minus, plus etc (going from bottom to top).

We now demonstrate the calculation for the back substitution. The following shows the calculation for the rows labeled Step 1, Step 2, Step 3 and Step 9:

$1=1 \times 1 + 14 \times 0$ (Step 1)

$1=7 \times 1 + 1 \times 1$ (Step 2)

$1=1 \times 8 + 7 \times 1$ (Step 3)

$W=T \times 605 + 1 \times 347$ (Step 9)

The idea is that each number is the sum of the cross multiplications of the two rows below. This recurrence relation is a more efficient way of performing extended Euclidean algorithm.

The first two rows of the above table give the solution to the equation $9007 \times x + \phi(N) \times y = 1$. In the first two rows, cross multiply the divisor and back substitution columns (along with the sign) as follows:

$9007 \times (-W) + \phi(N) \times 605 = 1$

Then $-W$ is the solution to $ed \equiv 1 \ (\text{mod} \ \phi(N))$. We need $d$ to be positive. To find $d$, simply add $\phi(N)$ to $-W$. Thus $d$ is the least positive integer such that $-W \equiv d \ (\text{mod} \ \phi(N))$ where

$d=$
10669861436857802444286877132892015478070990663393
78628012262244966310631259117744708733401685974623
06553968544513277109053606095

One additional comment about the above table. When you cross multiply divisor column and back substitution column for any two rows, the result is the GCD. In particular, when this is done on the first two rows, we solve the equation $9007 \times x + \phi(N) \times y = 1$ and find the multiplicative inverse of $e$ as a result.

___________________________________________________________________

Step 3 and Step 4. Decipher

With the decryption key $d$ solved in the above step, we are now ready to calculate the following modular exponentiation:

$c^d \equiv m \ (\text{mod} \ N)$

The standard approach is to use the fast powering algorithm. The idea is to use the binary expansion of the exponent $d$ to convert the exponentiation $c^d$ into a series of squarings and multiplications. The exponent $d$ is a 426-bit numbers, which means that the fast powering algorithm only requires 425 squarings and at most 425 multiplications. The algorithm is fast and efficient since it runs in polynomial time. Our calculator produces the following result:

$m=$
20080500130107090300231518041900011805001917210501
1309190800151919090618010705

Using the predetermined mapping of A = 01, B = 02 (and so on), the numeric plaintext is converted to the following English phrase:

the magic words are squeamish ossifrage

which is the title of this blog post.

___________________________________________________________________

Remark

The above demonstration shows how to derive the decryption key $d$ from the knowledge of the two prime factors $p$ and $q$ of the modulus $N$. Thus the prime factors $p$ and $q$ should be kept secret. Of course, the decryption key $d$ should also be kept secret so that the originator/creator of the public key is the only one who can read the encrypted messages sent to him or her.

___________________________________________________________________

Exercise

Suppose the public key $N$ and $e$ is as above. Verify that encrypting the plaintext $m$ will derive the ciphertext $c$ given in the challenge problem. The plaintext $m$ is repeated below.

$m=$
20080500130107090300231518041900011805001917210501
1309190800151919090618010705

___________________________________________________________________

Reference

1. Atkins D., Graff M., Lenstra, A. K. Lenstra, Leyland P. C., The magic words are squeamish ossifrage, ASIACRYPT-94, Lecture Notes Comput. Sci. Volume 917, Springer-Verlag, Berlin, 1995.

___________________________________________________________________
$\copyright \ \ 2014 \ \text{Dan Ma}$

# A primality testing exercise from RSA-100

In this post, we work on a primality testing exercise obtained by altering one digit of a known large prime number. The idea is that we take a known large prime number, change one of the digits and test the primality of the resulting number. In this post, we use the smaller prime factor of the number that is known as RSA-100. The goal is to keep changing digits (one at a time) until we obtain a prime number.

RSA-100 is the smallest RSA number. It is a 330-bit number (has 100 decimal digits). It was factored in 1991. The following are RSA-100 and its two factors.

RSA-100
15226050279225333605356183781326374297180681149613
80688657908494580122963258952897654000350692006139

Prime Factors of RSA-100
$p=$ 37975227936943673922808872755445627854565536638199
$q=$ 40094690950920881030683735292761468389214899724061

The exercise is to alter one digit of the smaller factor $p$ until we get a prime number. Each position of $p$ can be altered in 9 different ways. For example, the leading digit of $p$ can be changed to 0,1,2,4,5,6,7,8,9. The leading digit being changed to 0 has the effect that the leading digit is truncated (the resulting number is a 49-digit number).

___________________________________________________________________

The approach we take

Our approach is to work on one digit (position) of $p$ at a time. Once we pick a position, we examine the 9 different resulting numbers. For each of the 9 numbers, we perform the following three quick checks for compositeness.

• Check the sum of the digits. If the sum is divisible by 3, then the number is divisible by 3.
• Look for small prime factors.
• If $n$ is the number being tested, calculate $2^{n-1} \ (\text{mod} \ n)$. If it is not congruent to 1, we know $n$ is composite.

If any one of the checks turns up composite, we move on to another one of the 9 numbers. If all three checks fail to turn up composite, then we perform the Fermat primality test on that number. On the other hand, if all 9 numbers are found to be composite by the quick checks, then we pick another position and perform the same procedure.

___________________________________________________________________

The connection with weakly prime numbers

It is not entirely clear that the exercise of altering one digit of the smaller factor of RSA-100 will eventually produce a prime number. In fact, there are prime numbers such that altering one digit will always produce a composite number. Such prime numbers are called weakly prime numbers. So the exercise we propose is to find out whether $p$, the smaller factor of RSA-100, is a weakly prime number. Our hope is that $p$ is not weakly prime. If one is patient and has a calculator that can work with large numbers, the answer will eventually be found. The number $p$ has 50 digits. So there are 450 numbers to check. However, we hope that a prime number will emerge long before having to check the 450th number.

The first few weakly prime numbers are 294001, 505447, 584141, 604171, 971767, 1062599.

___________________________________________________________________

The first iteration

Our first iteration is on altering the first digit (the leading digit) of $p$. We have the following 9 numbers as a result.

$A_0=$ 07975227936943673922808872755445627854565536638199
$A_1=$ 17975227936943673922808872755445627854565536638199
$A_2=$ 27975227936943673922808872755445627854565536638199
$A_4=$ 47975227936943673922808872755445627854565536638199
$A_5=$ 57975227936943673922808872755445627854565536638199
$A_6=$ 67975227936943673922808872755445627854565536638199
$A_7=$ 77975227936943673922808872755445627854565536638199
$A_8=$ 87975227936943673922808872755445627854565536638199
$A_9=$ 97975227936943673922808872755445627854565536638199

The first check shows that $A_1$, $A_4$ and $A_7$ are divisible by 3. Their sums of digits are 264, 267 and 270, respectively. We can rule out these three numbers. We then divide each remaining number by primes up to (and including) 97. We find that $A_0$, $A_2$ and $A_9$ have small factors. Here are their factors:

$A_0$: 59
$A_2$: 7, 23
$A_9$: 7

The remaining numbers are $A_5$, $A_6$ and $A_8$. We then compute the modular exponentiation in the third check. Here are the results:

$2^{A_5-1} \equiv u \ (\text{mod} \ A_5)$
$2^{A_6-1} \equiv v \ (\text{mod} \ A_6)$
$2^{A_8-1} \equiv w \ (\text{mod} \ A_8)$

where

$u=$ 15312755671443520117479645349899406067694314394411
$v=$ 28479886991585882317542223278882664321705349083600
$w=$ 73062611017560045453228840468835363523125806596486

Clearly $u,v,w$ are not 1. Thus $A_5$, $A_6$ and $A_8$ are all composite. The first iteration yields no prime number.

___________________________________________________________________

Another 2 iterations

Next we choose to alter the second digit (the digit right after the leading digit). By applying the same procedure as for the first iteration, we find that all 9 resulting numbers are composite.

Unwilling to go with the natural order (3rd position, 4th position and so on), we choose the 27th position as the next iteration, 27th counting from the leading digit of $p$. The following are the resulting 9 numbers:

$B_0=$ 37975227936943673922808872055445627854565536638199
$B_1=$ 37975227936943673922808872155445627854565536638199
$B_2=$ 37975227936943673922808872255445627854565536638199
$B_3=$ 37975227936943673922808872355445627854565536638199
$B_4=$ 37975227936943673922808872455445627854565536638199
$B_5=$ 37975227936943673922808872555445627854565536638199
$B_6=$ 37975227936943673922808872655445627854565536638199
$B_8=$ 37975227936943673922808872855445627854565536638199
$B_9=$ 37975227936943673922808872955445627854565536638199

The first check shows that $B_2$, $B_5$ and $B_8$ are divisible by 3. Their sums of digits are 261, 264 and 267, respectively. These 3 numbers $B_2$, $B_5$ and $B_8$ are out. Now look for small factors in the remaining numbers. Divide each of the remaining numbers by small primes up to (and including) 97. Small factors are found for three of them. They are:

$B_0$: 11,47
$B_3$: 53
$B_6$: 17,59

The remaining numbers are $B_1$, $B_4$ and $B_9$. We then compute the modular exponentiation in the third check. Here are the results:

$2^{B_1-1} \equiv f \ (\text{mod} \ B_1)$
$2^{B_4-1} \equiv g \ (\text{mod} \ B_4)$
$2^{B_9-1} \equiv h \ (\text{mod} \ B_9)$

where

$f=$ 1
$g=$ 31019660101262614516708618435524184824189933761142
$h=$ 1

We have some interesting results by going to the 27th position. We have two numbers $B_1$ and $B_9$ that pass the three quick checks. These two numbers could still be composite. It could be that they have large factors that we have not detected. Or they have slightly larger Fermat witnesses that we have not yet found. We hope to settle these issues by applying a more formal primality test.

___________________________________________________________________

Checking for more evidence of primality

We wish perform primality testing on the number $B_1$, the result of altering the 27th digit of the smaller factor of RSA-100 to the digit of 1.

$B_1=$ 37975227936943673922808872155445627854565536638199

Before starting the Fermat test, we want to get further indication that $B_1$ is a prime. A quick check is to calculate $a^{B_1-1} \ (\text{mod} \ B_1)$ for a few more small values of $a$. In addition to $a=2$ that is done earlier, we have the following results:

$2^{B_1-1} \equiv 1 \ (\text{mod} \ B_1)$
$3^{B_1-1} \equiv 1 \ (\text{mod} \ B_1)$
$5^{B_1-1} \equiv 1 \ (\text{mod} \ B_1)$
$7^{B_1-1} \equiv 1 \ (\text{mod} \ B_1)$
$11^{B_1-1} \equiv 1 \ (\text{mod} \ B_1)$
$13^{B_1-1} \equiv 1 \ (\text{mod} \ B_1)$
$17^{B_1-1} \equiv 1 \ (\text{mod} \ B_1)$
$19^{B_1-1} \equiv 1 \ (\text{mod} \ B_1)$
$23^{B_1-1} \equiv 1 \ (\text{mod} \ B_1)$
$29^{B_1-1} \equiv 1 \ (\text{mod} \ B_1)$

So far so good. The Fermat congruence $a^{B_1-1} \ (\text{mod} \ B_1)$ for the first 10 prime numbers $a$ indicates that $B_1$ may be a prime number. Some authors would stop at this point and declare that the number $B_1$ is prime. However, to minimize the chance of making a mistake (incorrectly identifying a composite number as prime), the values of $a$ should not be predetermined and should instead be randomized.

In any case, all the initial checks turn up no evidences that rule out primality for the number $B_1$. We now continue with a randomized implementation of the Fermat test.

___________________________________________________________________

Fermat primality test

The Fermat test works the same as in the previous section, namely to calculate $a^{B_1-1} \ (\text{mod} \ B_1)$ for more values of $a$, except that the values $a$ are randomly selected. The following are 20 randomly selected values of $a$ where $1.

$a_1=$ 19849739905437652815437678431952000620013520723731
$a_2=$ 02124276794830381221643338971178300629602794570271
$a_3=$ 27138338415093662342987393979107100898152383178397
$a_4=$ 13439777399911226335368624024992520689134572541207
$a_5=$ 01296006449462468637265152716377285959118357948169
$a_6=$ 20162901028688646970889573834289207734216891750121
$a_7=$ 03158607876714769183179564222230937245373436521359
$a_8=$ 30367913460183037149800174337058220412636222780561
$a_9=$ 15671981166110368241285379979766798117058521736203
$a_{10}=$ 14484893059068285540085412541574057797151560108393
$a_{11}=$ 21310376560387253850314186514429075431358988956999
$a_{12}=$ 31751454532665167603222246950084316105718129864549
$a_{13}=$ 12514298198917547852874631789610584090955520049889
$a_{14}=$ 08879322212206875977179894330835479198484315727961
$a_{15}=$ 20439695787852522809810248767583601392695571172943
$a_{16}=$ 29336177583771558238055157728918246512748423397641
$a_{17}=$ 02964636742094604954001519522087518508106912037771
$a_{18}=$ 29924256551844529306459072702391350518242680154271
$a_{19}=$ 02316074815801009414245056557583330897320746154349
$a_{20}=$ 27750598271901581943312128958104515130586720939689

To use the Fermat’s little theorem, we need to check that each one of these values of $a$ is relatively prime to the modulus $B_1$. We use the Euclidean algorithm to compute $\text{GCD}(a_j,B_1)$ for all $j=1,2,\cdots,20$. The results are:

$\text{GCD}(a_1,B_1)=1$
$\text{GCD}(a_2,B_1)=1$
$\text{GCD}(a_3,B_1)=1$
$\text{GCD}(a_4,B_1)=1$
$\text{GCD}(a_5,B_1)=1$
$\text{GCD}(a_6,B_1)=1$
$\text{GCD}(a_7,B_1)=1$
$\text{GCD}(a_8,B_1)=1$
$\text{GCD}(a_9,B_1)=1$
$\text{GCD}(a_{10},B_1)=1$
$\text{GCD}(a_{11},B_1)=1$
$\text{GCD}(a_{12},B_1)=1$
$\text{GCD}(a_{13},B_1)=1$
$\text{GCD}(a_{14},B_1)=1$
$\text{GCD}(a_{15},B_1)=1$
$\text{GCD}(a_{16},B_1)=1$
$\text{GCD}(a_{17},B_1)=1$
$\text{GCD}(a_{18},B_1)=1$
$\text{GCD}(a_{19},B_1)=1$
$\text{GCD}(a_{20},B_1)=1$

Each random number is relatively prime to the number $B_1$. This provides another check. If any of the GCD is greater than 1, then we would have found divisor of $B_1$ that is greater than 1, in which case the primality test will be aborted.

Now we proceed to calculate $a_j^{B_1-1} \ (\text{mod} \ B_1)$. If any one of these congruence values is not 1, then we declare that $B_1$ is composite. If all 20 congruence values are 1, then we declare that $B_1$ is a prime number. The following table shows the results.

$\left[\begin{array}{rrr} a_j & \text{ } & a_j^{B_1-1} \ \text{mod} \ B_1 \\ \text{ } & \text{ } & \text{ } \\ a_1 & \text{ } & 1 \\ a_2 & \text{ } & 1 \\ a_3 & \text{ } & 1 \\ a_4 & \text{ } & 1 \\ a_5 & \text{ } & 1 \\ a_6 & \text{ } & 1 \\ a_7 & \text{ } & 1 \\ a_8 & \text{ } & 1 \\ a_9 & \text{ } & 1 \\ a_{10} & \text{ } & 1 \\ a_{11} & \text{ } & 1 \\ a_{12} & \text{ } & 1 \\ a_{13} & \text{ } & 1 \\ a_{14} & \text{ } & 1 \\ a_{15} & \text{ } & 1 \\ a_{16} & \text{ } & 1 \\ a_{17} & \text{ } & 1 \\ a_{18} & \text{ } & 1 \\ a_{19} & \text{ } & 1 \\ a_{20} & \text{ } & 1 \end{array}\right]$

The Fermat test results, both the predetermined part with the first 10 prime numbers and the randomized part with the 20 random selections, show that we have very strong evidence that the number $B_1$ is a prime number. All together, we have shown that $a^{B_1-1} \equiv 1 \ (\text{mod} \ B_1)$ for 30 values of $a$, 20 of which are randomly selected in the interval $1.

Recall Fermat's little theorem, which states that if $n$ is a prime number, then $a^{n-1} \equiv 1 \ (\text{mod} \ n)$ for all integers $a$ relatively prime to the modulus $n$.

With $a^{B_1-1} \equiv 1 \ (\text{mod} \ B_1)$ being true for 30 values of $a$ relatively prime to $B_1$, if we declare that $B_1$ is prime, what is the probability of making a mistake? Put another way, if $B_1$ is really a composite number, what is the probability of getting $a^{B_1-1} \equiv 1 \ (\text{mod} \ B_1)$ for 20 random choices of $a$? The probability is practically zero, except for one caveat. Thus we declare that $B_1$ is a prime number with the one caveat discussed below.

___________________________________________________________________

Remarks

There are composite integers $n$ such that $a^{n-1} \equiv 1 \ (\text{mod} \ n)$ for every integer $a$ that is relatively prime to $n$. These composite integers are called Carmichael numbers. The smallest Carmichael number is 561 (with factors 3, 11, 17).

The Fermat test will always declare a Carmichael number as prime. In other words, the Fermat test will always give a false positive if the test is applied on a Carmichael number. Fortunately Carmichael numbers are rare. So when the number whose primality is being tested is randomly selected, the Fermat test will often give the correct result. Selecting a number at random, it is not likely to pick a Carmichael number. But the number $B_1$ is not obtained by random selection. It is obtained in a predetermined way (by altering one digit of a known prime number).

So if you have a nagging worry that the number $B_1$ might be a Carmichael number, the Miller-Rabin test should be used instead. Carmichael numbers will not evade the Miller-Rabin test. When applying the Miller-Rabin test on a composite number (Carmichael number or not), it will detect the compositeness with arbitrarily small error probability.

The Miller-Rabin test is an extension of the Fermat test and has minimal additional calculation. We actually structure the calculation of $a_j^{B_1-1} \ (\text{mod} \ B_1)$ in the above table with the Miller-Rabin test in mind. We find that the Miller-Rabin test also indicates that the number $B_1$ is prime. With the 20 random values of $a$, the error probability is at most $0.25^{20}$, which is for all practical purposes zero. In other words, if $B_1$ were a composite number, there would be a close to zero chance that Miller-Rabin test would make a mistake by declaring $B_1$ a prime number. With such a small error probability, we declare that the number $B_1$ is prime.

Tying back to the notion of weakly prime numbers, we have found a prime number by altering one digit of the prime number $p$, the smaller factor of RSA-100. Thus the prime number $p$ is not a weakly prime number.

___________________________________________________________________

Exercises

The number

$B_9=$ 37975227936943673922808872955445627854565536638199

,obtained by changing the 27th digit of the smaller factor $p$ of RSA-100 to the digit of 9, is a probable prime (see above). Test the primality of this number.

Find another prime number by altering a different digit of $p$.

Another possible exercise is to do the same exercise on the larger factor of RSA-100 or factors of other RSA numbers.

___________________________________________________________________
$\copyright \ \ 2014 \ \text{Dan Ma}$

# A primality testing exercise from the 9th Fermat number

In this post, we discuss a primality testing exercise on a number derived from a prime factor of the 9th Fermat number. The idea of the exercise is that we test the primality of a number generated from a known large prime number by tagging or inserting a digit into the known prime number. This is an excellent way to generate exercises for primality testing. This approach of altering a known prime number is not meant to be a prime number generation process.

A Fermat number is a positive integer of the form $F_n=2^{2^n}+1$ where $n=0,1,2,\cdots$. The 9th Fermat number is $F_9=2^{2^9}+1=2^{512}+1$. This is a 155-digit number that was completely factored in 1993 [1]. Its three prime factors have 7 digits, 49 digits and 99 digits. The following is the 49-digit factor of $F_9$:

7,455,602,825,647,884,208,337,395,736,200,454,918,783,366,342,657

The above 49-digit number is a prime number that was resulted from a published effort of factorizing $F_9$. The other two factors of $F_9$ can be found in [1] or here. If we tag a digit in front of this 49-digit number, say the digit 6, is the resulting number a prime number? In this post, we discuss the primality testing of the following 50-digit number:

$A=$ 67,455,602,825,647,884,208,337,395,736,200,454,918,783,366,342,657

Primality testing is an important aspect of public key cryptography. For example, the modulus in the public key in RSA cryptosystem is a product of two distinct large prime numbers. To generate the key, it is crucial to generate large numbers at random and to be able to efficiently test whether the numbers are prime.

___________________________________________________________________

Pre-checks before primality testing

Primality tests such as Fermat test and Miller-Rabin test are popular and are easy to use. These tests check for the primality of a given integer $n$ by randomly choosing a set of auxiliary numbers and then checking whether any one of these auxiliary values is a witness to the compositeness of the number $n$. We would like to emphasize the point that before applying a randomized primality testing procedure, it will be advantageous to perform some easy checks to quickly rule out primality. If these quick checks show that the number being tested is composite, we can then continue the search by moving on to another candidate prime number. With the above number $A$ as example, we perform the following pre-checks.

• Check small prime numbers just in case the number being tested has small prime factors.
• If the previous step produces no factors, look for small Fermat witnesses.

The idea of the first check is clear. A Fermat witness for an integer $n$ is an integer $a$ that is relatively prime to $n$ such that $a^{n-1} \not \equiv 1 \ (\text{mod} \ n)$. If we can find such a number $a$, we can say conclusively that $n$ is not a prime number. According to Fermat’s little theorem, if $n$ is a prime number, then the congruence would be a one, i.e., $a^{n-1} \equiv 1 \ (\text{mod} \ n)$. This idea is the basis for the Fermat primality test, which is performed on a random set of values of $a$. Here in the pre-check, we calculate $a^{n-1} \ (\text{mod} \ n)$ for some small values of $a$ such as 2 or 3. The idea is to quickly rule out the candidate prime numbers that happen to have a small Fermat witness.

If either one of the two checks indicate the number being tested is composite, then we pick another number to test. If both of the above steps fail to indicate compositeness, we can then proceed to use the “probabilistic” part of the Fermat test or another probabilistic primality test.

We like to point out that at the outset, the author of the blog did not know the primality status of the 50-digit number $A$ that is obtained by tagging a 6 in front of the 49-digit factor of the 9th Fermat number. Though this number is far too small to work in the RSA algorithm, it serves as an excellent exercise for primality testing.

___________________________________________________________________

Pre-checking the number $A$

Very quickly, 7 is found to be a factor of $A$. We have $A=7 \times B$ where $B$ is:

$B=$ 9636514689378269172619627962314350702683338048951

We then try to find small factors of $B$. The number 283 is found to be a factor of $B$. Then we have $A=7 \times 283 \times C$ where $C$ is the following 47-digit number:

$C=$ 34051288655046887535758402693690285168492360597

By tagging a 6 in front of the 49-digit factor of the 9th Fermat number, we obtain a composite number. The prime or composite status for the number $A$ is settled. Now the next question: is the remaining factor $C$ prime or composite?

___________________________________________________________________

Pre-checking the number $C$

We perform the two pre-checks as described above. In searching for small factors, we find that $C$ is not divisible by all prime numbers less than 200,000. So if $C$ has a factor, it will have to be a large one. Or it could be that $C$ is prime. Instead of continuing to search for factors, we can do the second check. We calculate $2^{C-1} \ (\text{mod} \ C)$ and find that:

$2^{C-1} \equiv t \ (\text{mod} \ C)$

where $t=$ 7426390354305013563302537374271875139618265902

Since $t$ clearly is not 1, this tells us that $C$ is composite.

___________________________________________________________________

Remarks

Instead of doing the randomized primality testing right away, it makes sense to do the pre-checks as described above so that we do not waste time and effort on composite numbers that have small factors or have small Fermat witnesses. As soon as these two checks indicate the compositeness of a number, we then move on to another candidate prime number. If a number passes these two checks, then we can apply a primality test such as the Fermat test or the Miller-Rabin test.

Another remark is that primality testing is easy while factoring is hard. The compositeness of the 47-digit number $C$ can be determined by just one modular exponentiation calculation, which can be computed using the fast powering algorithm. This algorithm uses the binary expansion of the exponent to convert the modular exponentiation into a series of squarings and multiplications. Because the exponent $C-1$ is a 155-bit number, computing $2^{C-1} \ (\text{mod} \ C)$ only requires 154 squarings and at most 154 multiplications (the actual count of multiplications is 76). Implemented in a modern computer, this calculation takes less than one second.

On the other hand, factoring the above 47-digit number $C$ by the brute force approach (checking every possible prime factor) would require checking approximately $2 \times 10^{20}$ many prime numbers as potential factors. The age of the universe is believed to be about 13 billions years, which is about $4 \times 10^{17}$ seconds. That’s why we stop checking for prime factors of $C$ at some point. The authors of [1] factored a 155-digit number in 1993. So the current computing technology is certainly capable of factoring a 47-digit number. But the effort will take time and will require using more advanced factoring algorithm.

___________________________________________________________________

Exercises

The idea of the exercise is that we test the primality of a number generated from a known large prime number by tagging or inserting a digit into the known prime number. Using the same 49-digit factor of $F_9$, we can tag another digit in front or insert a digit somewhere in the middle. Another possibility is to try the other two factors of $F_9$.

There are many other large primes to be found on the Internet that can be used for this exercise. For example, factors of other Fermat numbers and RSA numbers.

___________________________________________________________________

Reference

1. Lenstra A. K., Lenstra H. W., Manasse M. S., Pollard J. M. The Factorization of the Ninth Fermat Number, Mathematiics of Computation, Volume 61, Number 203, July 1993, Pages 319-349.

___________________________________________________________________
$\copyright \ \ 2014 \ \text{Dan Ma}$