import java.util.Vector;
import java.lang.Math;
import java.io.*;

class mathe6 {
  public static void main(String [] args) {

    //*****************************************//
    // Hier die nächsten vier Zahlen anpassen //
    //*****************************************//

    int p = 107;
    int q = 181;
    int e = 4719;   
    int msg = 8630;   // Hier gehört die zu entschlüsselnde Zahl hin

    //****************************************//
    // Ab hier nichts mehr ändern! Hände weg! //
    // Hier werden nötige Zahlen berechnet    //
    //****************************************//

    int N = p*q;                // Man berechne die Zahl N
    int PhiN = (p-1)*(q-1);     // sowie Phi von N

    int iInverse;               // beinhaltet später die Inverse aus dem Erweiterten Euklid

    String sAusgabe = "";

    sAusgabe += "  Javaprogramm zum Miniprojekt 6, (c) '02 Martin Kuhlmann ";
    sAusgabe += "\r\n";
    sAusgabe += "===========================================================";
    sAusgabe += "\r\n";
    sAusgabe += "\r\n";

    sAusgabe += " Wir haben folgende Zahlen:\r\n";
    sAusgabe += " --------------------------\r\n";
    sAusgabe += "\r\n";

    sAusgabe += "      p = "+p+"\t q = "+q+"\r\n";
    sAusgabe += "      e = "+e+"\r\n";
    sAusgabe += "      N = p * q = "+N+"\r\n";
    sAusgabe += " Phi(N) = Phi(p*q) = (p-1)*(q-1) = "+PhiN+"\r\n";
    sAusgabe += "    msg = "+msg+"\r\n";
    sAusgabe += "\r\n";
    sAusgabe += "\r\n";

    // beinhaltet paarweise zuerst den Wert der Binärdarstellung
    // sowie dahinter den Wert der Repeated Squares
    //   x    y
    //   |    |
    //   v    v
    Vector vBinViewRepSquares = new Vector();

    // beinhaltet später die Unter- bzw Obergrenze,
    // bis zu der die binäre Darstellung sowie die Repeated Squares
    // berechnet werden müssen
    int iGrenze; 
                 
    //****************************************************//
    // Errechnen des Inversen von e Mod (phi(N))          //
    // mit Hilfe des Erweiterten Euklidischen Algorithmus //
    //****************************************************//
    {

      sAusgabe += " Nun berechnen wir das Inverse von e Mod (Phi(N))\r\n";
      sAusgabe += " --------------------------------------------------\r\n";
      sAusgabe += "\r\n";
      sAusgabe += " Und das machen wir mit Hilfe des Erweiterten Euklidischen\r\n";
      sAusgabe += " Algorithmus, d.h. wir nehmen die Zahlen e und Phi(N) dazu\r\n";
      sAusgabe += " und erhalten als Ergebnis rechts in der letzten eckigen\r\n";
      sAusgabe += " Klammer die Zahl d, mit der wir msg potenzieren müssen\r\n";
      sAusgabe += " um es zu entschlüsseln.\r\n";
      sAusgabe += "\r\n";
      
      // die beiden vorgegebenen Zahlen nehmen
      int iZahl1=PhiN;
      int iZahl2=e;

      // die größere herausfinden und ggf tauschen
      if(iZahl1 < iZahl2) {
        int iTmp = iZahl1;
        iZahl1 = iZahl2;
        iZahl2 = iTmp;
      }

      // Umverteilung der Variablen auf die Positionen
      //
      //    r0  =  q0  *  r1  +  r2   [  A0,  B0  ]  [  a0,  b0  ]
      //   -----------------------------------------------------------------------
      //    0      1      2      3       4    5         6    7 

      Vector vEuklid = new Vector();
      int [] iStartArray = new int[8];

      iStartArray[0] = iZahl1;
      iStartArray[1] = iZahl1 / iZahl2;
      iStartArray[2] = iZahl2;
      iStartArray[3] = iStartArray[0] - (iStartArray[1] * iStartArray[2]);
      iStartArray[4] = 1;
      iStartArray[5] = 0;
      iStartArray[6] = 0;
      iStartArray[7] = 1;
      vEuklid.add(iStartArray);

      while(((int[]) vEuklid.get(vEuklid.size()-1))[3] != 0) {
        int [] iArray = new int[8];

        // = iArray[2]
        iArray[0] = ((int[]) vEuklid.get(vEuklid.size()-1))[2];

        // = iArray[3]
        iArray[2] = ((int[]) vEuklid.get(vEuklid.size()-1))[3];

        // iArray[0] / iArray[2]
        iArray[1] = iArray[0] / iArray[2]; // ((int[]) vEuklid.get(vEuklid.size()-1))[0] / ((int[]) vEuklid.get(vEuklid.size()-1))[2];

        iArray[3] = iArray[0] - (iArray[1] * iArray[2]);
        iArray[4] = ((int[]) vEuklid.get(vEuklid.size()-1))[6]; // iArray[6]
        iArray[5] = ((int[]) vEuklid.get(vEuklid.size()-1))[7]; // iArray[7]

        // = iArray[4] - (iArray[1] * iArray[6])
        iArray[6] = ((int[]) vEuklid.get(vEuklid.size()-1))[4] -
                   (((int[]) vEuklid.get(vEuklid.size()-1))[1] * 
                    ((int[]) vEuklid.get(vEuklid.size()-1))[6]);

        // = iArray[5] - (iArray[1] * iArray[7])
        iArray[7] = ((int[]) vEuklid.get(vEuklid.size()-1))[5] -
                   (((int[]) vEuklid.get(vEuklid.size()-1))[1] * 
                    ((int[]) vEuklid.get(vEuklid.size()-1))[7]);

        // Nun das Array zur Speicherung zum Vektor hinzufügen
        vEuklid.add(iArray);
      }

      // Hier ist die Arbeit nun abgeschlossen und die berechneten Ergebnisse
      // werden ausgegeben.

      sAusgabe += " Hier die Rechenschritte des Erweiterten Euklidischen Algorithmus:\r\n";
      sAusgabe += "\r\n";

      for(int i=0;i<vEuklid.size();i++) {
        sAusgabe += " "+((int[]) vEuklid.get(i))[0]+" = "+
                         ((int[]) vEuklid.get(i))[1]+" * "+
                         ((int[]) vEuklid.get(i))[2]+" + "+
                         ((int[]) vEuklid.get(i))[3]+"   ["+
                         ((int[]) vEuklid.get(i))[4]+","+
                         ((int[]) vEuklid.get(i))[5]+"]  ["+
                         ((int[]) vEuklid.get(i))[6]+","+
                         ((int[]) vEuklid.get(i))[7]+"]\r\n";
      }
 
    iInverse = ((int[]) vEuklid.get(vEuklid.size()-1))[7];

    sAusgabe += "\r\n";
    sAusgabe += " Somit erhalten wir als Ergebnis die Zahl d = "+iInverse;
    sAusgabe += "\r\n";


    }

    //***********************************//
    // Errechnen der binären Darstellung //
    //***********************************//

    {

      sAusgabe += "\r\n";
      sAusgabe += " Die binäre Darstellung:\r\n";
      sAusgabe += " -----------------------\r\n";
      sAusgabe += "\r\n";
      sAusgabe += " Da jedoch kein normaler Taschenrechner der Welt imstande ist, \r\n";
      sAusgabe += " die Lösung von (msg mod N)^d [ ("+msg+" mod "+N+")^"+iInverse+" ]\r\n";
      sAusgabe += " direkt auszurechnen müssen wir das ganze in kleineren Schritten\r\n";
      sAusgabe += " rechnen und zerlegen es erstmal in die binäre Darstellung.\r\n";
      sAusgabe += "\r\n";

      int iUntergrenze=0;  // hier wird die Untergrenze der Darstellung gespeichert
      int iObergrenze=0;   // fester Wert für die Obergrenze... sofern keine Kommazahl(?) ist hier Ende
      int iZerlegZahl=iInverse;  // diese Zahl wird in die binäre Darstellung umgewandelt


      if(iZerlegZahl < 0) {

        sAusgabe += " Da die Zahl negativ ist rechnen wir sie in den positiven Raum um.\r\n";
        sAusgabe += " Dies machen wir, indem wir den Modulus von Phi(N) zu rate ziehen:\r\n\r\n";

        sAusgabe += " Ergebnis von "+iZerlegZahl+" + "+PhiN+" ergibt: ";
        iZerlegZahl += PhiN;
        sAusgabe += iZerlegZahl+"\r\n\r\n";

      }


      double iTmp=1;
      while(iTmp >= 1 || iTmp <= -1) {
        iUntergrenze--;
        iTmp = (double) iZerlegZahl*Math.pow((double) 2, (double) iUntergrenze);
      }

      // sAusgabe += "\n\n"+iUntergrenze+"\n\n";

      int iAktGrenze=iUntergrenze;
      sAusgabe += " Formel                          |   Einzelergebnisse    | Endergebnis\n";
      sAusgabe += " ---------------------------------------------------------------------\n";
      while(iAktGrenze<iObergrenze) {
        double iTmp2 = Math.floor(iZerlegZahl*Math.pow(2,iAktGrenze+1) -
                       2 * Math.floor(iZerlegZahl*Math.pow(2,iAktGrenze)));

        int[] iBinViewRepSquares = new int[2];
        iBinViewRepSquares[0] = (int) iTmp2;
        vBinViewRepSquares.add(iBinViewRepSquares);
        
        sAusgabe += " Floor(x*2^"+(iAktGrenze+1)+")-2*Floor(x*2^"+iAktGrenze+")\t|  "+
                         (int) Math.floor(iZerlegZahl*Math.pow(2,iAktGrenze+1))+"\t - 2 * "+
                         (int) Math.floor(iZerlegZahl*Math.pow(2,iAktGrenze))+
                         "\t| = "+(int) iTmp2+"\n";
        iAktGrenze++;
      }

    iGrenze = Math.abs(iUntergrenze);

    }
        
    //********************************//
    // Errechnen der repeated Squares //
    //********************************//

    {

      sAusgabe += "\r\n";
      sAusgabe += "\r\n";
      sAusgabe += " Errechnen der Repeated Squares:\r\n";
      sAusgabe += " -------------------------------\r\n";
      sAusgabe += "\r\n";
      sAusgabe += " Nun errechnen wir noch rasch die Liste der Repeated Squares,\r\n";
      sAusgabe += " indem wir (msg mod N)^2 => ("+msg+" mod "+N+")^2\r\n";
      sAusgabe += " mehrfach wiederholt rechnen und erst dann aufhören, wenn wir\r\n";
      sAusgabe += " ebenso viele Einträge wie Stellen in der Binärdarstellung haben.\r\n";
      sAusgabe += "\r\n";
      sAusgabe += " Da die Liste von 'ganz klein' hin zu 'ganz groß' sortiert\r\n";
      sAusgabe += " ist muß die Liste für den Abgleich mit der Binärdarstellung\r\n";
      sAusgabe += " noch umgedreht werden\r\n";
      sAusgabe += "\r\n";

      int iMsgZahl=msg;
      int iModZahl=p*q;

      long iTmpZahl = iMsgZahl;

      for(int i=0;i<iGrenze;i++) {

        int[] iBinViewRepSquares = (int[]) vBinViewRepSquares.elementAt(iGrenze-1-i);
        iBinViewRepSquares[1] = (int) iTmpZahl;
        vBinViewRepSquares.set(iGrenze-1-i,iBinViewRepSquares);

        sAusgabe += " "+i+".\t"+iTmpZahl+" Mod "+iModZahl+"\n";

        iTmpZahl = (iTmpZahl*iTmpZahl);
        iTmpZahl %= iModZahl;
      }
    }

    int iTmp=1;

    sAusgabe += "\r\n";
    sAusgabe += "\r\n";
    sAusgabe += " Das Errechnen der Lösung:\r\n";
    sAusgabe += " -------------------------\r\n";
    sAusgabe += "\r\n";
    sAusgabe += " Nun multiplizieren (*) wir noch die passenden Einträge der Liste der\r\n";
    sAusgabe += " repeated Squares miteinander und berechnen den Modulus N dazu.\r\n";
    sAusgabe += " Dank der Binärdarstellung wissen wir bereits, welche der Einträge\r\n";
    sAusgabe += " wir benötigen. Nachfolgend die Rechnung:\r\n";
    sAusgabe += "\r\n";
    

    for (int i=0;i<vBinViewRepSquares.size();i++) {
      // sAusgabe += ((int[]) vBinViewRepSquares.get(i))[0]+" => "+
      //                  ((int[]) vBinViewRepSquares.get(i))[1]+"\n";
      if(((int[]) vBinViewRepSquares.get(i))[0] != 0) {
        int iTmp2 = ((int[]) vBinViewRepSquares.get(i))[1];
        sAusgabe += " "+i+". Schritt: "+iTmp+" * "+iTmp2+" (=";
        iTmp=iTmp*iTmp2;
        sAusgabe += iTmp+") mod "+N+" = ";
        iTmp %= p*q;
        sAusgabe += iTmp+"\r\n";
      }
      else
        sAusgabe += " "+i+". Schritt: fällt weg, da laut Binärdarstellung 0 (nicht enthalten)\r\n";

    }

    sAusgabe += "\r\n";
    sAusgabe += "\r\n";
    sAusgabe += " Wir haben nach dem Rechnen nun folgende Zahlen:\r\n";
    sAusgabe += " -----------------------------------------------\r\n";
    sAusgabe += "\r\n";

    sAusgabe += "      p = "+p+"\t q = "+q+"\r\n";
    sAusgabe += "      e = "+e+"\t d = "+iInverse+"\r\n";
    sAusgabe += "      N = p * q = "+N+"\r\n";
    sAusgabe += " Phi(N) = Phi(p*q) = (p-1)*(q-1) = "+PhiN+"\r\n";
    sAusgabe += "    msg = "+msg+" msg_d = "+iTmp+"\r\n";
    sAusgabe += "\r\n";
    sAusgabe += "\r\n";
    sAusgabe += " Somit ist die gesuchte Zahl msg_d = "+iTmp+"\r\n";
    sAusgabe += "\r\n";
    sAusgabe += "\r\n";

    try {
      PrintWriter pwOut=new PrintWriter(new FileOutputStream("Ergebnis6.txt"));
      pwOut.print(sAusgabe);
      pwOut.close();
    } catch(FileNotFoundException fnfex) { 
      System.out.println("Kann in Datei Ergebnis.txt nicht schreiben.");
    }

  }
}