A primality proving algorithm using least strong pseudoprimes

This post is the continuation of this previous post. In this post, we discuss a deterministic primality proving algorithm that uses the least strong pseudoprimes to several prime bases. After describing the test, we present several examples.

The previous post discusses the notion of witness for the strong probable prime test (the Miller-Rabin test). One important characteristic of the strong probable prime test is that for any composite number, there is always at least one witness (in fact lots of them). This means that the strong probable prime test is not going to be tripped up on a Carmichael number like it is for the Fermat test.

When there is a guarantee that every composite number has a witness for its compositeness, it makes sense to talk about the least witness w(n) for a composite number n. The statement that w(n)>B is equivalent to the statement that n is a strong pseudoprime to all the bases less than or equal to B. Strong pseudoprimes to base 2 are rare. Strong pseudoprimes to multiple bases are even rarer. According to [2], there are only 13 numbers below 25 \cdot 10^9 that are strong pseudoprimes to all of the bases 2, 3 and 5. Thus it is rare to have composite numbers n whose w(n)>5. Because they are rare, knowing about strong pseudoprimes can help us find the primes.

The test in question comes from [1]. It had been improved and sharpened over the years. The paper [1] seems to contain the best results to date regarding this test. To see how the method evolved and got improved, any interested reader can look at the references provided in [1]. Let \psi_n be the least strong pseudoprime to all of the first n prime bases. The paper [1] presents the following 11 least strong pseudoprimes.

    \psi_1= 2047

    \psi_2= 1373653

    \psi_3= 25326001

    \psi_4= 3215031751

    \psi_5= 2152302898747

    \psi_6= 3474749660383

    \psi_7=\psi_8= 341550071723321

    \psi_9=\psi_{10}=\psi_{11}= 3825123056546413051

To illustrate, the number 25326001 is the smallest strong pseudoprime to all the bases 2, 3 and 5. For any odd number n less than 25326001, check whether n is a strong probable to these 3 bases. If it is, then n has to be prime. Otherwise, n is a strong pseudoprime to bases 2, 3 and 5 that is less than 25326001! Of course, if n happens to be not a strong probable prime to one of the 3 bases, then it is a composite number.

The test using \psi_n represents a primality test that actually proves primality rather than just giving strong evidence for primality. Using \psi_n, the test only requires n modular exponentiations. This test is a limited test since it only applies to numbers less than \psi_n. However, it is interesting to note that the notions of strong probable primes and strong pseudoprimes give a deterministic primality test (though limited) that is fast and easy to use in addition to the usual Miller-Rabin probabilistic primality test.

___________________________________________________________________

Examples

Example 1
Consider the number n= 2795830049. This number is below \psi_4. So we check for probable primality of n to the bases 2, 3, 5, and 7. First of all, n-1=2^5 \cdot Q where Q= 87369689. Here’s the calculation.

    2^Q \equiv 937249258 \ (\text{mod} \ 2795830049)

    2^{2 \cdot Q} \equiv 2693069488 \ (\text{mod} \ 2795830049)

    2^{4 \cdot Q} \equiv 226823779 \ (\text{mod} \ 2795830049)

    2^{8 \cdot Q} \equiv 2795830048 \equiv -1 \ (\text{mod} \ 2795830049)

    2^{16 \cdot Q} \equiv 1 \ (\text{mod} \ 2795830049)

    2^{32 \cdot Q} \equiv 1 \ (\text{mod} \ 2795830049)

Note that the first term that is a 1 in the above sequence is 2^{16 \cdot Q}. The preceding term is a -1. Thus n= 2795830049 is a strong probable prime to base 2. Now the base 3 calculation.

    3^Q \equiv 268289123 \ (\text{mod} \ 2795830049)

    3^{2 \cdot Q} \equiv 717416975 \ (\text{mod} \ 2795830049)

    3^{4 \cdot Q} \equiv 17652213 \ (\text{mod} \ 2795830049)

    3^{8 \cdot Q} \equiv 2569006270 \ (\text{mod} \ 2795830049)

    3^{16 \cdot Q} \equiv 2795830048 \equiv -1 \ (\text{mod} \ 2795830049)

    3^{32 \cdot Q} \equiv 1 \ (\text{mod} \ 2795830049)

Note that the first term that is a 1 in the above sequence is the last term 3^{32 \cdot Q}. The preceding term is a -1. Thus n= 2795830049 is a strong probable prime to base 3. Now the base 5 calculation.

    5^Q \equiv 102760561 \ (\text{mod} \ 2795830049)

    5^{2 \cdot Q} \equiv 226823779 \ (\text{mod} \ 2795830049)

    5^{4 \cdot Q} \equiv 2795830048 \equiv -1 \ (\text{mod} \ 2795830049)

    5^{8 \cdot Q} \equiv 1 \ (\text{mod} \ 2795830049)

    5^{16 \cdot Q} \equiv 1 \ (\text{mod} \ 2795830049)

    5^{32 \cdot Q} \equiv 1 \ (\text{mod} \ 2795830049)

The base 7 calculation.

    7^Q \equiv 121266349 \ (\text{mod} \ 2795830049)

    7^{2 \cdot Q} \equiv 937249258 \ (\text{mod} \ 2795830049)

    7^{4 \cdot Q} \equiv 2693069488 \ (\text{mod} \ 2795830049)

    7^{8 \cdot Q} \equiv 226823779 \ (\text{mod} \ 2795830049)

    7^{16 \cdot Q} \equiv 2795830048 \equiv -1 \ (\text{mod} \ 2795830049)

    7^{32 \cdot Q} \equiv 1 \ (\text{mod} \ 2795830049)

Both the base 5 and base 7 calculations show that n= 2795830049 is a strong probable prime to both bases. The calculations for the 4 bases conclusively prove that n= 2795830049 is a prime number.

Example 2
Consider the number n= 62834664835837. This number is below \psi_7. So we check for probable primality to the bases 2, 3, 5, 7, 11, 13, and 17. First, n-1=2^2 \cdot Q where Q= 15708666208959.

    2^Q \equiv 49994720924726 \ (\text{mod} \ 62834664835837)

    2^{2 \cdot Q} \equiv 62834664835836 \equiv -1 \ (\text{mod} \ 62834664835837)

    2^{4 \cdot Q} \equiv 1 \ (\text{mod} \ 62834664835837)

    __________________

    3^Q \equiv 1 \ (\text{mod} \ 62834664835837)

    3^{2 \cdot Q} \equiv 1 \ (\text{mod} \ 62834664835837)

    3^{4 \cdot Q} \equiv 1 \ (\text{mod} \ 62834664835837)

    __________________

    5^Q \equiv 49994720924726 \ (\text{mod} \ 62834664835837)

    5^{2 \cdot Q} \equiv 62834664835836 \equiv -1 \ (\text{mod} \ 62834664835837)

    5^{4 \cdot Q} \equiv 1 \ (\text{mod} \ 62834664835837)

    __________________

    7^Q \equiv 49994720924726 \ (\text{mod} \ 62834664835837)

    7^{2 \cdot Q} \equiv 62834664835836 \equiv -1 \ (\text{mod} \ 62834664835837)

    7^{4 \cdot Q} \equiv 1 \ (\text{mod} \ 62834664835837)

    __________________

    11^Q \equiv 1 \ (\text{mod} \ 62834664835837)

    11^{2 \cdot Q} \equiv 1 \ (\text{mod} \ 62834664835837)

    11^{4 \cdot Q} \equiv 1 \ (\text{mod} \ 62834664835837)

    __________________

    13^Q \equiv 12839943911111 \ (\text{mod} \ 62834664835837)

    13^{2 \cdot Q} \equiv 62834664835836 \equiv -1 \ (\text{mod} \ 62834664835837)

    13^{4 \cdot Q} \equiv 1 \ (\text{mod} \ 62834664835837)

    __________________

    17^Q \equiv 1 \ (\text{mod} \ 62834664835837)

    17^{2 \cdot Q} \equiv 1 \ (\text{mod} \ 62834664835837)

    17^{4 \cdot Q} \equiv 1 \ (\text{mod} \ 62834664835837)

The calculation for all bases shows that n= 62834664835837 is a strong probable primes to all 7 prime bases. This shows that n= 62834664835837 is prime.

Example 3
Consider the number n= 21276028621. This is a 11-digit number and is less than \psi_5. The algorithm is to check for the strong probable primality of n to the first 5 prime bases – 2, 3, 5, 7, 11. First, n-1=2^2 \cdot Q where Q= 5319007155.

    2^Q \equiv 560973617 \ (\text{mod} \ 21276028621)

    2^{2 \cdot Q} \equiv 21276028620 \equiv -1 \ (\text{mod} \ 21276028621)

    2^{4 \cdot Q} \equiv 1 \ (\text{mod} \ 21276028621)

    __________________

    3^Q \equiv 1 \ (\text{mod} \ 21276028621)

    3^{2 \cdot Q} \equiv 1 \ (\text{mod} \ 21276028621)

    3^{4 \cdot Q} \equiv 1 \ (\text{mod} \ 21276028621)

    __________________

    5^Q \equiv 1 \ (\text{mod} \ 21276028621)

    5^{2 \cdot Q} \equiv 1 \ (\text{mod} \ 21276028621)

    5^{4 \cdot Q} \equiv 1 \ (\text{mod} \ 21276028621)

    __________________

    7^Q \equiv 10282342854 \ (\text{mod} \ 21276028621)

    7^{2 \cdot Q} \equiv 19716227277 \ (\text{mod} \ 21276028621)

    7^{4 \cdot Q} \equiv 21275616058 \ (\text{mod} \ 21276028621)

Things are going well for the first 3 prime bases. The number n= 21276028621 is a strong pseudoprime to the first 3 prime bases. However, it is not a strong probable prime to base 7. Thus the number is composite. In fact, n= 21276028621 is one of the 13 numbers below 25 \cdot 10^9 that are strong pseudoprimes to bases 2, 3 and 5.

___________________________________________________________________

Exercises

Use the least strong pseudoprime primality test that is described here to determine the primality or compositeness of the following numbers:

  • 58300313
  • 235993423
  • 1777288949
  • 40590868757
  • 874191954161
  • 8667694799429
  • 1250195846428003

___________________________________________________________________

Reference

  1. Yupeng Jiang, Yingpu Deng, Strong pseudoprimes to the first 9 prime bases, arXiv:1207.0063v1 [math.NT], June 30, 2012.
  2. Pomerance C., Selfridge J. L., Wagstaff, S. S., The pseudoprimes to 25 \cdot 10^9, Math. Comp., Volume 35, 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