// Polynom.java - Rechnereien mit Polynomen modolo einer Zahl und Polynom
// Diese Klasse braucht noch die Klasse PTyp
// Zwei mögliche Parameter: 1) Grad des kreisteilungspolynoms 2) zu testende Zahl
// Aufruf: "java Polynom 3 11311"   # Testet Primzahl 11311 modulo (X^3 - 1)

import java.math.BigInteger;

public class Polynom
{
  private boolean AUSGABE = true;

  // Haupteinsprungpunkt für VM
  public static void main (String [] args)
  {
    // Es sind zwei Eingabeparameter nötig: die Zahl und ein Grad für das modulo-Polynom
    if (args.length == 0) { System.out.println ("Syntax: java Polynom <Grad> <Zahl>"); return; }
    int r = (args.length >= 1) ? Integer.parseInt(args[0]) : 3;
    long zahl = (args.length >= 2) ? new Long(args[1]).longValue() : 13; 
    if (r < 1) { System.out.println ("Modulo-Polynom muss mind. vom Grad 1 sein"); return; }
    if (zahl < 2) { System.out.println ("Testzahl muss mind. 2 sein"); return; }
    if (r > Math.log(zahl) * Math.log(zahl)) { System.out.println ("Grad hat keinen plausiblen Wert"); return; }

    if (args.length >= 2) 
    {  // nur die spezielle Zahl
       boolean istprim =new Polynom().aks_prim(zahl, r); System.out.println ("Zahl ist " + (istprim ? "prim" : "zusammengesetzt") );
    }
    else 
    { // Alle Zahlen in einem Bereich
      new Polynom().vergleich(r);
    }
  }

  // vergleicht den von Java angebotenen Wert mit AKS
  void vergleich (int r)
  {
    for (int a = 3; a < 1000000; a += 2)
    {
      boolean p1 = BigInteger.valueOf(a).isProbablePrime(r);
      boolean p2 = new Polynom().aks_prim(a, r);
      if (p1 != p2) System.out.println ("Unterschied bei " + a + ", Java " + p1 + ", AKS " + p2);
    }
  }

  // Testet die Primzahl "zahl" mit dem Verfahren nach Agrawal, Kayal, Saxena (AKS). r ist der Grad des Kreisteilungspolynoms
  public boolean aks_prim (long zahl, int r)
  {
    PTyp.modulo = zahl;
    // int r = 3; // ((int) Math.log(zahl)) + 1;
    int anzOffsets = 1;  // r

    PTyp rest = new PTyp(r);
    // System.out.println ("Kreisteilungspolynom vom Grad " + r);

    for (int offset = 1; offset <= anzOffsets; ++offset)
    {
      // (X + offset)^n == X^n + offset mod (n, Q), Q = X^r - 1 Kreisteilungspolynom
      // linke Seite (X + offset)^n mod (n, Q)
      long links [] = {offset, 1};
      PTyp basis = new PTyp(links);
      PTyp erg = basis.modPow(zahl, rest);

      // rechte Seite X^n + offset == (X^(n%r) + offset) mod (n, Q), aber nur wenn Q Ktp !
      int grad_mod = (int) (zahl % r);
      long rechts [] = new long [grad_mod+1]; rechts[grad_mod] = 1;
      PTyp erg2 = new PTyp(rechts);
      erg2 = erg2.addiereKonstante (offset);

      if (AUSGABE) System.out.println (erg + " und " + erg2);
      if (! erg.equals(erg2)) return false;
    } // Ende for

    return true;
  }
}