// PMinusEins.java - Einfache Faktorisierung nach der P-1 - Methode
// Bei Aufruf ohne Parameter wird der interaktive Modus gestartet, wo einzelne Zahlen eingegeben
// werden können. Bei Aufruf mit einer Ganzzahl wird nur diese faktorisiert.
// Die Größe der Schranke kann (beim Programmstart) erhöht werden, dann steigt aber auch die Rechenzeit an
// java -Dschranke=101 PMinusEins     # wenn (kleiner Faktor - 1) über einer Basis bis zur Pz 101 zerlegbar ist

// Beispiel:
// 35553361 = 15683[2*7841] * 2267[2*11*103], zerlegbar ab Schranke=103 oder höher

import java.math.BigInteger;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class PMinusEins
{
  private static BigInteger n = null;  
  private static BigInteger grenze = null;
  private final static BigInteger ZWEI = BigInteger.valueOf(2);
  private static int SIEBGROESSE = 97;
  private static int ANZAHLQUAD = 6;  // log2(SIEBGROESSE)
  private static int STAERKE = 1;  // für BigInteger-Primzahltest verwendet, je höher desto sicherer

  public static void main (String [] args)
  {
    // Siegroesse evt. noch bestimmen:
    String sg = System.getProperties().getProperty("schranke");
    if (sg != null)
    {
      try
      {
        int test = Integer.parseInt(sg);
        if (test > SIEBGROESSE)
        {
          SIEBGROESSE = test; ANZAHLQUAD = (int) (Math.log(test) / Math.log(2));
          System.out.println ("Erhöht: Siebgröße bis " + SIEBGROESSE + ", Anzahl Quadrierungen " + ANZAHLQUAD);
        }
      } catch (Exception ex) { /* initiale Werte so lassen */ }
    }

    final boolean interaktiv = (args.length == 0);
    BufferedReader eingabe = null;     String wert = null;
    if (interaktiv) eingabe = new BufferedReader(new InputStreamReader(System.in));

    do
    {
      if (interaktiv)
      {
        System.out.print ("> ");
        try { wert = eingabe.readLine(); } catch (IOException ex) { wert = null; }
        if (wert == null || 0 == wert.length()) { System.out.println ("Ende"); return; } // keine weiteren Eingaben
      }
      else
      {
        wert = args[0];
      }
      try
      {
        PMinusEins.n = new BigInteger(wert);
      }
      catch (NumberFormatException ex) { System.out.println("ungültig"); continue; }
      // Sonderbehandlung 2er hier, da technisch vor grenze_berechnen() sinnvoll
      if (n.signum() < 0) { System.out.print("-"); n = n.abs(); }
      int anzahlWeg = n.getLowestSetBit();
      if (anzahlWeg > 0) 
      {
        n = n.shiftRight(anzahlWeg); System.out.print (" 2^" + anzahlWeg + " ");
      }
      PMinusEins.grenze_berechnen();
      while (! (n.equals(BigInteger.ONE) || n.equals(BigInteger.ZERO)))
      {
        if (n.isProbablePrime(STAERKE)) { System.out.print (n); break; }
        BigInteger rueck = PMinusEins.faktorisieren();
        if (rueck != null) 
        {
          if (!rueck.equals(BigInteger.ONE))
          {
            System.out.print (rueck + " "); n = n.divide(rueck); // ausgeben und weitermachen
          }
        }
        else
        {
          System.out.print ("unbek."); n = BigInteger.ONE;  // kein Erfolg, also nichts mehr ausgeben
        }
      }
      System.out.println("");
    } while (interaktiv);

    if (interaktiv) eingabe = null; 
  }

  // Faktorisiert eine Zahl
  public static BigInteger faktorisieren ()
  {
    if ((n == null) || (grenze == null) || (n.getLowestSetBit() != 0)) return null;  // nichts gesetzt

    // System.out.println ("n ist " + n);
    if (n.compareTo(BigInteger.valueOf(3)) <= 0) return n;  // trivial
    
    for (short runde = 0; runde < 3; ++runde)
    {
      BigInteger basis = BigInteger.valueOf(runde == 0 ? 2 : (runde == 1 ? 3 : 5) );
      BigInteger erg = basis.modPow(grenze, n);
      // System.out.println ("Ergebnis ist " + erg);
      if (erg.equals(BigInteger.ONE))
      {
        System.out.println ("Schlecht, zu hoher Exponent");
      }
      else
      {
        for (short runde2 = 0; runde2 < ANZAHLQUAD; ++runde2)
        {
          if (erg.equals(n.subtract(BigInteger.ONE))) { System.out.println("-1 erreicht"); break; }
          BigInteger ggT = n.gcd(erg.subtract(BigInteger.ONE));
          if (! ggT.equals(BigInteger.ONE))
          {
            return ggT;
          }
          erg = erg.modPow(ZWEI, n);  // quadriert
        }
      }
    }

    return null;
  }

  // Errechnet eine Grenze zur Faktorisierung anhand der Zahl n - den kgV bis zur Siebgröße
  // Falls diese Zahlen bereits n teilen, wird dies dahingehend hier bereits verkleinert
  public static void grenze_berechnen()
  {
    if (n.equals(BigInteger.ZERO)) return;  // um Endlosschleife zu verhindern

    // kgV aller Zahlen unter dieser Größe 
    grenze = BigInteger.ONE;
    BigInteger aktuell = BigInteger.valueOf(3);

    while (aktuell.intValue() <= SIEBGROESSE)
    {
      // mal schauen, ob ob diese schon die Zahl teilt !
      do
      {
        BigInteger [] tmp = n.divideAndRemainder(aktuell);
        if (! tmp[1].equals(BigInteger.ZERO)) break;
        n = tmp[0]; System.out.print (aktuell + " ");
      } while (true);
      if (n.equals(BigInteger.ONE)) return;  // komplett geknackt

      BigInteger test = grenze.gcd(aktuell);
      grenze = grenze.multiply(aktuell);
      if (! test.equals(BigInteger.ONE))
      {
        grenze = grenze.divide(test);
      }
      aktuell = aktuell.add(ZWEI);
    }
    // System.out.println ("Grenze hat Bitgroesse " + grenze.bitLength());
  }

}