C++ Program To Perform Baillie Psw Primality Test

In this article, you will learn the implementation of the Baillie-PSW Primality Test in C++ with its example.

Samuel S. Wagstaff, Jr., John Selfridge, and Colin P. L. Bailey developed the probabilistic primality test known as the Baillie-PSW Primality Test . The test provides an accurate method for determining the primality of numbers by combining elements of the Miller-Rabin and Lucas probable prime tests.

Miller-Rabin Primality Test

✅ Fermat's Little Theorem serves as the foundation for this probabilistic primality test. It checks many random bases to determine the probability that a given integer, n, is prime.
✅ The test is repeated using different random bases and includes modular exponentiation to improve the possibility of accuracy .
✅ A number is usually always right if the test reveals that it is composite.
✅ The probability of misidentifying as prime decreases rapidly when the test is repeated with more random bases.

Lucas Probable Prime Test

✅ The Lucas test is a deterministic test that uses recursively produced sequences called Lucas sequences as the basis of the test.
✅ This test performs particularly well with numbers with special forms, such as Mersenne numbers.
✅ While deterministic, it's less commonly used due to its complexity and limited applicability.

Baillie-PSW Test

✅ The Miller-Rabin and Lucas tests are combined into the Baillie-PSW test .
✅ It determines if a given number passes the Fibonacci or Lucas test in addition to the Miller-Rabin test.
✅ If a number passes both tests, it will likely be prime.

Example:

Let us take an example to illustrate the Baillie-PSW Primality Test in C++.

Example


#include <iostream>
#include <cmath>
// Function to calculate (b^expo_nent) % mod
long long power(long long b, long long expo_nent, long long mod) 
{
    long long ans = 1;
    b %= mod;
    while (expo_nent > 0)
    {
        if (expo_nent % 2 == 1)
            ans = (ans * b) % mod;
        expo_nent >>= 1;
        b = (b * b) % mod;
    }
    return ans;
}
// Utilising the Miller-Rabin primality test, this Function determines if a given integer is Prime.
bool Miller_RabinTest(long long p, int q) 
{
    if (p <= 1)
        return false;
    if (p <= 3)
        return true;
    if (p % 2 == 0)
        return false;
    long long s = p - 1;
    while (s % 2 == 0)
        s >>= 1;
    for (int l = 0; l < q; ++l) 
    {
        long long a = 2 + rand() % (p - 3);
        long long z = power(a, s, p);
        if (z == 1 || z == p - 1)
            continue;
        bool Prime = false;
        while (s != p - 1)
        {
            z = (z * z) % p;
            s *= 2;
            if (z == 1) return false;
            if (z == p - 1)
            {
                Prime = true;
                break;
            }
        }
        if (!Prime) return false;
    }
    return true;
}
//Function to check if a number is a perfect square
bool Perfect_Square(long long p) 
{
    long long root = sqrt(p);
    return root * root == p;
}
//Function to determine if a given integer is a perfect square.
bool Fibonacci(long long p)
{
    return Perfect_Square(5 * p * p + 4) || Perfect_Square(5 * p * p - 4);
}
// The Baillie-PSW primality test function.
bool Baillie_PSWTest(long long p, int q)
{
    return Miller_RabinTest(p, q) && (Fibonacci(p) || (p % 4 == 1));
}
int main() 
{
    long long num;
    int q = 5; 
    //Number of iterations for the Miller-Rabin test
    std::cout << "Enter a number to check for primality: ";
    std::cin >> num;
    if (Baillie_PSWTest(num, q))
        std::cout << num << " is a Prime Number." << std::endl;
    else
        std::cout << num << " is a Composite Number." << std::endl;
    return 0;
}

Output:

Output


Enter a number to check for primality: 3
3 is a Prime Number.

Explanation:

The Baillie-PSW primality test , which determines if a given number is prime, is implemented in this C++ program. It checks composite numbers using several random bases using the Miller-Rabin primality test. It also checks whether the Number matches the requirements for a Lucas or Fibonacci probable prime. After asking the user to enter a number, the application uses the Baillie-PSW test function to determine the integer's primality. Lastly, depending on the test findings, it outputs whether the entered integer is prime or composite. Adjustments to the q parameter control the accuracy of the Miller-Rabin test , balancing precision with computation time.

Example:

Input Required