A Miller-Rabin prímteszt egy véletlenített algoritmus, amely nagy számok prímtesztelésére szolgál. Ez az algoritmus a Fermat-teszt kiterjesztése, amelyet a prímek pontosabb ellenőrzésére terveztek, és képes az összetett számok kiszűrésére nagy hatékonysággal.
Adott egy (n > 2) egész szám, a cél annak meghatározása, hogy (n): - Valószínűsíthetően prím (lehetséges prím), - vagy biztosan összetett.
A Miller-Rabin algoritmus a következő tételekre épít:
MillerRabin(n, k):
Írd fel n-1 = 2^s * d alakban
ismételd k alkalommal:
Válassz véletlen a számot tartományból
x = a^d mod n
ha x == 1 vagy x == n-1:
folytasd a következő iterációval
ismételd (s-1) alkalommal:
x = x^2 mod n
ha x == n-1:
folytasd a következő iterációval
ha egyik feltétel sem teljesült:
n biztosan összetett
n valószínűleg prím
import random
def miller_rabin(n, k=5):
if n <= 1:
return False
if n <= 3:
return True
if n % 2 == 0:
return False
# Írd fel n-1 = 2^s * d alakban
s, d = 0, n - 1
while d % 2 == 0:
s += 1
d //= 2
def is_composite(a):
x = pow(a, d, n)
if x == 1 or x == n - 1:
return False
for _ in range(s - 1):
x = pow(x, 2, n)
if x == n - 1:
return False
return True
# Véletlen tesztek
for _ in range(k):
a = random.randint(2, n - 2)
if is_composite(a):
return False
return True
# Példa használat
n = 561 # Összetett szám
print(f"A {n} szám prím? {'Igen' if miller_rabin(n) else 'Nem'}")
Kimenet:
A 561 szám prím? Nem
#include <iostream>
#include <cstdlib>
#include <cmath>
using namespace std;
bool miller_rabin(long long n, int k = 5) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0) return false;
// Írd fel n-1 = 2^s * d alakban
long long d = n - 1;
int s = 0;
while (d % 2 == 0) {
d /= 2;
s++;
}
auto is_composite = (long long a) {
long long x = pow(a, d) - (long long)(pow(a, d) / n) * n;
if (x == 1 || x == n - 1) return false;
for (int r = 1; r < s; ++r) {
x = (x * x) % n;
if (x == n - 1) return false;
}
return true;
};
// Véletlen tesztek
for (int i = 0; i < k; ++i) {
long long a = 2 + rand() % (n - 3);
if (is_composite(a)) return false;
}
return true;
}
int main() {
long long n = 561; // Összetett szám
cout << "A " << n << " szám prím? " << (miller_rabin(n) ? "Igen" : "Nem") << endl;
return 0;
}
Kimenet:
A 561 szám prím? Nem
A Miller-Rabin prímteszt egy hatékony és széles körben alkalmazott algoritmus, amely nagy számok gyors prímtesztelését teszi lehetővé. Bár nem determinisztikus, a gyakorlatban rendkívül megbízható, ezért elengedhetetlen eszköz a modern kriptográfiában és matematikai alkalmazásokban.