Popis AKS algoritmu

Implementace AKS algoritmu zahrnuje využití dlouhých čísel a vyžaduje znalost základních postupů teorie čísel. Nejprve se podíváme na slovní popis algoritmu, rozdělený do 6ti hlavních bodů:

pro na vstupu:

• ⇒ n je SLOŽENÉ
• Najdi nejmenší celočíselné , tak aby řád byl větší než </m>(log_2(N))^2</m>
• Pokud platí pro libovolné ⇒ n je SLOŽENÉ
• Pokud ⇒ n je PRVOČÍSLO
• Pro až do testuj .. pokud není kongruentní s ⇒ n je SLOŽENÉ
• je PRVOČÍSLO

V prvním kroku algoritmu testujeme, zda nevzniklo umocněním neznámého základu na neznámý exponent. Pro každý základ menší než odmocnina z procházíme všechny exponenty, dokud základ umocněný na exponent nepřekročí velikost , pokud nastane rovnost, je složené.

  CBigInt a(2);

  // Dokud je a^2 je mensi nez n ... zvetsuj zaklad
  while (a*a <= n) {
    CBigInt b = 2, c = A;

    // Dokud je a^b mensi nez n ... zvetsuj exponent
    while (c < n) {          

      // Pokud N = A^B, konec
      c *= a;
      if (c == n) return false;
    }    
    a++;
  }

V druhém kroku hledáme takové nejmenší, celočíselné aby řád modulo byl větší než druhá mocnina z . Příčemž řádem čísla rozumíme exponent, na který musíme umocnit číslo , aby byl výsledek kongruentní číslu .

K nalezení řádu použijeme Eulerovu větu, která nám říká, že pokud , jsou nesoudělná čísla a platí umocněno na je kongruentní číslu , pak řád je menší roven , kde je Eulerova funkce aplikována na . Eulerova funkce čísla vrací počet čísel nesoudělných s číslem z množiny {1,2..r}.

Druhý krok můžeme sloučit s krokem třetím, při hledání tedy zároveň zkoušíme, zda není náhodou soudělné s aktuálním hodnotou v . Vycházíme z toho že dvě čísla jsou soudělná pokud se jejich největší společný dělitel nerovná jedné.

  CBigInt r(2), tmpLog(CBigInt::log2pow(n, 2));

  while (r < n) {

    // Pokud je n soudelne s libovolnym r, konec (n neni prvocislo)
    if (CIntMath::findGCD(r, n) != 1) return false;    

    // Pokud je r soudelne s n, konec, n je slozene 
    CBigInt tmpGCD = CIntMath::findGCD(r, n);

    if ((tmpGCD > 1) && (tmpGCD < n)) return false;
    if ((CIntMath::fastExp(n, d, r) == (CBigInt(1) % r)) && (d > tmpLog)) break;    
    r++;
  }

Ve čtvrtém kroku pouze porovnáme a námi nalezené , pokud by bylo , n je prvočíslo.

  if (n <= r) return true;

Pátý krok představuje časově nejnáročnější část algoritmu, zároveň je i poněkud náročnější na implementaci, než předešlé kroky. Zbývá nám prověřit, zda je polynom kongruentní s polynomem v okruhu zbytkových tříd . Pokud je tato podmínka splněna pro všechna z množiny {1,.. }, kde je celá část z logaritmu o základu 2, potom n je prvočíslo.

  a = 1; 

  while (a < CIntMath::eulerFunc(r) * log2(n)) {    

    CPolynom<CBigInt, CBigInt> p1, p2;

    // Polynom1 = (x + a)^n
    p1.clearItems();
    p1.setItem(1, 1);
    p1.setItem(0, a);

    // Polynom2 = x^n + a
    p2.clearItems();
    p2.setItem(n, 1);
    p2.setItem(0, a);

    if (CIntMath::fastExp(p1, n, r, n) != CIntMath::fastExp(p2, 1, r, n)) return false;
    a++;
  }