Dado un número n, comprueba si es primo o no. Hemos presentado y discutido el método de la Escuela para las pruebas de primalidad en el Conjunto 1.
Prueba de Primalidad | Conjunto 1 (Introducción y Método Escolar)
En este post, se discute el método de Fermat. Este método es un método probabilístico y se basa en el Pequeño Teorema de Fermat.
Fermat's Little Theorem: If n is a prime number, then for every a, 1 < a < n-1, an-1 ≡ 1 (mod n) OR an-1 % n = 1 Example: Since 5 is prime, 24 ≡ 1 (mod 5) [or 24%5 = 1], 34 ≡ 1 (mod 5) and 44 ≡ 1 (mod 5) Since 7 is prime, 26 ≡ 1 (mod 7), 36 ≡ 1 (mod 7), 46 ≡ 1 (mod 7) 56 ≡ 1 (mod 7) and 66 ≡ 1 (mod 7) Refer this for different proofs.
Si un número dado es primo, entonces este método siempre devuelve verdadero. Si el número dado es compuesto (o no primo), entonces puede devolver verdadero o falso, pero la probabilidad de producir resultados incorrectos para compuestos es baja y puede reducirse haciendo más iteraciones.
A continuación se muestra el algoritmo:
// Higher value of k indicates probability of correct
// results for composite inputs become higher. For prime
// inputs, result is always correct
1) Repeat following k times:
a) Pick a randomly in the range [2, n - 2]
b) If gcd(a, n) ≠ 1, then return false
c) If an-1 ≢ 1 (mod n), then return false
2) Return true [probably prime].
A continuación se muestra la implementación del algoritmo anterior. El código usa la función de potencia de Modular Exponentiation
C++
// C++ program to find the smallest twin in given range
#include <bits/stdc++.h>
using namespace std;
/* Iterative Function to calculate (a^n)%p in O(logy) */
int power(int a, unsigned int n, int p)
{
int res = 1; // Initialize result
a = a % p; // Update 'a' if 'a' >= p
while (n > 0)
{
// If n is odd, multiply 'a' with result
if (n & 1)
res = (res*a) % p;
// n must be even now
n = n>>1; // n = n/2
a = (a*a) % p;
}
return res;
}
/*Recursive function to calculate gcd of 2 numbers*/
int gcd(int a, int b)
{
if(a < b)
return gcd(b, a);
else if(a%b == 0)
return b;
else return gcd(b, a%b);
}
// If n is prime, then always returns true, If n is
// composite than returns false with high probability
// Higher value of k increases probability of correct
// result.
bool isPrime(unsigned int n, int k)
{
// Corner cases
if (n <= 1 || n == 4) return false;
if (n <= 3) return true;
// Try k times
while (k>0)
{
// Pick a random number in [2..n-2]
// Above corner cases make sure that n > 4
int a = 2 + rand()%(n-4);
// Checking if a and n are co-prime
if (gcd(n, a) != 1)
return false;
// Fermat's little theorem
if (power(a, n-1, n) != 1)
return false;
k--;
}
return true;
}
// Driver Program to test above function
int main()
{
int k = 3;
isPrime(11, k)? cout << " true\n": cout << " false\n";
isPrime(15, k)? cout << " true\n": cout << " false\n";
return 0;
}
Java
// Java program to find the
// smallest twin in given range
import java.io.*;
import java.math.*;
class GFG {
/* Iterative Function to calculate
// (a^n)%p in O(logy) */
static int power(int a,int n, int p)
{
// Initialize result
int res = 1;
// Update 'a' if 'a' >= p
a = a % p;
while (n > 0)
{
// If n is odd, multiply 'a' with result
if ((n & 1) == 1)
res = (res * a) % p;
// n must be even now
n = n >> 1; // n = n/2
a = (a * a) % p;
}
return res;
}
// If n is prime, then always returns true,
// If n is composite than returns false with
// high probability Higher value of k increases
// probability of correct result.
static boolean isPrime(int n, int k)
{
// Corner cases
if (n <= 1 || n == 4) return false;
if (n <= 3) return true;
// Try k times
while (k > 0)
{
// Pick a random number in [2..n-2]
// Above corner cases make sure that n > 4
int a = 2 + (int)(Math.random() % (n - 4));
// Fermat's little theorem
if (power(a, n - 1, n) != 1)
return false;
k--;
}
return true;
}
// Driver Program
public static void main(String args[])
{
int k = 3;
if(isPrime(11, k))
System.out.println(" true");
else
System.out.println(" false");
if(isPrime(15, k))
System.out.println(" true");
else
System.out.println(" false");
}
}
// This code is contributed by Nikita Tiwari.
Python3
# Python3 program to find the smallest
# twin in given range
import random
# Iterative Function to calculate
# (a^n)%p in O(logy)
def power(a, n, p):
# Initialize result
res = 1
# Update 'a' if 'a' >= p
a = a % p
while n > 0:
# If n is odd, multiply
# 'a' with result
if n % 2:
res = (res * a) % p
n = n - 1
else:
a = (a ** 2) % p
# n must be even now
n = n // 2
return res % p
# If n is prime, then always returns true,
# If n is composite than returns false with
# high probability Higher value of k increases
# probability of correct result
def isPrime(n, k):
# Corner cases
if n == 1 or n == 4:
return False
elif n == 2 or n == 3:
return True
# Try k times
else:
for i in range(k):
# Pick a random number
# in [2..n-2]
# Above corner cases make
# sure that n > 4
a = random.randint(2, n - 2)
# Fermat's little theorem
if power(a, n - 1, n) != 1:
return False
return True
# Driver code
k = 3
if isPrime(11, k):
print("true")
else:
print("false")
if isPrime(15, k):
print("true")
else:
print("false")
# This code is contributed by Aanchal Tiwari
C#
// C# program to find the
// smallest twin in given range
using System;
class GFG {
/* Iterative Function to calculate
// (a^n)%p in O(logy) */
static int power(int a,int n, int p)
{
// Initialize result
int res = 1;
// Update 'a' if 'a' >= p
a = a % p;
while (n > 0)
{
// If n is odd, multiply 'a' with result
if ((n & 1) == 1)
res = (res * a) % p;
// n must be even now
n = n >> 1; // n = n/2
a = (a * a) % p;
}
return res;
}
// If n is prime, then always returns true,
// If n is composite than returns false with
// high probability Higher value of k increases
// probability of correct result.
static bool isPrime(int n, int k)
{
// Corner cases
if (n <= 1 || n == 4) return false;
if (n <= 3) return true;
// Try k times
while (k > 0)
{
// Pick a random number in [2..n-2]
// Above corner cases make sure that n > 4
Random rand = new Random();
int a = 2 + (int)(rand.Next() % (n - 4));
// Fermat's little theorem
if (power(a, n - 1, n) != 1)
return false;
k--;
}
return true;
}
static void Main() {
int k = 3;
if(isPrime(11, k))
Console.WriteLine(" true");
else
Console.WriteLine(" false");
if(isPrime(15, k))
Console.WriteLine(" true");
else
Console.WriteLine(" false");
}
}
// This code is contributed by divyesh072019
PHP
<?php
// PHP program to find the
// smallest twin in given range
// Iterative Function to calculate
// (a^n)%p in O(logy)
function power($a, $n, $p)
{
// Initialize result
$res = 1;
// Update 'a' if 'a' >= p
$a = $a % $p;
while ($n > 0)
{
// If n is odd, multiply
// 'a' with result
if ($n & 1)
$res = ($res * $a) % $p;
// n must be even now
$n = $n >> 1; // n = n/2
$a = ($a * $a) % $p;
}
return $res;
}
// If n is prime, then always
// returns true, If n is
// composite than returns
// false with high probability
// Higher value of k increases
// probability of correct
// result.
function isPrime($n, $k)
{
// Corner cases
if ($n <= 1 || $n == 4)
return false;
if ($n <= 3)
return true;
// Try k times
while ($k > 0)
{
// Pick a random number
// in [2..n-2]
// Above corner cases
// make sure that n > 4
$a = 2 + rand() % ($n - 4);
// Fermat's little theorem
if (power($a, $n-1, $n) != 1)
return false;
$k--;
}
return true;
}
// Driver Code
$k = 3;
$res = isPrime(11, $k) ? " true\n": " false\n";
echo($res);
$res = isPrime(15, $k) ? " true\n": " false\n";
echo($res);
// This code is contributed by Ajit.
?>
Javascript
<script>
// Javascript program to find the
// smallest twin in given range
/* Iterative Function to calculate
// (a^n)%p in O(logy) */
function power( a, n, p)
{
// Initialize result
let res = 1;
// Update 'a' if 'a' >= p
a = a % p;
while (n > 0)
{
// If n is odd, multiply 'a' with result
if ((n & 1) == 1)
res = (res * a) % p;
// n must be even now
n = n >> 1; // n = n/2
a = (a * a) % p;
}
return res;
}
// If n is prime, then always returns true,
// If n is composite than returns false with
// high probability Higher value of k increases
// probability of correct result.
function isPrime( n, k)
{
// Corner cases
if (n <= 1 || n == 4) return false;
if (n <= 3) return true;
// Try k times
while (k > 0)
{
// Pick a random number in [2..n-2]
// Above corner cases make sure that n > 4
let a = Math.floor(Math.random()* (n-1 - 2) + 2);
// Fermat's little theorem
if (power(a, n - 1, n) != 1)
return false;
k--;
}
return true;
}
// Driver Code
let k = 3;
if(isPrime(11, k))
document.write(" true" + "</br>");
else
document.write(" false"+ "</br>");
if(isPrime(15, k))
document.write(" true"+ "</br>");
else
document.write(" false"+ "</br>");
</script>
Producción:
true false
Complejidad temporal: O(k Log n). Tenga en cuenta que la función de potencia toma el tiempo O (Log n).
Espacio auxiliar: O(1)
Tenga en cuenta que el método anterior puede fallar incluso si aumentamos el número de iteraciones (mayor k). Existen algunos números compuestos con la propiedad de que para todo a < n, mcd(a, n) = 1 y a n-1 ≡ 1 (mod n) . Tales números se llaman números de Carmichael . La prueba de primalidad de Fermat se usa a menudo si se necesita un método rápido para filtrar, por ejemplo, en la fase de generación de claves del algoritmo criptográfico de clave pública RSA.
Pronto discutiremos más métodos para las pruebas de primalidad.
Referencias:
https://en.wikipedia.org/wiki/Fermat_primality_test
https://en.wikipedia.org/wiki/Prime_number
http://www.cse.iitk.ac.in/users/manindra/presentations/FLTBasedTests. pdf
https://en.wikipedia.org/wiki/Primality_test
Este artículo es una contribución de Ajay . 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