// Primgenerator - allgemeine Funktionen
// Primzahlen, RSA-Zahlen, Jacobi-Symbol speziell.

import java.math.BigInteger;
import java.util.Random;

public final class PrimGenerator
{

  private static final BigInteger SIEBEN = BigInteger.valueOf(7);
  private static Random r = new Random(System.currentTimeMillis() );  // wird mit der Systemzeit init.

  // generiert eine RSA-Zahl, wobei die erste Primzahl n1 Bits und die zweite n2 Bits haben soll
  public static BigInteger hole_rsa_zahl (int n1, int n2)
  {
    // Achtung: folgendes kann scheitern, wenn n1 und n2 klein sind
    BigInteger p1 = null, p2 = null;

    p1 = erzeugePrimzahl(n1, true);
    if (p1 == null) return p1;

    for (int i = 0; i < 10; ++i)
    {
      p2 = erzeugePrimzahl(n2, true);
      if (p2 == null) continue;
      if (! p1.equals(p2)) break;  // sie müssen verschieden sein !
    }
    if (p2 == null || p2.equals(p1)) return null;
    // System.out.println ("RSA-Zahl generiert aus " + p1 + " und " + p2); // ausgeben, weil oben erstmal nicht bek.

    BigInteger n = p1.multiply(p2);
    // Für ECM Hinweis auf Gruppenordnung. Bei p1 und p2 == 3 mod 4 gilt:
    // ungerade x = (p1 + p2) / 2, gerade y = (p1 - p2) / 2  --> Ordnung n + 1 + p1 + p2 (symmetrisch !)
    /*
    BigInteger tmp = n.add(BigInteger.ONE).add(p1).add(p2);
    System.out.println ("ECM-Gruppenordnung: " + tmp);
    */

    return n;
  }

  // erzeugt eine "normale/schwere" Primzahl mit n1 Bits. Bei schwer soll auch (z-1)/2 eine Primzahl sein
  // Es wird jedenfalls eine mit == 3 mod 4 gewählt; Falls nichts gefunden, wird null zurück gegeben
  public static BigInteger erzeugePrimzahl(int n1, boolean schwer)
  {
    if (n1 <= 2)
    {
      return null;  // dafür ist nichts generierbar (erstes taugbares ist 5).
    }

    for (int i = 0; i < (n1 * n1); ++i)
    {
      BigInteger p = BigInteger.ZERO; BigInteger DREI = BigInteger.valueOf(3);
      p = p.setBit(n1 - 1); p = p.setBit(0); p = p.setBit(1);

      // Alle Bits dazwischen zufällig festlegen
      for (int wo = 2; wo < (n1 - 1); ++wo)
      {
        if (r.nextBoolean()) p = p.setBit(wo);
      }
      if (p.remainder(DREI).equals(BigInteger.ZERO)) { --i; continue; } // :3 --> nein
      if (! p.isProbablePrime(5)) continue; // keine Primzahl
      if (schwer)
      {
        BigInteger weiter = p.subtract(BigInteger.ONE).shiftRight(1);
        if (! weiter.isProbablePrime(5)) continue;  // RSA:(p-1)/2 ist keine Primzahl
      }
      // System.out.println ("Primzahl ist " + p);
      return p;
    }

    System.out.println ("Abbruch bei erzeugePrimzahl");
    return null;
  }

  // Berechnet speziell das Jacobi-Symbol, wenn unten eine ungerade Zahl steht.
  public static int jacobiSymbol(BigInteger a, BigInteger n)
  {
    BigInteger zaehler = a; BigInteger nenner = n; int rueck = +1;

    if (!nenner.testBit(0) || nenner.signum() <= 0) { System.out.println ("Nicht unterstützt: Unten gerade/negativ"); System.exit(1); }

    // wenn a < 0 ? Bei n == 3 mod 4 Vorzeichen wechsel
    if (zaehler.signum() < 0)
    {
      if (nenner.testBit(0) && nenner.testBit(1)) rueck = -1;  // zu tun: wenn n gerade
      zaehler = zaehler.abs();
    }

    while (!zaehler.equals(BigInteger.ONE))
    {
      if (zaehler.equals(BigInteger.ZERO)) return 0;

      // 4er raus
      while (zaehler.getLowestSetBit() >= 2) zaehler = zaehler.shiftRight(2);
      // 2er raus (max. einen)
      if (! zaehler.testBit(0))
      {
        int rest = nenner.and(PrimGenerator.SIEBEN).intValue();
        if ((rest == 3) || (rest == 5)) rueck = - rueck;
        zaehler = zaehler.shiftRight(1);
      }
      if (zaehler.equals(BigInteger.ONE)) break;

      // beide sich jetzt ungerade: modulo rechnen, um Fall beides 3 mod 4 ermitteln
      if (zaehler.testBit(1) && nenner.testBit(1)) rueck = - rueck;
      BigInteger neu = nenner.remainder(zaehler);
      nenner = zaehler; zaehler = neu;
    }
    return rueck;
  } 

  public static int jacobiSymbol(int a, int n)
  {
    return jacobiSymbol(BigInteger.valueOf(a), BigInteger.valueOf(n));
  }

  // Benützt Formel, um die Grenze zu bestimmen ... siehe Doku. über quadratisches Sieb
  // Achtung: für kleine n können negative Zahlen zurückgeliefert werden
  // BitGroesse sind die Anzahl 2er-Bits der Zahl, die maximal auftreten kann.
  // Beim Kettenbruchverfahren also: b ~ Bits(sqrt(n))
  // Beim diskreten Logarithmus also: b ~ Bits(n)
  public static int holeAnzahlPrimzahlen (int bitgroesse)
  {
    // Grenze b = exp(Wur(log(N) * log(log(N))) / c), c soll 2 sein
    double y = (bitgroesse - 0.5) * 0.693147;       // mit dem 2er-Log abschätzen
    System.out.println ("Ln ist " + y);
    double primGrenze;
    primGrenze = Math.exp(Math.sqrt(y * Math.log(y)) / 2);  // Ln[0.5, 0.5]
    System.out.println ("Primgrenze ist " + primGrenze);

    // die Anzahl der Primzahlen bis dahin abschätzen:
    // 1/4 * log2 * n/log(n) < pi(n) < 6 * log2 * n/log(n), also asymptotisch n/log(n)
    // oder nach Legendre n / (log(n) - 1.08366)
    int erg = (int) Math.ceil(primGrenze / (Math.log(primGrenze) - 1.08366));
    // bei kleinen Bitzahlen sinnvolle Begrenzung, da 'erg' auch Begrenzung
    if ((Math.log(erg) / 0.6931) > bitgroesse) erg = (1 << (bitgroesse >> 1));

    return erg;
  }

}