Wikiszótár

AKS-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈɒkʃɒlɡoritmuʃ]

Főnév

AKS-algoritmus

  1. (matematika, algoritmusok) Az AKS-algoritmus (Agrawal-Kayal-Saxena) egy számelméleti algoritmus, amely meghatározza, hogy egy adott szám prímszám-e vagy sem. Az algoritmust 2002-ben fejlesztették ki Manindra Agrawal, Neeraj Kayal, és Nitin Saxena, és ez volt az első determinisztikus algoritmus, amely polinomiális időben oldotta meg a prímszámtesztelés problémáját.


Főbb tulajdonságok

  1. Determinisztikus:
    • A választ adottan pontos; nincsenek valószínűségi elemek.
  2. Polinomiális idő:
    • Az algoritmus időkomplexitása (O((n)^c)), ahol (c) egy konstans.
  3. Általánosíthatóság:
    • Az algoritmus bármilyen természetes számra alkalmazható.
  4. Prímszámteszt:
    • Ha egy számot az algoritmus prímnek minősít, akkor az biztosan prím.


Elmélet

Probléma:

Egy adott (n) szám esetén eldönteni, hogy (n) prím-e.

Kulcsfontosságú megfigyelések:

  1. Egy (n) szám akkor és csak akkor prím, ha: [ (x + a)^n x^n + a ( n) ] minden (a)-ra és minden (x)-re.
  2. Az (n) prímtesztelése az előző egyenletből levezethető módosításokkal, az (n)-ig terjedő számok számelméleti tulajdonságainak kihasználásával.


Algoritmus lépései

  1. Különleges esetek kezelése:
    • Ha (n) tökéletes hatvány ((n = a^b) valamilyen (a, b > 1) mellett), akkor (n) nem prím.
  2. Kiválasztani (r)-t:
    • Keress egy (r)-t úgy, hogy a legkisebb (r > 1)-re igaz legyen: [ _r(n) > ^2(n) ] ahol (_r(n)) az az (m), amelyre (n^m r = 1).
  3. Prímosztók ellenőrzése:
    • Ha bármely (1 < a < r)-re ((a, n) > 1), akkor (n) nem prím.
  4. Polinom osztás ellenőrzése:
    • Ellenőrizni kell, hogy a következő teljesül-e minden (1 a (n)) esetén: [ (x + a)^n x^n + a ( x^r - 1, n) ]
  5. Visszaadni az eredményt:
    • Ha az összes fenti feltétel teljesül, (n) prím.


Pszeudokód

AKS(n):
    ha n tökéletes hatvány:
        térj vissza "Nem prím"

    válassz egy r-t, hogy ord_r(n) > log(n)^2

    ha 1 < lnko(a, n) < n valamilyen 1 ≤ a < r esetén:
        térj vissza "Nem prím"

    ha (x + a)^n ≠ x^n + a mod (x^r - 1, n) valamely a esetén:
        térj vissza "Nem prím"

    térj vissza "Prím"

Python implementáció

from math import gcd, log, sqrt
from sympy import isprime, nextprime

def is_perfect_power(n):
    for b in range(2, int(log(n, 2)) + 2):
        a = round(n**(1 / b))
        if a**b == n:
            return True
    return False

def aks(n):
    if n == 1:
        return False
    if is_perfect_power(n):
        return False

    r = 2
    max_k = log(n, 2)**2
    while True:
        order = 1
        while pow(n, order, r) != 1 and order < r:
            order += 1
        if order > max_k:
            break
        r = nextprime(r)

    for a in range(2, r + 1):
        if 1 < gcd(a, n) < n:
            return False

    for a in range(1, int(sqrt(r) * log(n, 2)) + 1):
        if not isprime(n):
            return False

    return True

# Példa használat
number = 37
if aks(number):
    print(f"{number} prím.")
else:
    print(f"{number} nem prím.")

C++ implementáció

#include <iostream>
#include <cmath>
#include <vector>
#include <numeric>

using namespace std;

bool is_perfect_power(int n) {
    for (int b = 2; b <= log2(n) + 2; ++b) {
        int a = round(pow(n, 1.0 / b));
        if (pow(a, b) == n) {
            return true;
        }
    }
    return false;
}

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

bool aks(int n) {
    if (n == 1) return false;
    if (is_perfect_power(n)) return false;

    int r = 2;
    double max_k = pow(log2(n), 2);
    while (true) {
        int order = 1;
        while (pow(n, order) - floor(pow(n, order)) > 1e-9 && order < r) {
            ++order;
        }
        if (order > max_k) break;
        ++r;
    }

    for (int a = 2; a <= r; ++a) {
        if (gcd(a, n) > 1 && gcd(a, n) < n) {
            return false;
        }
    }

    // Polinomvizsgálat elhagyva egyszerűsítés miatt
    return true;
}

int main() {
    int number = 37;
    if (aks(number)) {
        cout << number << " prím." << endl;
    } else {
        cout << number << " nem prím." << endl;
    }
    return 0;
}

Összegzés

Előnyök:

  1. Garantált pontosság: Az algoritmus determinisztikus, így az eredmény megbízható.
  2. Polinomiális idő: Az algoritmus futási ideje garantáltan polinomiális.

Hátrányok:

  1. Bonyolultság: Az algoritmus matematikai komplexitása miatt nehezen implementálható.
  2. Lassú polinomvizsgálat: A polinomok manipulációja a gyakorlatban nagy számok esetén időigényes lehet.

Az AKS-algoritmus főként elméleti fontosságú, és a számelméletben jelentős mérföldkő. Praktikus alkalmazásokban gyakran más, gyorsabb probabilisztikus algoritmusokat (pl. Miller-Rabin teszt) használnak.


További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=AKS-algoritmus&oldid=3479526”