Prueba de primalidad | Conjunto 5 (usando la serie Lucas-Lehmer)

En este artículo, discutiremos la serie de Lucas-Lehmer que se usa para verificar la primalidad de los números primos de la forma 2 ^p – 1 donde p es un número entero.
Primero, veamos qué es la serie de Lucas-Lehmer.
La serie de Lucas-Lehmer se puede expresar como: 

Por lo tanto, la serie es: 
Término 0: 4, 
Término 1: 4*4 – 2 = 14, 
Término 2: 14*14 – 2 = 194, 
Término 3: 194*194 – 2 = 37634, 
Término 4: 37634*37634 – 2 = 1416317954, … y así sucesivamente.
A continuación se muestra el programa para averiguar los primeros n términos de la serie de Lucas-Lehmer.
 

// C++ program to find out Lucas-Lehmer series.
#include <iostream>
#include <vector>
using namespace std;
 
// Function to find out first n terms
// (considering 4 as 0th term) of
// Lucas-Lehmer series.
void LucasLehmer(int n) {
 
  // the 0th term of the series is 4.
  unsigned long long current_val = 4;
 
  // create an array to store the terms.
  vector<unsigned long long> series;
 
  // compute each term and add it to the array.
  series.push_back(current_val);
  for (int i = 0; i < n; i++) {
    current_val = current_val * current_val - 2;
    series.push_back(current_val);
  }
 
  // print out the terms one by one.
  for (int i = 0; i <= n; i++)
    cout << "Term " << i << ": "
        << series[i] << endl; 
}
 
// Driver program
int main() {
  int n = 5;
  LucasLehmer(n);
  return 0;
}

// Java program to find out
// Lucas-Lehmer series.
import java.util.*;
 
class GFG
{
 
    // Function to find out
    // first n terms(considering
    // 4 as 0th term) of Lucas-
    // Lehmer series.
    static void LucasLehmer(int n)
    {
 
        // the 0th term of
        // the series is 4.
        long current_val = 4;
 
        // create an array
        // to store the terms.
        ArrayList<Long> series = new ArrayList<>();
 
         // compute each term
        // and add it to the array.
        series.add(current_val);
        for (int i = 0; i < n; i++)
        {
            current_val = current_val
                    * current_val - 2;
            series.add(current_val);
        }
 
        // print out the
       // terms one by one.
        for (int i = 0; i <= n; i++)
        {
            System.out.println("Term " + i
                    + ": " + series.get(i));
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        int n = 5;
        LucasLehmer(n);
    }
}
 
// This code has been contributed by 29AjayKumar

# Python3 program to find out Lucas-Lehmer series.
 
# Function to find out first n terms
# (considering 4 as 0th term) of
# Lucas-Lehmer series.
def LucasLehmer(n):
 
  # the 0th term of the series is 4.
  current_val = 4;
 
  # create an array to store the terms.
  series = []
 
  # compute each term and add it to the array.
  series.append(current_val)
 
  for i in range(n):
    current_val = current_val * current_val - 2;
    series.append(current_val);
 
  # print out the terms one by one.
  for i in range(n + 1):
      print("Term", i, ":", series[i])
 
# Driver program
if __name__=='__main__':
 
  n = 5;
  LucasLehmer(n);
   
# This code is contributed by pratham76.

// C# program to find out
// Lucas-Lehmer series.
using System;
using System.Collections.Generic;
 
class GFG
{
     
// Function to find out
// first n terms(considering
// 4 as 0th term) of Lucas-
// Lehmer series.
static void LucasLehmer(int n)
{
 
// the 0th term of
// the series is 4.
long current_val = 4;
 
// create an array
// to store the terms.
List<long> series = new List<long>();
 
// compute each term
// and add it to the array.
series.Add(current_val);
for (int i = 0; i < n; i++)
{
    current_val = current_val *
                  current_val - 2;
    series.Add(current_val);
}
 
// print out the
// terms one by one.
for (int i = 0; i <= n; i++)
    Console.WriteLine("Term " + i +
                      ": " + series[i]);
}
 
// Driver Code
static void Main()
{
    int n = 5;
    LucasLehmer(n);
}
}
 
// This code is contributed by
// ManishShaw(manishshaw1)

<script>
// Javascript program to find out
// Lucas-Lehmer series.
 
// Function to find out
    // first n terms(considering
    // 4 as 0th term) of Lucas-
    // Lehmer series.
function LucasLehmer(n)
{
 
    // the 0th term of
        // the series is 4.
        let current_val = 4;
  
        // create an array
        // to store the terms.
        let series = [];
  
         // compute each term
        // and add it to the array.
        series.push(current_val);
        for (let i = 0; i < n; i++)
        {
            current_val = (current_val
                    * current_val) - 2;
            series.push(current_val);
        }
  
        // print out the
       // terms one by one.
        for (let i = 0; i <= n; i++)
        {
            document.write("Term " + i
                    + ": " + series[i]+"<br>");
        }
}
 
// Driver Code
let n = 5;
LucasLehmer(n);
 
// This code is contributed by rag2127
</script>

Producción:  

Term 0: 4
Term 1: 14
Term 2: 194
Term 3: 37634
Term 4: 1416317954
Term 5: 2005956546822746114

Podemos usar string para almacenar los números grandes de la serie.
Ahora bien , ¿cuál es la relación con los números primos de esta serie de Lucas-Lehmer? 
 

1. Lo primero es que solo podemos verificar la primalidad de aquellos números que podemos representar como, x = (2 ^p – 1) donde p es un número entero. 
2. Ahora tenemos que encontrar el (p-1)-ésimo término de la serie de Lucas-Lehmer. 
3. Si este término es un múltiplo de x, entonces x es un número primo. 
4. Cuando x es grande, es decir, p es grande, entonces podemos encontrar dificultades para encontrar el (p-1)-ésimo término de la serie.
Más bien, lo que podemos hacer: 
1. Comenzar a calcular la serie de Lucas-Lehmer desde el término 0 y almacenar el término completo solo almacenar el s[i]%x (es decir, el término módulo x). 
2. Calcule el siguiente número de esta serie modificada utilizando el término anterior. s[i] = (s[i-1] ² – 2)%x. 
3. Calcule hasta el término (p-1). 
4. Si el término (p-1) es 0, entonces x es primo; de lo contrario, no. Por lo tanto, s[p-1] tiene que ser 0 para ser x = (2 ^p – 1) primo.

Ejemplos:  

Is 2^7 - 1 = 127 is a prime?
        so here x = 127, p = 7-1 = 6.
        Hence the modified Lucas-Lehmer series is:
        term 1: 4,
        term 2: (4*4 - 2) % 127 = 14,
        term 3: (14*14 - 2) % 127 = 67,
        term 4: (67*67 - 2) % 127 = 42,
        term 5: (42*42 - 2) % 127 = 111,
        term 6: (111*111) % 127 = 0.
        Here the 6th term is 0 so 127 is a prime number.

Código para comprobar si 2^p-1 es primo o no
 

// CPP program to check for primality using
// Lucas-Lehmer series.
#include <cmath>
#include <iostream>
using namespace std;
 
// Function to check whether (2^p - 1)
// is prime or not.
bool isPrime(int p) {
 
  // generate the number
  long long checkNumber = pow(2, p) - 1;
 
  // First number of the series
  long long nextval = 4 % checkNumber;
 
  // Generate the rest (p-2) terms
  // of the series.
  for (int i = 1; i < p - 1; i++)
    nextval = (nextval * nextval - 2) % checkNumber; 
 
  // now if the (p-1)th term is
  // 0 return true else false.
  return (nextval == 0);
}
 
// Driver Program
int main() {
  // Check whether 2^p-1 is prime or not.
  int p = 7;
 
  long long checkNumber = pow(2, p) - 1;
 
  if (isPrime(p))
    cout << checkNumber << " is Prime.";
  else
    cout << checkNumber << " is not Prime.";
 
  return 0;
}

// Java program to check for primality using
// Lucas-Lehmer series.
 
class GFG{
// Function to check whether (2^p - 1)
// is prime or not.
static boolean isPrime(int p) {
 
// generate the number
double checkNumber = Math.pow(2, p) - 1;
 
// First number of the series
double nextval = 4 % checkNumber;
 
// Generate the rest (p-2) terms
// of the series.
for (int i = 1; i < p - 1; i++)
    nextval = (nextval * nextval - 2) % checkNumber;
 
// now if the (p-1)th term is
// 0 return true else false.
return (nextval == 0);
}
 
// Driver Program
public static void main(String[] args) {
// Check whether 2^p-1 is prime or not.
int p = 7;
double checkNumber = Math.pow(2, p) - 1;
 
if (isPrime(p))
    System.out.println((int)checkNumber+" is Prime.");
else
    System.out.println((int)checkNumber+" is not Prime.");
 
}
}
// This code is contributed by mits

# Python3 Program to check for primality
# using Lucas-Lehmer series.
 
# Function to check whether (2^p - 1)
# is prime or not.
def isPrime(p):
 
    # generate the number
    checkNumber = 2 ** p - 1
 
    # First number of the series
    nextval = 4 % checkNumber
 
    # Generate the rest (p-2) terms
    # of the series
    for i in range(1, p - 1):
        nextval = (nextval * nextval - 2) % checkNumber
 
    # now if the (p-1) the term is
    # 0 return true else false.
    if (nextval == 0): return True
    else: return False
 
# Driver Code
 
# Check whether 2^(p-1)
# is prime or not.
p = 7
checkNumber = 2 ** p - 1
 
if isPrime(p):
    print(checkNumber, 'is Prime.')
else:
    print(checkNumber, 'is not Prime')
 
# This code is contributed by egoista.

// C# program to check for primality using
// Lucas-Lehmer series.
using System;
 
class GFG{
// Function to check whether (2^p - 1)
// is prime or not.
static bool isPrime(int p) {
 
// generate the number
double checkNumber = Math.Pow(2, p) - 1;
 
// First number of the series
double nextval = 4 % checkNumber;
 
// Generate the rest (p-2) terms
// of the series.
for (int i = 1; i < p - 1; i++)
    nextval = (nextval * nextval - 2) % checkNumber;
 
// now if the (p-1)th term is
// 0 return true else false.
return (nextval == 0);
}
 
// Driver Program
static void Main() {
// Check whether 2^p-1 is prime or not.
int p = 7;
double checkNumber = Math.Pow(2, p) - 1;
 
if (isPrime(p))
    Console.WriteLine((int)checkNumber+" is Prime.");
else
    Console.WriteLine((int)checkNumber+" is not Prime.");
 
}
}
// This code is contributed by mits

<?php
// PHP program to check for
// primality using Lucas-
// Lehmer series.
 
// Function to check whether
/// (2^p - 1) is prime or not.
function isPrime($p)
{
 
    // generate the number
        $checkNumber = pow(2, $p) - 1;
     
    // First number of the series
        $nextval = 4 % $checkNumber;
     
    // Generate the rest (p-2) terms
    // of the series.
    for ($i = 1; $i < $p - 1; $i++)
        $nextval = ($nextval * $nextval - 2) %
                                 $checkNumber;
     
    // now if the (p-1)th term is
    // 0 return true else false.
    return ($nextval == 0);
}
 
    // Driver Code
    // Check whether 2^p-1 is
    // prime or not.
    $p = 7;
    $checkNumber = pow(2, $p) - 1;
    if (isPrime($p))
        echo $checkNumber , " is Prime.";
    else
        echo $checkNumber , " is not Prime.";
 
// This code is contributed by ajit.
?>

<script>
    // Javascript program to check for primality using
    // Lucas-Lehmer series.
     
    // Function to check whether (2^p - 1)
    // is prime or not.
    function isPrime(p) {
 
        // generate the number
        let checkNumber = Math.pow(2, p) - 1;
 
        // First number of the series
        let nextval = 4 % checkNumber;
 
        // Generate the rest (p-2) terms
        // of the series.
        for (let i = 1; i < p - 1; i++)
            nextval = (nextval * nextval - 2) % checkNumber;
 
        // now if the (p-1)th term is
        // 0 return true else false.
        return (nextval == 0);
    }
     
    // Check whether 2^p-1 is prime or not.
    let p = 7;
    let checkNumber = Math.pow(2, p) - 1;
 
    if (isPrime(p))
        document.write(checkNumber+" is Prime.");
    else
        document.write(checkNumber+" is not Prime.");
     
</script>

Producción:  

127 is Prime.

El número primo más grande en el momento de escribir este artículo es (2^(77232917) – 1) (descubierto el 26 de diciembre de 2017). Tiene 23, 249, 425 dígitos. Estos números primos se encuentran de la misma manera discutida anteriormente. Se requiere una gran potencia computacional y varios meses de procesamiento para encontrar este tipo de grandes números primos. 
Un hecho interesante es que para verificar tantos números primos grandes, p también se toma como primo. Después del procesamiento, si encuentra que el número x no es primo, se toma p como el siguiente número primo y se ejecuta el mismo proceso.