# 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}$