Tutorialspoint.dev

Lucas Primality Test

A number p greater than one is prime if and only if the only divisors of p are 1 and p. First few prime numbers are 2, 3, 5, 7, 11, 13, …

The Lucas test is a primality test for a natural number n, it can test primality of any kind of number.

It follows from Fermat’s Little Theorem: If p is prime and a is an integer, then a^p is congruent to a (mod p )

Lucas’ Test : A positive number n 
is prime if there exists an integer a (1 < a 
< n) such that :

a^{{n-1}} equiv  1{pmod n}

And for every prime factor q of (n-1),

a^{{({n-1})/q}} 
ot equiv  1{pmod n}

Examples :

Input :  n = 7
Output : 7 is Prime
Explanation : let's take a = 3, 
then 3^6 % 7 = 729 % 7 = 1 (1st 
condition satisfied). Prime factors 
of 6 are 2 and 3,
3^(6/2) % 7 = 3^3 % 7 = 27 % 7 = 6
3^(6/3) % 7 = 3^2 % 7 = 9 % 7 = 2
Hence, 7 is Prime  

Input :  n = 9
Output : 9 is composite
Explanation : Let's take a = 2,
then 2^8 % 8 = 256 % 8 = 0
Hence 9 is composite 
lucasTest(n):
If n is even
    return composite
Else
   Find all prime factors of n-1
   for i=2 to n-1
      pick 'a' randomly in range [2, n-1]
      if a^(n-1) % n not equal 1:
          return composite
      else 
          // for all q, prime factors of (n-1)
          if a^(n-1)/q % n not equal 1 
             return prime
   Return probably prime

Problems Associated with Lucas’s test are :



  • Knowing all of the prime factors of n-1
  • Finding an appropriate choice for a
    • // CPP Program for Lucas Primality Test
      #include <bits/stdc++.h>
      using namespace std;
        
      // function to generate prime factors of n
      void primeFactors(int n, vector<int>& factors)
      {
          // if 2 is a factor
          if (n % 2 == 0)
              factors.push_back(2);
          while (n % 2 == 0)
              n = n / 2;
                
          // if prime > 2 is factor
          for (int i = 3; i <= sqrt(n); i += 2) {
              if (n % i == 0)
                  factors.push_back(i);
              while (n % i == 0)
                  n = n / i;
          }
          if (n > 2)
            factors.push_back(n);
      }
        
      // this function produces power modulo 
      // some number. It can be optimized to 
      // using 
      int power(int n, int r, int q)
      {
          int total = n;
          for (int i = 1; i < r; i++)
              total = (total * n) % q;
          return total;
      }
        
      string lucasTest(int n)
      {
          // Base cases 
          if (n == 1)
              return "neither prime nor composite";
          if (n == 2)
              return "prime";
          if (n % 2 == 0)
              return "composite1";
                
                
          // Generating and storing factors 
          // of n-1
          vector<int> factors;
          prime_factors(n - 1, factors);
        
          // Array for random generator. This array 
          // is to ensure one number is generated 
          // only once
          int random[n - 3];
          for (int i = 0; i < n - 2; i++)
              random[i] = i + 2;
                
          // shuffle random array to produce randomness
          shuffle(random, random + n - 3, 
                     default_random_engine(time(0)));
        
          // Now one by one perform Lucas Primality
          // Test on random numbers generated.
          for (int i = 0; i < n - 2; i++) {
              int a = random[i]; 
              if (power(a, n - 1, n) != 1) 
                  return "composite";
        
              // this is to check if every factor 
              // of n-1 satisfy the condition
              bool flag = true;
              for (int k = 0; k < factors.size(); k++) {
                  // if a^((n-1)/q) equal 1
                  if (power(a, (n - 1) / factors[k], n) == 1) {
                      flag = false;
                      break;
                  }
              }
        
              // if all condition satisfy
              if (flag)
                  return "prime";
          }
          return "probably composite";
      }
        
      // Driver code
      int main()
      {
          cout << 7 << " is " << lucasTest(7) << endl;
          cout << 9 << " is " << lucasTest(9) << endl;
          cout << 37 << " is " << lucasTest(37) << endl;
          return 0;
      }

      Output:

      7 is prime
      9 is composite
      37 is prime
      

      This method is quite complicated and inefficient as compared to other primality tests. And the main problems are factors of ‘n-1’ and choosing appropriate ‘a’.

      Other Primality tests:

      Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter