Prueba de primalidad | Conjunto 4 (Solovay-Strassen)

Ya hemos sido introducidos a las pruebas de primalidad en los artículos anteriores de esta serie. 

La prueba de primalidad de Solovay-Strassen es una prueba probabilística para determinar si un número es compuesto o probablemente primo. 
Antes de sumergirnos en el código, necesitaremos comprender algunos términos y conceptos clave para poder codificar este algoritmo.

Antecedentes:
Símbolo de Legendre: Este símbolo se define como un par de números enteros ayp tales que p es primo. Se denota por (a/p) y se calcula como: 

      = 0    if a%p = 0
(a/p) = 1    if there exists an integer k such that k2 = a(mod p)
      = -1   otherwise.

Euler demostró que: 

 (a/p) = a((p-1)/2)%p Condition (i)

Símbolo jacobiano: este símbolo es una generalización del símbolo de Legendre, donde p se reemplaza por n donde n es

n = p1k1 * .. * pnkn

, entonces el símbolo jacobiano se define como: 

(a/n) = ((a/p1)k1) * ((a/p2)k2) *.....* ((a/pn)kn)

Si n se toma como un número primo, entonces el jacobiano es igual al símbolo de Legendre. Estos símbolos tienen ciertas propiedades
1) (a/n) = 0 si mcd(a,n) != 1, por lo tanto (0/n) = 0. Esto se debe a que si mcd(a,n) != 1, entonces debe haber algún primo pi tal que pi divida tanto a a como a n. En ese caso (a/pi) = 0 [por definición del Símbolo de Legendre]. 
2) (ab/n) = (a/n) * (b/n). Se puede derivar fácilmente del hecho (ab/p) = (a/p)(b/p) (aquí (a/p) es el Símbolo Legendario). 
3) Si a es par, entonces (a/n) = (2/n)*((a/2)/n). Se puede demostrar que: 

      = 1 if n = 1 ( mod 8 ) or n = 7 ( mod 8 )
(2/n) = -1 if n = 3 ( mod 8 ) or n = 5 ( mod 8 )
      = 0 otherwise
4) (a/n) = (n/a) * (-1)((a - 1)(n - 1) / 4)  if a and n are both odd.

El algoritmo: 
seleccionamos un número n para probar su primalidad y un número aleatorio a que se encuentra en el rango de [2, n-1] y calculamos su jacobiano (a/n), si n es un número primo, entonces el El jacobiano será igual al Legendre y cumplirá la condición (i) dada por Euler. Si no satisface la condición dada, entonces n es compuesto y el programa se detendrá. Al igual que cualquier otra prueba de primalidad probabilística, su precisión también es directamente proporcional al número de iteraciones. Así que ejecutamos la prueba en varias iteraciones para obtener resultados más precisos.

Nota: No nos interesa calcular el jacobiano de los números pares ya que sabemos que no son primos excepto el 2.

Pseudocódigo: 

Algorithm for Jacobian:
Step 1    //base cases omitted
Step 2     if a>n then
Step 3         return (a mod n)/n
Step 4     else

Step 5         return (-1)((a - 1)/2)((n - 1)/2)(a/n)
Step 6     endif
Algorithm for Solovay-Strassen:
Step 1    Pick a random element a < n
Step 2    if gcd(a, n) > 1 then
Step 3        return COMPOSITE
Step 4    end if
Step 5    Compute a(n - 1)/2 using repeated squaring
          and (a/n) using Jacobian algorithm.
Step 6    if (a/n) not equal to a(n - 1)/2 then
Step 7        return composite
Step 8    else
Step 9        return prime
Step 10   endif

Implementación:

C++

// C++ program to implement Solovay-Strassen
// Primality Test
#include <bits/stdc++.h>
using namespace std;
 
// modulo function to perform binary exponentiation
long long modulo(long long base, long long exponent,
                                      long long mod)
{
    long long x = 1;
    long long y = base;
    while (exponent > 0)
    {
        if (exponent % 2 == 1)
            x = (x * y) % mod;
 
        y = (y * y) % mod;
        exponent = exponent / 2;
    }
 
    return x % mod;
}
 
// To calculate Jacobian symbol of a given number
int calculateJacobian(long long a, long long n)
{
    if (!a)
        return 0;// (0/n) = 0
 
    int ans = 1;
    if (a < 0)
    {
        a = -a; // (a/n) = (-a/n)*(-1/n)
        if (n % 4 == 3)
            ans = -ans; // (-1/n) = -1 if n = 3 (mod 4)
    }
 
    if (a == 1)
        return ans;// (1/n) = 1
 
    while (a)
    {
        if (a < 0)
        {
            a = -a;// (a/n) = (-a/n)*(-1/n)
            if (n % 4 == 3)
                ans = -ans;// (-1/n) = -1 if n = 3 (mod 4)
        }
 
        while (a % 2 == 0)
        {
            a = a / 2;
            if (n % 8 == 3 || n % 8 == 5)
                ans = -ans;
 
        }
 
        swap(a, n);
 
        if (a % 4 == 3 && n % 4 == 3)
            ans = -ans;
        a = a % n;
 
        if (a > n / 2)
            a = a - n;
 
    }
 
    if (n == 1)
        return ans;
 
    return 0;
}
 
// To perform the Solovay-Strassen Primality Test
bool solovoyStrassen(long long p, int iterations)
{
    if (p < 2)
        return false;
    if (p != 2 && p % 2 == 0)
        return false;
 
    for (int i = 0; i < iterations; i++)
    {
        // Generate a random number a
        long long a = rand() % (p - 1) + 1;
        long long jacobian = (p + calculateJacobian(a, p)) % p;
        long long mod = modulo(a, (p - 1) / 2, p);
 
        if (!jacobian || mod != jacobian)
            return false;
    }
    return true;
}
 
// Driver Code
int main()
{
    int iterations = 50;
    long long num1 = 15;
    long long num2 = 13;
 
    if (solovoyStrassen(num1, iterations))
        printf("%d is prime\n",num1);
    else
        printf("%d is composite\n",num1);
 
    if (solovoyStrassen(num2, iterations))
        printf("%d is prime\n",num2);
    else
        printf("%d is composite\n",num2);
 
    return 0;
}

Java

// Java program to implement Solovay-Strassen
// Primality Test
import java.util.Scanner;
import java.util.Random;
 
class GFG{
     
// Modulo function to perform
// binary exponentiation
static long modulo(long base,
                   long exponent,
                   long mod)
{
    long x = 1;
    long y = base;
     
    while (exponent > 0)
    {
        if (exponent % 2 == 1)
            x = (x * y) % mod;
 
        y = (y * y) % mod;
        exponent = exponent / 2;
         
    }
    return x % mod;
}
 
// To calculate Jacobian symbol of
// a given number
static long calculateJacobian(long a, long n)
{
    if (n <= 0 || n % 2 == 0)
        return 0;
         
    long ans = 1L;
     
    if (a < 0)
    {
        a = -a; // (a/n) = (-a/n)*(-1/n)
        if (n % 4 == 3)
            ans = -ans; // (-1/n) = -1 if n = 3 (mod 4)
    }
     
    if (a == 1)
        return ans; // (1/n) = 1
         
    while (a != 0)
    {
        if (a < 0)
        {
            a = -a; // (a/n) = (-a/n)*(-1/n)
            if (n % 4 == 3)
                ans = -ans; // (-1/n) = -1 if n = 3 (mod 4)
        }
         
        while (a % 2 == 0)
        {
            a /= 2;
            if (n % 8 == 3 || n % 8 == 5)
                ans = -ans;
        }
 
        long temp = a;
        a = n;
        n = temp;
 
        if (a % 4 == 3 && n % 4 == 3)
            ans = -ans;
             
        a %= n;
        if (a > n / 2)
            a = a - n;
    }
     
    if (n == 1)
        return ans;
         
    return 0;
}
     
// To perform the Solovay-Strassen Primality Test
static boolean solovoyStrassen(long p,
                               int iteration)
{
    if (p < 2)
        return false;
    if (p != 2 && p % 2 == 0)
        return false;
         
    // Create Object for Random Class
    Random rand = new Random();
    for(int i = 0; i < iteration; i++)
    {
         
        // Generate a random number r
        long r = Math.abs(rand.nextLong());           
        long a = r % (p - 1) + 1;
        long jacobian = (p + calculateJacobian(a, p)) % p;
        long mod = modulo(a, (p - 1) / 2, p);
         
        if (jacobian == 0 || mod != jacobian)
            return false;
    }
    return true;       
}
 
// Driver code
public static void main (String[] args)
{
    int iter = 50;
    long num1 = 15;
    long num2 = 13;
     
    if (solovoyStrassen(num1, iter))
        System.out.println(num1 + " is prime");
    else
        System.out.println(num1 + " is composite");   
      
     if (solovoyStrassen(num2,iter))
        System.out.println(num2 + " is prime");
    else
        System.out.println(num2 + " is composite");
}
}
 
// This code is contributed by Srishtik Dutta

Python3

# Python3 program to implement Solovay-Strassen
# Primality Test
import random
 
# modulo function to perform binary
# exponentiation
def modulo(base, exponent, mod):
    x = 1;
    y = base;
    while (exponent > 0):
        if (exponent % 2 == 1):
            x = (x * y) % mod;
 
        y = (y * y) % mod;
        exponent = exponent // 2;
 
    return x % mod;
 
# To calculate Jacobian symbol of a
# given number
def calculateJacobian(a, n):
 
    if (a == 0):
        return 0;# (0/n) = 0
 
    ans = 1;
    if (a < 0):
         
        # (a/n) = (-a/n)*(-1/n)
        a = -a;
        if (n % 4 == 3):
         
            # (-1/n) = -1 if n = 3 (mod 4)
            ans = -ans;
 
    if (a == 1):
        return ans; # (1/n) = 1
 
    while (a):
        if (a < 0):
             
            # (a/n) = (-a/n)*(-1/n)
            a = -a;
            if (n % 4 == 3):
                 
                # (-1/n) = -1 if n = 3 (mod 4)
                ans = -ans;
 
        while (a % 2 == 0):
            a = a // 2;
            if (n % 8 == 3 or n % 8 == 5):
                ans = -ans;
 
        # swap
        a, n = n, a;
 
        if (a % 4 == 3 and n % 4 == 3):
            ans = -ans;
        a = a % n;
 
        if (a > n // 2):
            a = a - n;
 
    if (n == 1):
        return ans;
 
    return 0;
 
# To perform the Solovay- Strassen
# Primality Test
def solovoyStrassen(p, iterations):
 
    if (p < 2):
        return False;
    if (p != 2 and p % 2 == 0):
        return False;
 
    for i in range(iterations):
         
        # Generate a random number a
        a = random.randrange(p - 1) + 1;
        jacobian = (p + calculateJacobian(a, p)) % p;
        mod = modulo(a, (p - 1) / 2, p);
 
        if (jacobian == 0 or mod != jacobian):
            return False;
 
    return True;
 
# Driver Code
iterations = 50;
num1 = 15;
num2 = 13;
 
if (solovoyStrassen(num1, iterations)):
    print(num1, "is prime ");
else:
    print(num1, "is composite");
 
if (solovoyStrassen(num2, iterations)):
    print(num2, "is prime");
else:
    print(num2, "is composite");
 
# This code is contributed by mits

C#

/// C# program to implement Solovay-Strassen
// Primality Test
using System;
using System.Collections.Generic;  
class GFG {
     
    // Modulo function to perform
    // binary exponentiation
    static long modulo(long Base, long exponent, long mod)
    {
        long x = 1;
        long y = Base;
          
        while (exponent > 0)
        {
            if (exponent % 2 == 1)
                x = (x * y) % mod;
      
            y = (y * y) % mod;
            exponent = exponent / 2;
              
        }
        return x % mod;
    }
      
    // To calculate Jacobian symbol of
    // a given number
    static long calculateJacobian(long a, long n)
    {
        if (n <= 0 || n % 2 == 0)
            return 0;
              
        long ans = 1L;
          
        if (a < 0)
        {
            a = -a; // (a/n) = (-a/n)*(-1/n)
            if (n % 4 == 3)
                ans = -ans; // (-1/n) = -1 if n = 3 (mod 4)
        }
          
        if (a == 1)
            return ans; // (1/n) = 1
              
        while (a != 0)
        {
            if (a < 0)
            {
                a = -a; // (a/n) = (-a/n)*(-1/n)
                if (n % 4 == 3)
                    ans = -ans; // (-1/n) = -1 if n = 3 (mod 4)
            }
              
            while (a % 2 == 0)
            {
                a /= 2;
                if (n % 8 == 3 || n % 8 == 5)
                    ans = -ans;
            }
      
            long temp = a;
            a = n;
            n = temp;
      
            if (a % 4 == 3 && n % 4 == 3)
                ans = -ans;
                  
            a %= n;
            if (a > n / 2)
                a = a - n;
        }
          
        if (n == 1)
            return ans;
              
        return 0;
    }
          
    // To perform the Solovay-Strassen Primality Test
    static bool solovoyStrassen(long p, int iteration)
    {
        if (p < 2)
            return false;
        if (p != 2 && p % 2 == 0)
            return false;
              
        // Create Object for Random Class
        Random rand = new Random();
        for(int i = 0; i < iteration; i++)
        {
              
            // Generate a random number r
            long r = Math.Abs(rand.Next());           
            long a = r % (p - 1) + 1;
            long jacobian = (p + calculateJacobian(a, p)) % p;
            long mod = modulo(a, (p - 1) / 2, p);
              
            if (jacobian == 0 || mod != jacobian)
                return false;
        }
        return true;       
    }
   
  // Driver code
  static void Main()
  {
        int iter = 50;
        long num1 = 15;
        long num2 = 13;
          
        if (solovoyStrassen(num1, iter))
            Console.WriteLine(num1 + " is prime");
        else
            Console.WriteLine(num1 + " is composite");   
           
         if (solovoyStrassen(num2,iter))
            Console.WriteLine(num2 + " is prime");
        else
            Console.WriteLine(num2 + " is composite");
  }
}
 
// This code is contributed by divyeshrabadiya07

PHP

<?php
// PHP program to implement
// Solovay-Strassen Primality Test
 
// modulo function to perform
// binary exponentiation
function modulo($base, $exponent, $mod)
{
    $x = 1;
    $y = $base;
    while ($exponent > 0)
    {
        if ($exponent % 2 == 1)
            $x = ($x * $y) % $mod;
 
        $y = ($y * $y) % $mod;
        $exponent = $exponent / 2;
    }
 
    return $x % $mod;
}
 
// To calculate Jacobian
// symbol of a given number
function calculateJacobian($a, $n)
{
    if (!$a)
        return 0;// (0/n) = 0
 
    $ans = 1;
    if ($a < 0)
    {
        // (a/n) = (-a/n)*(-1/n)
        $a = -$a;
        if ($n % 4 == 3)
         
            // (-1/n) = -1 if n = 3 (mod 4)
            $ans = -$ans;
    }
 
    if ($a == 1)
        return $ans;// (1/n) = 1
 
    while ($a)
    {
        if ($a < 0)
        {
            // (a/n) = (-a/n)*(-1/n)
            $a = -$a;
            if ($n % 4 == 3)
                 
                // (-1/n) = -1 if n = 3 (mod 4)
                $ans = -$ans;
        }
 
        while ($a % 2 == 0)
        {
            $a = $a / 2;
            if ($n % 8 == 3 || $n % 8 == 5)
                $ans = -$ans;
 
        }
        //swap
        list($a, $n) = array($n, $a);
 
        if ($a % 4 == 3 && $n % 4 == 3)
            $ans = -$ans;
        $a = $a % $n;
 
        if ($a > $n / 2)
            $a = $a - $n;
 
    }
 
    if ($n == 1)
        return $ans;
 
    return 0;
}
 
// To perform the Solovay-
// Strassen Primality Test
function solovoyStrassen($p, $iterations)
{
    if ($p < 2)
        return false;
    if ($p != 2 && $p % 2 == 0)
        return false;
 
    for ($i = 0; $i < $iterations; $i++)
    {
        // Generate a random number a
        $a = rand() % ($p - 1) + 1;
        $jacobian = ($p +
                     calculateJacobian($a,
                                       $p)) % $p;
        $mod = modulo($a, ($p - 1) / 2, $p);
 
        if (!$jacobian || $mod != $jacobian)
            return false;
    }
    return true;
}
 
// Driver Code
$iterations = 50;
$num1 = 15;
$num2 = 13;
 
if (solovoyStrassen($num1, $iterations))
    echo $num1," is prime ","\n";
else
    echo $num1," is composite\n";
 
if (solovoyStrassen($num2, $iterations))
    echo $num2," is prime\n";
else
    echo $num2," is composite\n";
 
// This code is contributed by ajit
?>

Javascript

<script>
 
// Javascript program to implement Solovay-Strassen
// Primality Test
 
     
// Modulo function to perform
// binary exponentiation
function modulo( base, exponent,mod)
{
    let x = 1;
    let y = base;
     
    while (exponent > 0)
    {
        if (exponent % 2 == 1)
            x = (x * y) % mod;
 
        y = (y * y) % mod;
        exponent = Math.floor(exponent / 2);
         
    }
    return x % mod;
}
 
// To calculate Jacobian symbol of
// a given number
function calculateJacobian( a, n)
{
    if (n <= 0 || n % 2 == 0)
        return 0;
         
    let ans = 1;
     
    if (a < 0)
    {
        a = -a; // (a/n) = (-a/n)*(-1/n)
        if (n % 4 == 3)
            ans = -ans; // (-1/n) = -1 if n = 3 (mod 4)
    }
     
    if (a == 1)
        return ans; // (1/n) = 1
         
    while (a != 0)
    {
        if (a < 0)
        {
            a = -a; // (a/n) = (-a/n)*(-1/n)
            if (n % 4 == 3)
                ans = -ans; // (-1/n) = -1 if n = 3 (mod 4)
        }
         
        while (a % 2 == 0)
        {
            a = Math.floor(a/2);
            if (n % 8 == 3 || n % 8 == 5)
                ans = -ans;
        }
 
        let temp= a;
        a = n;
        n = temp;
 
        if (a % 4 == 3 && n % 4 == 3)
            ans = -ans;
             
        a %= n;
        if (a > Math.floor(n / 2))
            a = a - n;
    }
     
    if (n == 1)
        return ans;
         
    return 0;
}
     
// To perform the Solovay-Strassen Primality Test
function solovoyStrassen( p, iteration)
{
    if (p < 2)
        return false;
    if (p != 2 && p % 2 == 0)
        return false;
         
     
    for(let i = 0; i < iteration; i++)
    {
         
        // Generate a random number r
        let r = Math.floor(Math.random()* (Number.MAX_VALUE, 2) );   
        let a = r % (p - 1) + 1;
        let jacobian = (p + calculateJacobian(a, p)) % p;
        let mod = modulo(a, Math.floor((p - 1) / 2), p);
         
        if (jacobian == 0 || mod != jacobian)
            return false;
    }
    return true;   
}
 
 
// Driver Code
 
let iter = 50;
let num1 = 15;
let num2 = 13;
     
if (solovoyStrassen(num1, iter))
    document.write(num1 + " is prime"+ "</br>");
else
    document.write(num1 + " is composite" + "</br>");
     
if (solovoyStrassen(num2,iter))
    document.write(num2 + " is prime"+ "</br>");
else
    document.write(num2 + " is composite"+ "</br>");
 
</script>

Producción : 

15 is composite
13 is prime

Tiempo de ejecución: Usando algoritmos rápidos para la exponenciación modular, el tiempo de ejecución de este algoritmo es O(k· log^3 n), donde k es el número de valores diferentes que probamos.

Precisión: es posible que el algoritmo devuelva una respuesta incorrecta. Si la entrada n es de hecho prima, entonces la salida probablemente siempre será correctamente prima. Sin embargo, si la entrada n es compuesta, entonces es posible que la salida sea un primo incorrecto. El número n se llama entonces pseudoprimo de Euler-Jacobi.

Este artículo es una contribución de Palash Nigam . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *