Large examples of strong pseudoprimes to several bases

A strong pseudoprime to base a is a composite number that passes the strong probable prime test (i.e. the Miller-Rabin test) in the base a. There are indications that strong pseudoprimes are rare. According to [6], there are only 4842 numbers below 25 \cdot 10^9 that are strong pseudoprimes to base 2. Strong pseudoprimes to several bases are even rarer. According to [6], there are only 13 numbers below 25 \cdot 10^9 that are strong pseudoprimes to bases 2, 3 and 5. The paper [4] tabulates the numbers below 10^{12} that are strong pseudoprimes to bases 2, 3 and 5. That listing contains only 101 numbers. These examples show that strong pseudoprimes to several bases may be rare but they do exist. In this post we discuss two rather striking examples of large numbers that are strong pseudoprimes to the first 11 prime bases for the first one and to the first 46 prime bases for the second one. One important lesson that can be drawn from these examples is that the implementation of the strong probable prime test must be randomized.

___________________________________________________________________

The strong probable prime test

Given an odd number n whose “prime versus composite” status is not known, set n-1=2^k \cdot Q where k \ge 1 and Q is odd. Then calculate the following sequence of k+1 numbers:

    \displaystyle a^Q, \ a^{2Q}, \ a^{2^2 Q}, \ \cdots, \ a^{2^{k-1} Q}, \ a^{2^{k} Q} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

where a is some integer relatively prime to n. The first term a^Q can be efficiently calculated using the fast powering algorithm. Each subsequent term is the square of the preceding term. Each term is reduced modulo n.

If a^Q \equiv 1 \ (\text{mod} \ n) (i.e. the first term in sequence (1) is a 1) or a^{2^j \cdot Q} \equiv -1 \ (\text{mod} \ n) for some j=0,1,2,\cdots,k-1 (i.e. the term preceding the first 1 in the sequence is a -1), then n is said to be a strong probable prime to the base a. A strong probable prime to base a could be a prime or could be composite. If the latter, it is said to be a strong pseudoprime to base a. In fact, most strong probable primes to one base are prime.

The strong probable prime test consists of checking whether n is a strong probable prime to several bases. If n is not a strong probable prime to one of the bases, then n is composite for sure. If n is a strong probable prime to all of the bases being used, then n is likely a prime number in that the probability that it is composite is at most 4^{-u} if u is the number of bases.

The last probability of 4^{-u} is what makes the 337-digit number N defined below striking. Here we have a number that is a strong probable prime to 46 bases. What could go wrong in declaring it a prime number? The problem is that using a pre-determined set of bases is not a randomized implementation of the strong probable prime test.

___________________________________________________________________

Examples

The following is a 46-digit found in [3] that is a strong pseudoprime to the first 11 prime bases (the prime numbers from 2 to 31).

    M=
    1195068768795265792518361315725116351898245581

The following is a 337-digit number found in [3] that is a strong pseudoprime to all 46 prime bases up to 200 (the prime numbers from 2 to 199).

    N=
    80383745745363949125707961434194210813883768828755
    81458374889175222974273765333652186502336163960045
    45791504202360320876656996676098728404396540823292
    87387918508691668573282677617710293896977394701670
    82304286871099974399765441448453411558724506334092
    79022275296229414984230688168540432645753401832978
    6111298960644845216191652872597534901

The following sets up the calculation for the Miller-Rabin test (strong probable prime test).

    M-1=2^2 \cdot Q

    N-1=2^2 \cdot R

where Q and R are odd and

    Q=
    298767192198816448129590328931279087974561395

    R=
    20095936436340987281426990358548552703470942207188
    95364593722293805743568441333413046625584040990011
    36447876050590080219164249169024682101099135205823
    21846979627172917143320669404427573474244348675417
    70576071717774993599941360362113352889681126583523
    19755568824057353746057672042135108161438350458244
    6527824740161211304047913218149383725

___________________________________________________________________

Random bases

Though the second number N is very striking, the author of [3] has an even larger example in [2], a 397-digit Carmichael number that is a strong pseudoprime to all the 62 prime bases under 300! One lesson from these examples is that the implementation of the strong probable prime test should be randomized, or at least should include some randomly chosen bases in the testing. Any algorithm that implements the strong probable prime test in any “fixed” way (say, only checking the prime bases up to a certain limit) may incorrectly identify these rare numbers as prime.

Let’s apply the strong probable prime test on the above numbers N and M using some random bases. Consider the following randomly chosen bases b and c where 1<b<M and 1<c<N.

    b=
    932423153687800383671087185189848318498417236

    c=
    23876349986768815408041169070899917334655923628776
    58344592618224528502905948639172375368742187714892
    08287654410018942444630244906406410549094447554821
    42803219639200974486541191341820595453041950723891
    75748815383568979859763861820607576949539863746244
    98291058421101888215044176056586791235119485393994
    789287924346696785645273545040760136

___________________________________________________________________

The calculation using random bases

Here’s the calculation for the 46-digit number M.

    b^Q \equiv t_1 \ (\text{mod} \ M)

    b^{2 \cdot Q} \equiv t_2 \ (\text{mod} \ M)

    b^{M-1}=b^{4 \cdot Q} \equiv t_3 \ (\text{mod} \ M)

where t_1, t_2 and t_3 are:

    t_1=
    1042866890841899880275968177787239559549445173

    t_2=
    826876320842405260107866407865475914456579581

    t_3=
    1195068768795265792518263537659322626328455738

Note that the last number t_3 is not a 1. So the number M is not a strong probable prime to base b. This means that it is composite.

Here’s the calculation for the 337-digit number N.

    c^R \equiv g_1 \ (\text{mod} \ N)

    c^{2 \cdot R} \equiv g_2 \ (\text{mod} \ N)

    c^{N-1}=c^{4 \cdot R} \equiv g_3 \ (\text{mod} \ N)

where g_1, g_2 and g_3 are:

    g_1=
    43050290968654965761881145696359381339174664947842
    93659429396009893693594328847691223585119425166890
    43134041173054778367051375333950357876719375530986
    40705386242996844394887879855798166233504226845778
    76290707027478869178569806270616567220414388766208
    75314254126730991658967210391794715621886266557484
    525788655243561737981785859480518172

    g_2=
    69330060289060873891683879069908453474713549543545
    79381982871766126161928753307995063953670075390874
    26152164526384520359363221849834543643026694082818
    11219470237408138833421506246436132564652734265549
    18153992550152009526926092009346342470917684117296
    93655167027805943247124949639747970357553704408257
    9853042920364675222045446207932076084

    g_3=
    80383745745363949125707961434194210813883768828755
    81458374889175222974273765333652186502336163960045
    45791504202360320876656996676098728404396540823292
    87387918508691668493091034289810372813316104284761
    45244183107779151749589951324358651494383103941607
    35777636976785468267798055151468799251924355070195
    1772723904683953622590747688533861698

Interestingly, the last number g_3 agrees with the modulus N from the first digit (the largest) to digit 167. It is clear that g_3 is clearly not a 1. So the 337-digit number N is not a strong probable prime to base c, meaning it is composite. Even though the number M is a strong pseudoprime to all of the first 46 prime bases, it is easy to tell that it is composite by using just one random base. This calculation demonstrates that it is not likely to make the mistake of identifying large pseudoprimes as prime if randomized bases are used in the strong probable prime test.

___________________________________________________________________

Some verification

We also verify that the 46-digit M is a strong pseudoprime to the first 11 prime bases.

    \left[\begin{array}{rrrrrrr}      a & \text{ } & a^Q \ (\text{mod} \ M) & \text{ }  & a^{2Q} \ (\text{mod} \ M) & \text{ } & a^{4Q} \ (\text{mod} \ M) \\           \text{ } & \text{ } & \text{ }  \\            2 & \text{ } & * & \text{ } & -1 & \text{ } & 1  \\      3 & \text{ } & 1 & \text{ } & 1 & \text{ } & 1  \\      5 & \text{ } & -1 & \text{ } & 1 & \text{ } & 1  \\      7 & \text{ } & * & \text{ } & -1 & \text{ } & 1  \\      11 & \text{ } & * & \text{ } & -1 & \text{ } & 1  \\        13 & \text{ } & * & \text{ } & -1 & \text{ } & 1  \\      17 & \text{ } & * & \text{ } & -1 & \text{ } & 1  \\      19 & \text{ } & * & \text{ } & -1 & \text{ } & 1  \\      23 & \text{ } & * & \text{ } & -1 & \text{ } & 1  \\      29 & \text{ } & * & \text{ } & -1 & \text{ } & 1  \\        31 & \text{ } & * & \text{ } & -1 & \text{ } & 1             \end{array}\right]

The asterisks in the above table mean that those cells have numbers that are \not \equiv \pm 1 modulo M. Clearly the table shows that the number M passes the strong probable prime test for these 11 bases. We also verify that M is not a strong probable prime to base 37, the next prime base.

    37^Q \equiv w_1 \ (\text{mod} \ M)

    37^{2 \cdot Q} \equiv w_2 \ (\text{mod} \ M)

    37^{M-1}=b^{4 \cdot Q} \equiv w_3 \ (\text{mod} \ M)

where

    w_1=
    977597583337476418144488003654858986215112009

    w_2=
    368192447952860532410592685925434163011455842

    w_3=
    1195068768795265792518263537659322626328455738

Note that the last number w_3 agrees with the modulus M for the first 22 digits and they differ in the subsequent digits. It is clear that w_3 is not 1. So the strong pseudoprimality of M stops at the base 37.

We do not verify the number N for all the 46 prime bases. We only show partial verification. The following calculation shows the pseudoprimality of N to bases 197 and 199, and that the strong pseudoprimality of N fails at 211, the next prime base.

    197^R \equiv * \ (\text{mod} \ N)

    197^{2 \cdot R} \equiv -1 \ (\text{mod} \ N)

    197^{N-1}=197^{4 \cdot R} \equiv 1 \ (\text{mod} \ N)

    __________________

    199^R \equiv * \ (\text{mod} \ N)

    199^{2 \cdot R} \equiv -1 \ (\text{mod} \ N)

    199^{N-1}=199^{4 \cdot R} \equiv 1 \ (\text{mod} \ N)

    __________________

    211^R \equiv v_1 \ (\text{mod} \ N)

    211^{2 \cdot R} \equiv v_2 \ (\text{mod} \ N)

    211^{N-1}=211^{4 \cdot R} \equiv 1 \ (\text{mod} \ N)

where

    v_1=
    48799236892584399744277334997653638759429800759183
    35229821626086043683022014304157526246067279138485
    99367014952239377476103536546259094903793421522217
    99291447356172114871135567262925519534270746139465
    22832800077663455346130103616087329184090071367607
    57478119260722231575606816699461642864577323331271
    2974554583992816678859279700007174348

    v_2=
    80191643327899921083661290416909370601037633208226
    50175490124094760064341402392485432446383194439467
    16432633017071633393829046762783433857505596089159
    3600905184063673203

Note that v_2 is clearly not congruent to -1. Thus the number N is not a strong pseudoprime to base 211 (though it is a pseudoprime to base 211). Clearly, the above calculation indicates that the number N is a strong pseudoprime to bases 197 and 199.

___________________________________________________________________

Remark

Because strong pseudoprimes are rare (especially those that are strong pseudoprimes to several bases), they can be used as primality tests. One idea is to use the least pseudoprimes to the first n prime bases [5]. This method is discussed in this previous post.

Another idea is to use the listing of strong pseudoprimes to several bases that are below a bound. Any number below the bound that is strong probable primes to these bases and that is not on the list must be a prime. For example, Table 1 of [4] lists 101 strong pseudoprimes to bases 2, 3 and 5 that are below 10^{12}. This test is fast and easy to use; it requires only three modular exponentiations to determine the primality of numbers less than 10^{12}.

The numbers M and N are not Carmichael numbers since b^{M-1} \not \equiv 1 \ (\text{mod} \ M) and c^{N-1} \not \equiv 1 \ (\text{mod} \ N), making the random numbers b and c Fermat witnesses for these two numbers respectively. Another way to see that they are not Carmichael is that each of the two number M and N is also a product of two distinct primes according to [3].

An even more striking result than the examples of M and N is that it follows from a theorem in [1] that for any finite set of bases, there exist infinitely many Carmichael numbers which are strong pseudoprimes to all the bases in the given finite set. This is discussed in the next post.

___________________________________________________________________

Reference

  1. Alford W., Granville A., and Pomerance C., On the difficulty
    of finding reliable witnesses
    , L. Adleman and M.-D. Huang, editors, Algorithmic Number Theory: Proc. ANTS-I, Ithaca, NY, volume 877 of
    Lecture Notes in Computer Science, pages 1–16. Springer–Verlag, 1994.
  2. Arnault F., Constructing Carmichael numbers which are strong pseudoprimes to several bases, J. Symbolic Computation, 20, 151-161, 1995.
  3. Arnault F., Rabin-Miller primality test: composite numbers that pass it, Math. Comp., Volume 64, No. 209, 355-361, 1995.
  4. Jaeschke G., On strong pseudoprimes to several bases, Math. Comp., Volume 61, No. 204, 915-926, 1993.
  5. Jiang Yupeng, Deng Yingpu, Strong pseudoprimes to the first 9 prime bases, arXiv:1207.0063v1 [math.NT], June 30, 2012.
  6. Pomerance C., Selfridge J. L., Wagstaff, S. S., The pseudoprimes to 25 \cdot 10^9, Math. Comp., Volume 35, No. 151, 1003-1026, 1980.

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s