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<B_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<a<B_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}