// PTyp.java - Kapselt ein Polynom (Feld aus long) und einen Grad.

import java.math.BigInteger;


public final class PTyp
{
  public static long modulo;  // zu primtestende oder faktorisierende Zahl
  private long [] feld;        // Feld der Koeffizienten
  private int grad;           // Grad des höchsten nicht-leeren Koeffizienten



  // --------------------- 1. Konstrukturen und Objekthilfsmittel ---------------------------------

  // Konstruktoren
  public PTyp ()
  {
    feld = new long[0]; grad = -1;  // Nullpolynom
  }

  // Achtung: Koeffizientennummern steigen mit dem Index auf, d.h an [0] ist das konst. Glied
  public PTyp (long [] pFeld)
  {
    feld = pFeld;
    int i;
    // noch sicherstellen, dass alle Koeff modulo passen
    for (i = feld.length-1; i >= 0; --i) feld[i] = feld[i] % modulo;

    grad_bestimmen();
  }

  // erzeugt ein Kreisteilungspolynom X^grad - 1
  public PTyp (int p_grad)
  {
    feld = new long [p_grad+1];
    grad = p_grad; feld[grad] = 1; feld[0] = -1;
  }

  // kopiert das Objekt tief
  protected Object clone()
  {
    PTyp neu = new PTyp();
    neu.feld = (long [] ) this.feld.clone();
    neu.grad = this.grad;

    return neu;
  }



  // --------------------- 2. Ab hier Funktionen für Polynome ---------------------------------

  private void grad_bestimmen()
  {
    int i;

    // Grad ist der erstelle Koeffizient != 0
    for (i = feld.length-1; i >= 0 && feld[i] == 0; --i);
    grad = i;
  }

  // multipliziert Polynom mit Skalar
  public PTyp multSkalar (long faktor)
  {
    PTyp neu = (PTyp) this.clone(); 

    for (int i = 0; i < neu.feld.length; ++i)
    {
      // Hier kann es zu zahlenüberlauf kommen, wenn zwei long-Werte miteinander mult. werden
      neu.feld[i] = modmul (neu.feld[i], faktor);  // (neu.feld[i] * faktor) % modulo;
      if (neu.feld[i] < 0) { System.out.println ("Zahlenüberlauf " + neu.feld[i] + " und " + faktor); System.exit(1); }
    }

    return neu;
  }

  // um Zahlenüberlauf zu vermeiden
  long modmul (long e1, long e2)
  {
    if ((e1 < 0) || (e2 < 0) || (e1 >= modulo) || (e2 >= modulo))
    {
      System.out.println ("modmul: falscher Wertebereich " + e1 + " und " + e2); System.exit(1);
    }
    if (e1 == 0 || e2 == 0) return 0; // Sonderfall
    if ((e1 < Integer.MAX_VALUE) && (e2 < Integer.MAX_VALUE))
    {
      return ((e1 * e2) % modulo);  // sollte dann eigentlich reinpassen, kein Überlauf erwartet
    }
    // System.out.println ("Überlaufbehandlung " + e1 + " und " + e2);
    long summe = 0;  // Überlaufbehandlung
    while (e1 > 0)
    {
      if ((e1 & 1) == 1) summe = (summe + e2) % modulo;
      e1 = e1 >> 1; e2 = e2 << 1; if (e2 >= modulo) e2 -= modulo;
    }
    return summe;
  }

  // Polynom schieben (von hoch nach nieder)
  public PTyp schiebenRechts ()
  {
    PTyp neu = new PTyp();
    neu.grad = (this.grad < 0) ? 0 : this.grad-1;
    neu.feld = new long[neu.grad+1];
    for (int i = 0; i <= neu.grad; ++i) neu.feld[i] = this.feld[i+1];

    return neu;
  }

  // Polynom schieben (von nieder nach hoch)
  public PTyp schiebenLinks ()
  {
    PTyp neu = new PTyp();
    neu.feld = new long[this.grad+2];      
    neu.grad = this.grad+1;
    for (int i = 0; i <= this.grad; ++i) neu.feld[i+1] = this.feld[i];
    // neu.feld[0] = 0; wird autom. so init.

    return neu;
  }


  // addiert Konstante
  public PTyp addiereKonstante (long wert)
  {
    PTyp rueck = (PTyp) clone();
    if (wert == 0) return rueck;

    if (rueck.grad < 0) rueck.feld = new long[1];
    rueck.feld[0] = (rueck.feld[0] + wert) % modulo;
    rueck.grad_bestimmen(); // da sich hohe koeff auch auslöschen können

    return rueck;
  }

  // Ausgabe
  public String toString()
  {
    String erg = "";
    if (grad < 0) erg = "(Nullpolynom)";

    for (int i = grad; i >= 0; --i)
    {
      if (feld[i] != 0) 
      {
        if (erg.length() > 0) erg += " + ";
        erg += (feld[i] + "*x^" + i);
      }
    }

    return erg;
  }

  // Testet zwei Polynome, ob sie identisch sind
  public boolean equals (Object o)
  {
    if (o == this) return true;
    if (! (o instanceof PTyp)) return false;   // mag er irgendwie nicht

    PTyp vergl = (PTyp) o;
    if (this.grad != vergl.grad) return false;

    // jetzt noch die Koeffizienten vergleichen
    for (int i = 0; i <= grad; ++i)
    {
      if (this.feld[i] != vergl.feld[i]) return false;
    }

    return true;
  }

  // errechnet den Funktionswert
  long funktionswert (long eingabe)
  {
    if (this.grad < 0) return 0;  // Nullpolynom: nichts auswerten

    long erg = this.feld[this.grad];
    for (int i = this.grad - 1; i >= 0; --i)
    {
      erg = (((erg * eingabe) % this.modulo) + this.feld[i]) % this.modulo;
    }
    return erg;
  }


  // 2.b ------------------ addieren, multipl., modulo, Potenz -------------------------------------

  // addieren
  public PTyp addieren (PTyp dazu)
  {
    if (dazu.grad == -1) return this;
    else if (this.grad == -1) return dazu;  // hier keine Veränderung

    int gradNeu = (this.grad > dazu.grad) ? this.grad : dazu.grad;
    long [] feldNeu = new long [gradNeu+1];
    for (int i = 0; i <= gradNeu; ++i)
    {
      if (i > this.grad) feldNeu[i] = dazu.feld[i];
      else if (i > dazu.grad) feldNeu[i] = this.feld[i];
      else feldNeu[i] = (dazu.feld[i] + this.feld[i]) % modulo;
    }
    PTyp rueck = new PTyp(feldNeu);

    return rueck;    
  }

  // multiplizieren modulo. Einschränkung: Polynome müssen kleineren Grad als Restpolynom sein
  public PTyp multiplizieren (PTyp mal, PTyp rest)
  {
    // Was noch nicht programmiert ist:
    if (this.grad >= rest.grad || mal.grad >= rest.grad)
    {
      System.out.println ("Mult: noch nicht programmiert"); System.exit(1);
    }

    // folgendes mit ägyptischer Multiplikation, also auf addieren und schieben zurückführen
    PTyp summe = new PTyp();
    PTyp lauf1 = (PTyp) this.clone(); PTyp lauf2 = (PTyp) mal.clone();  // lauf2 vergr., lauf1 verkleinert
    while (true)
    {
      if (lauf2.grad < lauf1.grad)
      {
        PTyp hilf = lauf1; lauf1 = lauf2; lauf2 = hilf; // Größentausch !
      }
      if (lauf1.grad < 0) break;
      // System.out.println ("Hilfe: " + lauf1 + " und " + lauf2 + " und " + summe);
      summe = summe.addieren(lauf2.multSkalar(lauf1.feld[0]));
      // summe = summe.testMod(rest);  nicht nötig !
      lauf1 = lauf1.schiebenRechts();
      lauf2 = lauf2.schiebenLinks();
      lauf2 = lauf2.testMod(rest);
    }

    return summe;
  }


  // Das aktuelle Polynom modulo eines rest-Polynoms betrachten, also Grad(aktuell) <= Grad(rest)
  public PTyp testMod (PTyp rest)
  {
    // Was noch nicht programmiert ist:
    if (this.grad > rest.grad)
    {
      System.out.println ("testMod: noch nicht programmiert"); System.exit(1);
    }
    if (this.grad < rest.grad) return this;  // nichts weiter

    // Rest und Polynom haben den gleichen Grad - also abziehen
    long koeff = rest.feld[grad];
    long inv = -1;
    try
    {
      inv = (BigInteger.valueOf(koeff).modInverse(BigInteger.valueOf(modulo))).intValue();
    }
    catch (Exception ex) { System.out.println (koeff + " ist nicht invertierbar"); System.exit(1); }
    inv = (inv * this.feld[grad]) % modulo;

    PTyp neu = (PTyp) this.clone();
    for (int i = neu.feld.length-1; i >= 0; --i)
    {
      neu.feld[i] = (this.feld[i] - rest.feld[i] * inv) % modulo;
    }
    if (neu.feld[neu.grad] != 0) { System.out.println ("Logikfehler bei testMod"); System.exit(1); }

    // neuen Grad bestimmen
    neu.grad_bestimmen();

    return neu;
  }

  // modPotenz modulo
  public PTyp modPow(long exponent, PTyp rest)
  {
    if (exponent < 0) { System.out.println ("modPow: Exponent muss positiv sein"); System.exit(1); }

    long [] eins = {1};
    PTyp erg = new PTyp(eins); PTyp aktuell = this;
    while (exponent > 0)
    {
      if ((exponent & 1) == 1) erg = erg.multiplizieren(aktuell, rest);
      aktuell = aktuell.multiplizieren(aktuell, rest);
      exponent = exponent >> 1;
    }

    return erg;
  }

}