// ECM.java: y^2 = x^3 + a*x + b
// Es wird ein kgv einer Anzahl von Zahlen gebildet, n+1 hat sich hier nicht als sinnvoll erwiesen !
// Nach Beobachtung mit schwierigen Zahlen ist ein ggT häufiger als eine gefundene Ordnung,
// und ggt häufig, wenn Diskr durch 4 oder 27 teilbar, bzw ggT(x, b) > 1. Diese Kurven sollten
// also bevorzugt angelegt werden. Das Jacobi-Symbol für die Det. scheint keinen Einfluss zu haben

import java.math.BigInteger;


public final class ECM2 extends ECM_Basis // optimierte Variante
{
  private static BigInteger grenze;    // Die Schranke für multSkalar
  private static final BigInteger VIER = BigInteger.valueOf(4);
  private static final BigInteger ACHT = BigInteger.valueOf(8);
  private static final BigInteger VIERUNDSECHZIG = BigInteger.valueOf(64);
  private final static boolean ABBRUCHTREFFER = true;  // Ende, wenn ggT gefunden
  private static final boolean DEBUGENDP = false;  // Endpunkte anzeigen
  private static final boolean DEBUGK = false;  // die erzeugten Kurven anzeigen
  private static int zahl_bis;  // wird bei Kettenbruch heraufgesetzt
  private static final boolean modusMitDreiLoesungen = true;
  private static final int ANZ_KURVEN = 100;
  private static int modusGrenze =  3;


  // Einsprungpunkt
  public static void main (String [] args) throws Exception
  {
    // test_ordnung();

    if (args.length >= 2)
    {
      int n1 = Integer.parseInt(args[0]);
      int n2 = Integer.parseInt(args[1]);
      BigInteger p1 = PrimGenerator.erzeugePrimzahl(n1, false);
      BigInteger p2 = PrimGenerator.erzeugePrimzahl(n2, false);
      ECM2.n = p1.multiply(p2);  // nicht so "schwere"
      // ECM2.n = PrimGenerator.hole_rsa_zahl(n1, n2);
      System.out.println("Zahl ist " + ECM2.n);
    }
    else if (args.length >= 1)
    {
      if (args[0].indexOf("-") >= 0) { System.out.println("Zahl muss positiv sein"); System.exit(1); }
      ECM2.n = new BigInteger(args[0]);  // diese Zahl übernehmen
    }
    else
    {
      System.out.println ("Syntax: ECM2 (<Zahl> | <BitLaenge 1><BitLaenge 2>)"); System.exit(1);
    }
    ECM2.rest8 = n.remainder(ACHT).intValue();

    // Vergrößerungsfaktor: über die Umgebung ermitteln
    String s_f = System.getProperties().getProperty("faktor"); // zahl_bis = faktor * log(n)^2
    if (s_f != null)
    {
      double neu = new Double(s_f).doubleValue();
      if (neu > 0) { grenz_faktor = neu; faktor_schritt = neu; System.out.println("Grenzfaktor gesetzt auf " + neu); }
    }

     // Schwelle initial berechnen, später ggf. anpassen ...
    zahl_bis = grenze_berechnen((short)3);  // berechnet die Größe der Schwelle B
    // zahl_bis = 5;  // f. Testzwecke Grenze runter setzen
    grenze = kgv_bis(BigInteger.ONE, 1, zahl_bis);
    // System.out.println("Grenze ist " + grenze);

    // günstigen Spezialfall abtesten
    boolean erl = test_spezialfall();
    if (erl && ABBRUCHTREFFER) return;

    // Erzeugung von Kurven starten: Kettenbruchverfahren zum Erzeugen von Kurven
    // DEBUG=true;
    erzeugen_kettenbruch();
  }

  // Konstrukturen
  public ECM2 (int para_a, int para_b) throws Logik_Fehler
  {
    super (para_a, para_b);
  }
  public ECM2 (BigInteger para_a, BigInteger para_b) throws Logik_Fehler
  {
    super (para_a, para_b);
  }

  // Tests und Warnungen
  private static void test_init()
  {
    if (n == null || grenze == null) { System.out.println ("n oder Grenze nicht richtig initalisiert"); System.exit(1); }

    if (n.isProbablePrime(1))
    {
      System.out.println (n + " ist wahrsch. eine Primzahl ...");
    }
  }

  // Strategien, um Kurven anzulegen

  // Testet bestimme Spezialfälle, welche möglichst keine Ordnung haben bzw. die Ordnung bekannt ist
  public static boolean test_spezialfall()
  {
    test_init();

    try
    {
      ECM2 kurve = null; Paar_ECM p = null, rueck=null;

      // 1) beste Kurve für b == 0
      kurve = new ECM2(-15, 0);
      p = new Paar_ECM(4, 2);
      System.out.println ("Starte Kurve a=-15 und b=0");

      System.out.println ("  dieser Spezialfall mit bek. Ordnung");
      rueck = kurve.multSkalar(n.add(BigInteger.ONE), p);  // wenn ggT, dann rueck == null
      if (DEBUGENDP && rueck != null) System.out.println (p + " --> " + rueck);
      else if (rueck == null && ABBRUCHTREFFER)
      {
        System.out.println("Punkt hat 3 Lösungen: " + kurve.punkt_drei_loesung(p));
        return true;  // ggT
      }
      // else Leider kein ggT.
      if (rueck != null && n.testBit(0) && n.testBit(1))
      {
        // 3 mod 4, hier muss rueck das neutrale Element sein, da Ordnung n+1 genommen
        // bei
        if (! rueck.istNeutral()) throw new RuntimeException("Erwartet neutrales Element, erhalten " + rueck);
      }

      // 2)
      System.out.println ("  dieser Speziallfall mit unbek. Ordnung");
      rueck = kurve.multSkalar(grenze, p);  // wenn ggT, dann rueck == null
      if (DEBUGENDP && rueck != null) System.out.println (p + " --> " + rueck);
      else if (rueck == null && ABBRUCHTREFFER)
      {
        System.out.println("Punkt hat 3 Lösungen: " + kurve.punkt_drei_loesung(p));
        return true;  // ggT
      }
      // else Leider kein ggT.

      // 3) beste Kurve für b != 0
      kurve = new ECM2(-17, -4);
      p = new Paar_ECM(5, 6);
      System.out.println ("Starte Kurve a=-17 und b=-4");

      rueck = kurve.multSkalar(grenze, p);  // wenn ggT, dann rueck == null
      if (DEBUGENDP && rueck != null) System.out.println (p + " --> " + rueck);
      else if (rueck == null && ABBRUCHTREFFER)
      {
        System.out.println("Punkt hat 3 Lösungen: " + kurve.punkt_drei_loesung(p));
        return true;  // ggT
      }
      // else Leider kein ggT.

      // 4) singuläre Kurve für b != 0. Ordnungn sollte n/n+2 bei zusammen gesetzt sein,
      // n-1/n+1 bei prim, unbek. dabei, in welchem Fall
      kurve = new ECM2(-3, +2); boolean hatNeutral = false;
      p = new Paar_ECM(2, 2);
      System.out.println ("Starte Kurve a=-3 und b=2");

      final boolean istPrim = n.isProbablePrime(3);
      BigInteger ord1 = istPrim ? n.subtract(BigInteger.ONE) : n;
      BigInteger ord2 = istPrim ? n.add(BigInteger.ONE) : n.add(BigInteger.valueOf(2));

      rueck = kurve.multSkalar(ord1, p);  // wenn ggT, dann rueck == null
      if (rueck == null || rueck.istNeutral()) hatNeutral = true; // auch ggT
      if (DEBUGENDP && rueck != null) System.out.println (p + " --> " + rueck);
      else if (rueck == null && ABBRUCHTREFFER)
      {
        System.out.println("Punkt hat 3 Lösungen: " + kurve.punkt_drei_loesung(p));
        return true;  // ggT
      }
      // else Leider kein ggT.

      rueck = kurve.multSkalar(ord2, p);  // wenn ggT, dann rueck == null
      if (rueck == null || rueck.istNeutral()) hatNeutral = true; // auch ggT
      if (DEBUGENDP && rueck != null) System.out.println (p + " --> " + rueck);
      else if (rueck == null && ABBRUCHTREFFER)
      {
        System.out.println("Punkt hat 3 Lösungen: " + kurve.punkt_drei_loesung(p));
        return true;  // ggT
      }
      // else Leider kein ggT.
      if (! hatNeutral && !istPrim) throw new RuntimeException("singuläre Kurve hat keine bekannte Ordnung"); // da Prim == wahr nicht 100% sicher


      //System.out.println("Start Test");
      //BigInteger test = BigInteger.valueOf(1000);
      //BigInteger erg = kurve.sucheBabyStepGiantStep(p, test);
      //System.out.println("Ende Test");


    }
    catch (Exception ex) { System.out.println(ex); }

    return false;
  }

  // Berechnet Wurzel ganzzahlig nach Heron
  private static BigInteger holeWurzel(BigInteger wert)
  {
    BigInteger wurzel = BigInteger.ONE; wurzel = wurzel.setBit(wert.bitLength() >> 1);
    do
    {
      BigInteger neu = (wurzel.add(wert.divide(wurzel))).shiftRight(1);
      if (wurzel.equals(neu)) break; // Konvergenz
      if (wurzel.equals(neu.subtract(BigInteger.ONE)))
      {
        // fertig, wenn eingeschlossen bei neu = wurzel+1
        if (wurzel.multiply(wurzel).compareTo(wert) <= 0 &&
            neu.multiply(neu).compareTo(wert) > 0) break;
      }
      wurzel = neu;
    } while (true);

    return wurzel;
  }

  enum Kurve_Rueck {GGT, NEUTRAL, IGNORIERT, SONST};

  // erzeugt Kurven mithilfe von Kettenbrüchen
  public static void erzeugen_kettenbruch()
  {
    test_init();

    // Wurzel (abgerundet) hier berechen, mit Heron (Startwert: etwa die Hälfte der Bitzahl)
    BigInteger wurzel = holeWurzel(n);
    BigInteger vergl = wurzel.multiply(wurzel);
    if (vergl.equals(n))
    {
      System.out.println ("n ist Quadratzahl, hier ist das Kettenbruchverfahren nicht geeignet"); return;
    }
    if (DEBUG) System.out.println ("Wurzel abgerundet ist " + wurzel);

    boolean istQuadrat = false; // der nächste ist kein Quadrat
    BigInteger a = BigInteger.ZERO; BigInteger b = BigInteger.ONE;
    BigInteger w1 = BigInteger.ZERO; BigInteger w2 = BigInteger.ONE; int anzProRunde = 0 ;
    BigInteger dar [];   // Division und Rest in einem Schritt
    BigInteger bNeu, aNeu, wNeu, erg;

    boolean ist1Mod4 = (n.and(DREI).intValue() == 1);

    long anzKurven = 1; // wg. Spezialfall (3,0) oben
    // Lasse Kettenbruch laufen
    long start = System.currentTimeMillis();
    while (true )
    {
      dar = (wurzel.add(a)).divideAndRemainder(b);
      erg = dar[0];
      aNeu = wurzel.subtract(dar[1]); dar = null;
      bNeu = (n.subtract(aNeu.multiply(aNeu))).divide(b);  // b(neu)
      if (DEBUG) System.out.println ("a=" + aNeu.toString() + ", b=" + bNeu.toString());

      // Wurzel noch aktualisieren
      wNeu = erg.equals(BigInteger.ONE) ? w2 : w2.multiply(erg).remainder(n);
      wNeu = wNeu.add(w1); if (wNeu.compareTo(n) >= 0) wNeu = wNeu.subtract(n);

      // Suche noch nach Periodenmitte
      if (ist1Mod4)
      {
        if (bNeu.equals(b))
        {
          System.out.println ("\n@@@\nPeriodenmitte ohne Mittelelement\n@@@"); break;
        }
      }
      // das nächste kann wahrs. bei 1&3 mod 4 auftreten
      {
        if (aNeu.equals(a))
        {
          System.out.println ("\n@@@\nPeriodenmitte mit Mittelelement " + b.toString() + "\n@@@"); break;
        }
      }

      // generiert aus diesen Daten eine Kurve
      try
      {
        Kurve_Rueck rueck = berechne_kurve (w2, wNeu, b, bNeu, istQuadrat);
        if ((rueck == Kurve_Rueck.GGT) && ABBRUCHTREFFER)
        {
          System.out.println ("Bei " + n + " Anzahl ECM-Kurven: " + anzKurven); break;
        }
        if (rueck == Kurve_Rueck.GGT)
        {
          anzProRunde++;
        }
        if (rueck != Kurve_Rueck.IGNORIERT)
        {
          ++anzKurven;
        }
        if (rueck == Kurve_Rueck.NEUTRAL) System.out.print("!");

        // Erhöhung des Exponenten nach gewisser Zeit bei Modus > 3, wenn nichts gef. wurde:
        if ((rueck != Kurve_Rueck.IGNORIERT) && modusGrenze > 3 && ((anzKurven % ANZ_KURVEN) == 0))
        {
          if (! ABBRUCHTREFFER)
          {
            System.out.println("Anzahl pro Runde bei " + zahl_bis + ": " + anzProRunde);
            anzProRunde = 0;
          }

          grenz_faktor += faktor_schritt;
          int zahl_bis_neu = grenze_berechnen((short)modusGrenze );  // berechnet die Größe der Schwelle B
          BigInteger grenze_neu = kgv_bis(grenze, zahl_bis+1, zahl_bis_neu);
          System.out.println (zahl_bis + " --> " + zahl_bis_neu);
          zahl_bis = zahl_bis_neu; grenze = grenze_neu;

          test_spezialfall();
        }
        else if ((anzKurven % ANZ_KURVEN) == 0)
        {
          System.out.print("-"); // Fortschrittsanzeige !
        }
      }
      catch (Logik_Fehler ex) { System.out.println ("Logikfehler: " + ex.getMessage()); }

      w1 = w2; w2 = wNeu; b = bNeu; a = aNeu;
      if (DEBUG) System.out.println ("Paar: " + w2.toString() + " --> " + b.toString() );
      istQuadrat = !istQuadrat;
    } // Ende Lauf Kettenbruch

    long ende = System.currentTimeMillis();
    System.out.println ("Anzahl Sek: " + ((long) ((ende - start) / 10)) / 100.0 );

  } // Ende erzeugen_kettenbruch


  // bekommt zwei Paare von Wurzel und Quadrat modulo n und errechnet daraus die Parameter a und b für eine ellipt. Kurve
  // Vorbedingung aus Kettenbruch:
  // w2^2 = b mod n,  wNeu^2 = bNeu mod n, bei einem rechts noch Vorzeichen umdrehen.
  private static Kurve_Rueck berechne_kurve(BigInteger w2, BigInteger wNeu, BigInteger b, BigInteger bNeu, boolean zweitesIstQuadrat) throws Logik_Fehler
  {
    if (!zweitesIstQuadrat) bNeu = bNeu.negate();
    else b = b.negate();
    if (DEBUG) System.out.println (w2 + " --> " + b);
    if (DEBUG) System.out.println (wNeu + " --> " + bNeu);

    // aus den beiden Paaren Kurve erzeugen, also hier a und c bestimmen. y berechnet, für x Wert 1 und 2,4 fest gewählt
    // Am.: die symmetrische Kurve mit konstanter Koeffizient=0 ist gut, was die Minimierung
    // der Ordnung betrifft. Deren Bestimmung aus zwei Punkte erfordert i.A. aber das Lösen einer quadr. Gleichung,
    // deshalb werden x entsprechend gesetzt, und dann auf die lin. Parameter geschlossen.

    Paar_ECM p1 = new Paar_ECM(BigInteger.ONE, w2); BigInteger aECM, bECM; Paar_ECM p2;
    {
      // b im allgemeinen != 0
      BigInteger rechts1 = b.subtract(BigInteger.ONE);
      // w2^2 = b = 1^3 + a + c
      // wNeu^2 = bNeu = 2^3 + a*2 + c  bzw. 4^3 + a*4 + c
      // Verbesserungsmöglichkeit: wenn Jac(2,n) == -1, dann nicht x=2 nehmen!
      if (rest8 == 1 || rest8 == 7)
      {
        p2 = new Paar_ECM(ZWEI, wNeu);
        // --> lineares Gleichungssystem der Variablen a und b der Kurve
        BigInteger rechts2 = bNeu.subtract(ACHT);
        aECM = rechts2.subtract(rechts1);
      }
      else
      {
        p2 = new Paar_ECM(VIER, wNeu);
        // --> lineares Gleichungssystem der Variablen a und b der Kurve
        BigInteger rechts2 = bNeu.subtract(VIERUNDSECHZIG);
        aECM = rechts2.subtract(rechts1);  // noch durch 3 teilen
        int rest = aECM.remainder(DREI).intValue();
        if (rest != 0) { aECM = aECM.add(n); rest = aECM.remainder(DREI).intValue(); }
        if (rest != 0) { aECM = aECM.add(n); rest = aECM.remainder(DREI).intValue(); }
        if (rest != 0) { System.out.println("Ist nicht durch 3 teilbar"); return Kurve_Rueck.SONST; /* 3|n ! */ }
        aECM = aECM.divide(DREI);  // sollte ganzz. teilbar sein
      }
      bECM = rechts1.subtract(aECM);

      // Wertebereich anpassen, für kompaktere Anzeige ...
    }

    ECM2 kurve = new ECM2(aECM, bECM);
    if (modusMitDreiLoesungen)
    {
      // Anhand von Heuristiken zur Minimierung der Gruppenordnung
      // beide Punkte sollen nicht drei Lösungen haben
      if (kurve.punkt_drei_loesung(p1) && (p2 == null || kurve.punkt_drei_loesung(p2)) )
      {
        return Kurve_Rueck.IGNORIERT;
      }
    }
    if (DEBUGK) System.out.println ("Starte Kurve a=" + aECM + " und b=" + bECM);

    // 2 Multiplikationsvarianten nehmen, bei einigen Zahlen dann schneller; ob erst Skalar2 und dann Skalar schneller ist, ist wechselnd.
    Paar_ECM erg = kurve.multSkalar(grenze, p1);
    // Wert nochmals mit anderer Multiplikationsreihenfolge aufrufen, damit oft weniger Kurven notwendig !
    if (erg != null) erg = kurve.multSkalar2(grenze, erg); //if (erg != null && erg2 != null && !erg.x.equals(erg2.x)) throw new Logik_Fehler("Multiplizierung: " + erg + " und " + erg2);

    // Nachzustand: ggT gefunden, dann Rückgabe null, sonst konkreter Wert
    if (erg == null)
    {
      System.out.println ("Kurve mit a=" + aECM + " und b=" + bECM +":");

      //grenzeOptimieren(kurve, p1, true);

      System.out.println ("Punkt 1 hat 3 Lösungen: " + kurve.punkt_drei_loesung(p1));
      if (p2 != null) System.out.println ("Punkt 2 hat 3 Lösungen: " + kurve.punkt_drei_loesung(p2));
      return Kurve_Rueck.GGT; // Kurve_Rueck.SONST;
    }
    if (erg.istNeutral()) return Kurve_Rueck.NEUTRAL;
    if (DEBUGENDP) System.out.println ("Erg --> " + erg);

    kurve.teste_punkt(erg);  // nur Test
    // Was macht man nun mit erg ?
    // Wurzel ziehen y^2 brachte bei 60-Bit-Zahlen nie ein neues Ergebnis
    // nicht ab 0, sondern ab n+1 rückwärts gehen(k * -p); brachte nie Erfolg

    return Kurve_Rueck.SONST;
  }


  // es liegt ein ggT vor, wenn Grenze verwendet wird. kann man hier Faktoren rauswerfen und bekommt trotzdem noch ggT ?
  private static void grenzeOptimieren(ECM2 kurve, Paar_ECM p1, boolean skalar2) throws Logik_Fehler
  {
    BigInteger grenze_lokal = grenze;
    boolean veraendert;
    GGTAUSGABE = false;

    do
    {
      veraendert = false; System.out.print(".");
      for (int lauf = 2; lauf <= zahl_bis; lauf += 2)
      {
        if (lauf == 4) lauf =  3;
        BigInteger ak = BigInteger.valueOf(lauf);
        if (! ak.isProbablePrime(2)) continue;
        BigInteger was = grenze_lokal;
        while (was.remainder(ak).equals(BigInteger.ZERO)) { was = was.divide(ak); }  // Potenz aller Primfaktoren raus
        if (was.equals(grenze_lokal)) continue;
        Paar_ECM erg = (skalar2 ? kurve.multSkalar2(was, p1) : kurve.multSkalar(was, p1));
        if (erg == null)
        {
          /*System.out.println("Raus: " + ak);*/ grenze_lokal = was; veraendert = true; // Faktoren, welche raus können, sind beides QR und NQR, auch bei den notw. Faktoren
        }
      }
    } while (veraendert);  // Ende, wenn es gar keine Verbesserung mehr gibt
    if (! grenze_lokal.equals(grenze))
    {
      System.out.println("Optimierbar " + grenze + " --> " + grenze_lokal);
      System.out.println("a=" + kurve.a + ", b = " + kurve.b);
    }
    GGTAUSGABE = true;
  }


  // es wird systematisch von unten die kleinste Grenze gesucht, bei welcher ein ggT auftritt; momentan Aufruf nicht praktikabel
  // public static void grenzeMinimal(ECM2 kurve, Paar_ECM p1) throws Logik_Fehler


}