Efektivita AKS algoritmu

Nezaujatému pozorovateli se nyní může zdát, že AKS algortimus je až příliš složitý. Vezměme si například triviální algoritmus, vycházející z definice prvočísla, která nám říká, že prvočíslo je takové přirozené číslo, větší než jedna, které je dělitelné pouze samo sebou, nebo číslem jedna. Z toho vyplývá, že pokud není dané přirozené číslo N beze zbytku dělitelné žádným číslem z množiny {2,3...N/2} je prvočíslem. Celý algoritmus by šel zapsat takto:

  bool isPrime(int n) {
    int p(n >> 1);
    while (n % p) p--;
    return !(--p);
  }

V takto navrženém algoritmu musíme v nejhorším případě projít n/2 čísel, závislost počtu průchodů na velikosti n, si můžeme prohlédnout na (obr1) (závislost f1). Časová složitost AKS algoritmu se pohybuje kolem (log N)^12 (závislost f2). Z Obr1. je tedy patrné, že od určité hranice začne být AKS algoritmus efektivnější. Na druhou stranu si můžeme všimnout, že ona “určitá hranice” leží kdesy za 2*10^20, což zatím na běžném počítači není možné za rozumný čas prověřit.