content: // <XMP>
  // Discrete logarithm calculator
  //
  // Written by Dario Alejandro Alpern (Buenos Aires - Argentina)
  // Last updated April 15th, 2005, See http://www.alpertron.com.ar/DILOG.HTM
  //
  // No part of this code can be used for commercial purposes without
  // the written consent from the author. Otherwise it can be used freely
  // except that you have to write somewhere in the code this header.
  // 
  import java.applet.*;
  import java.util.*;
  import java.awt.*;
  import java.math.*;
  
  public final class dilog extends ecm {
  
    private TextField textBase, textPower, textMod, textExp, textPeriod;
    private Button btnSolve;
    private BigInteger base, power, modulus;
    private BigInteger LastModulus = BigInt0;
    private Frame factorWindow;
    private ecm factorPanel;
    private BigInteger PrimesMod[];    // Mod = Modulus.
    private int ExponentsMod[];
    private BigInteger PrimesModBak[];
    private int ExponentsModBak[];
    private BigInteger PrimesGO[];     // GO = Group Order.
    private int ExponentsGO[];
    private BigInteger PrimesGOBak[];
    private int ExponentsGOBak[];
    private BigInteger nbrV[];
    private int NumberLengthOther;
    private int NbrFactorsMod=0;
    private long TestNbrOther[] = new long[NLen];
    private long nbrA[] = new long[NLen];
    private long nbrA2[] = new long[NLen];
    private long nbrB[] = new long[NLen];
    private long nbrB2[] = new long[NLen];
    private long nbrK[] = new long[NLen];
    private long nbrR[] = new long[NLen];
    private long nbrROther[] = new long[NLen];
    private long nbrR2[] = new long[NLen];
    private long nbrPower[] = new long[NLen];
    private long nbrBase[] = new long[NLen];
    private double dNOther;
  
    public void init() {
      Label labelBase, labelPower, labelMod, labelExp, labelPeriod, labelBottom;
  
      PrimesMod=new BigInteger[400];
      ExponentsMod=new int[400];
      PrimesModBak=new BigInteger[400];
      ExponentsModBak=new int[400];
      PrimesGO=new BigInteger[400];
      ExponentsGO=new int[400];
      nbrV = new BigInteger[400];
      setLayout(null);
      labelBase = new Label("Base");
      labelBase.reshape(10, 15, 40, 14);
      labelBase.setFont(new Font("Courier", Font.PLAIN, 12));
      labelBase.setAlignment(Label.CENTER);
      add(labelBase);
      textBase = new TextField(64);
      textBase.reshape(60, 10, 520, 30);
      textBase.setEditable(true);
      add(textBase);
      labelPower = new Label("Power");
      labelPower.reshape(10, 65, 40, 14);
      labelPower.setFont(new Font("Courier", Font.PLAIN, 12));
      labelPower.setAlignment(Label.CENTER);
      add(labelPower);
      textPower = new TextField(64);
      textPower.reshape(60, 60, 520, 30);
      textPower.setEditable(true);
      add(textPower);
      labelMod = new Label("Mod");
      labelMod.reshape(10, 115, 40, 14);
      labelMod.setFont(new Font("Courier", Font.PLAIN, 12));
      labelMod.setAlignment(Label.CENTER);
      add(labelMod);
      textMod = new TextField(64);
      textMod.reshape(60, 110, 520, 30);
      textMod.setEditable(true);
      add(textMod);
      btnSolve = new Button("Find discrete logarithm");
      btnSolve.reshape(210, 160, 180, 30);
      btnSolve.setFont(new Font("Courier", Font.PLAIN, 12));
      add(btnSolve);
      labelStatus = new Label("");
      labelStatus.reshape(30, 205, 520, 14);
      labelStatus.setFont(new Font("Courier", Font.PLAIN, 12));
      labelStatus.setAlignment(Label.CENTER);
      add(labelStatus);
      textExp = new TextField(64);
      labelExp = new Label("Exp");
      labelExp.reshape(10, 235, 40, 14);
      labelExp.setFont(new Font("Courier", Font.PLAIN, 12));
      labelExp.setAlignment(Label.CENTER);
      add(labelExp);
      textExp = new TextField(64);
      textExp.reshape(60, 230, 520, 30);
      textExp.setEditable(false);
      add(textExp);
      textPeriod = new TextField(64);
      labelPeriod = new Label("Period");
      labelPeriod.reshape(10, 285, 40, 14);
      labelPeriod.setFont(new Font("Courier", Font.PLAIN, 12));
      labelPeriod.setAlignment(Label.CENTER);
      add(labelPeriod);
      textPeriod = new TextField(64);
      textPeriod.reshape(60, 280, 520, 30);
      textPeriod.setEditable(false);
      add(textPeriod);
      labelBottom = new Label("Written by Dario Alejandro Alpern. Last updated April 15th, 2005");
      labelBottom.reshape(10, 330, 570, 14);
      labelBottom.setFont(new Font("Courier", Font.PLAIN, 12));
      labelBottom.setAlignment(Label.CENTER);
      add(labelBottom);
      validate();
      textBase.requestFocus();
      }
  
  public boolean handleEvent(Event e) {
    if (e.id == Event.ACTION_EVENT && e.target == btnSolve ||
        e.id == Event.KEY_PRESS && e.key == 13) {
      if (calcThread != null) {
        TerminateThread = true;
        try {
          calcThread.join();        /* Wait until the solving thread dies */
          } catch (InterruptedException ie) {};
        }
      calcThread = new Thread(this);  /* Start solving thread */
      calcThread.start();
      return true;
      }
  
    if (e.id == Event.KEY_PRESS && e.key == Event.TAB) {
      if (e.target == textBase) {textPower.requestFocus();}
      if (e.target == textPower) {textMod.requestFocus();}
      if (e.target == textMod) {textBase.requestFocus();}
      return true;
      }
    return super.handleEvent(e);
    }
  
    public void run() {
      BigInteger groupOrder, subGroupOrder, range, powSubGroupOrder;
      BigInteger GroupOrder = null;
      BigInteger Exponent, runningExp, baseExp, mod;
      BigInteger basePH, powerPH;
      BigInteger logar=null, logarMult;
      BigInteger divideExp, nbrD;
      BigInteger bigNbrA2, bigNbrB2;
      BigInteger DiscreteLog, DiscreteLogPeriod;
      int d, j, indexBase, indexExp;
      int i, index;
      long addA, addB, addA2, addB2;
      long mult1, mult2;
      long magnitude;
      int mostSignificantDword, leastSignificantDword;
      long firstLimit, secondLimit;
      long brentK, brentR;
      int ExpressionRC;
      BigInteger ExpressionResult[] = new BigInteger[1];
  
      Old=System.currentTimeMillis();
      OldTimeElapsed = 0;
      lModularMult = 0;
      TerminateThread = false;
      try {
  
        try {
          ExpressionRC = expression.ComputeExpression(textMod.getText().trim(),1,ExpressionResult);
        } catch (OutOfMemoryError e) {
          textExp.setText("Out of memory.");
          return;
        } catch (ArithmeticException e) {
          return;
        }
        modulus= ExpressionResult[0].abs();
        if (ExpressionRC != 0) {
          textExp.setText("Modulus: "+expressionText[-1-ExpressionRC]);
          return;
        }
  
        try {
          ExpressionRC = expression.ComputeExpression(textBase.getText().trim(),1,ExpressionResult);
        } catch (OutOfMemoryError e) {
          textExp.setText("Out of memory.");
          return;
        } catch (ArithmeticException e) {
          return;
        }
        base = ExpressionResult[0].mod(modulus);
        if (ExpressionRC != 0) {
          textExp.setText("Base: "+expressionText[-1-ExpressionRC]);
          return;
        }
  
        try {
          ExpressionRC = expression.ComputeExpression(textPower.getText().trim(),1,ExpressionResult);
        } catch (OutOfMemoryError e) {
          textExp.setText("Out of memory.");
          return;
        } catch (ArithmeticException e) {
          return;
        }
        power = ExpressionResult[0].abs();
        if (ExpressionRC != 0) {
          textExp.setText("Power: "+expressionText[-1-ExpressionRC]);
          return;
        }
  
        } catch (Exception e) {
          textExp.setText("Invalid data entered");
          return;
          }
      if (modulus.gcd(base).equals(BigInt1) == false) {
        textExp.setText("Modulus and base are not relatively prime.");
        return;
        }
      if (modulus.gcd(power).equals(BigInt1) == false) {
        textExp.setText("Modulus and power are not relatively prime.");
        return;
        }
      if (modulus.compareTo(BigInt1) <= 0) {
        textExp.setText("Modulus must be greater than 1.");
        return;
        }
      if (LastModulus.equals(modulus) == false) {
        if (GetSmallFactors(modulus, PrimesModBak, ExponentsModBak, Typ, 0) != 1) {
          LastModulus = modulus;
          factorPanel = new ecm();
          factorWindow = new Frame("Modulus factorization");
          factorWindow.setResizable(false);
          factorWindow.add(factorPanel);
          factorPanel.setSize(600, 390);
          Insets in = factorWindow.getInsets();
          factorWindow.setSize(600+in.right+in.left, 390+in.top+in.bottom);
          factorWindow.show();
          NbrFactorsMod = factorPanel.getFactors(modulus, PrimesModBak, ExponentsModBak);
          factorWindow.remove(factorPanel);
          factorWindow.dispose();
          }
        else {
          NbrFactorsMod = NbrFactors;
          }
        for (j=0; j<NbrFactorsMod; j++) {
          PrimesMod[j] = PrimesModBak[j];
          ExponentsMod[j] = ExponentsModBak[j];
          }
        }
      DiscreteLog = BigInt0;
      DiscreteLogPeriod = BigInt1;
      for (index = 0; index < NbrFactorsMod; index++) {
        groupOrder = PrimesMod[index].subtract(BigInt1);
        textExp.setText("Computing discrete logarithm...");
        if (GetSmallFactors(groupOrder, PrimesGO, ExponentsGO, Typ, 0) != 1) {
          LastModulus = modulus;
          factorPanel = new ecm();
          factorWindow = new Frame("Group order factorization");
          factorWindow.setResizable(false);
          factorWindow.add(factorPanel);
          factorPanel.setSize(600, 390);
          Insets in = factorWindow.getInsets();
          factorWindow.setSize(600+in.right+in.left, 390+in.top+in.bottom);
          factorWindow.show();
          NbrFactors = factorPanel.getFactors(groupOrder, PrimesGO, ExponentsGO);
          factorWindow.remove(factorPanel);
          factorWindow.dispose();
          }
        mod = PrimesMod[index];
        range = mod.divide(BigInt3);
        logar = BigInt0;
        logarMult = BigInt1;
        BigNbrToBigInt(mod);
        yieldFreq = 1000000/(NumberLength*NumberLength);
        GetMontgomeryParms();
        if (NumberLength == 1) {
          mostSignificantDword = NLen - 1;
          leastSignificantDword = NumberLength - 1;
          }
        else {
          mostSignificantDword = NumberLength - 1;
          leastSignificantDword = NumberLength - 2;
          }
        secondLimit = ((TestNbr[mostSignificantDword] << 31) +
                        TestNbr[leastSignificantDword]) * 2 / 3;
        firstLimit = secondLimit / 2;
  
        for (indexBase = 0; indexBase < NbrFactors; indexBase++) {
          textExp.setText("Computing discrete logarithm in subgroup of "+PrimesGO[indexBase]+" elements.");
          runningExp = BigInt0;
          subGroupOrder = PrimesGO[indexBase];
          ExchangeMods();                    // TestNbr <- subGroupOrder
          BigNbrToBigInt(subGroupOrder);
          dN = (double)TestNbr[NumberLength-1];
          if (NumberLength > 1) {
            dN += (double)TestNbr[NumberLength-2]/dDosALa31;
          }
          if (NumberLength > 2) {
            dN += (double)TestNbr[NumberLength-3]/dDosALa62;
          }
          ExchangeMods();                    // TestNbr <- modulus
          baseExp = groupOrder;
          powSubGroupOrder = BigInt1;
          for (indexExp = 0; indexExp < ExponentsGO[indexBase]; indexExp++) {
  
          /* PH below comes from Pohlig-Hellman algorithm */
  
            divideExp = BigInt1;
            j = ExponentsGO[indexBase] - indexExp;
            do {
              divideExp = divideExp.multiply(subGroupOrder);
              basePH = base.modPow(groupOrder.divide(divideExp), mod);
              j--;
              } while (j>0 && basePH.equals(BigInt1));
            powerPH = power.multiply(base.modPow(runningExp.negate(), mod)).
                            modPow(baseExp.divide(divideExp),mod);
            baseExp = baseExp.divide(subGroupOrder);
            if (subGroupOrder.compareTo(BigInteger.valueOf(20L)) < 0) {
              for (j=subGroupOrder.intValue()-1; j>=0; j--) {
                if (basePH.modPow(BigInteger.valueOf(j), mod).equals(powerPH)) {
                  break;
                  }
                }
              if (j<0) {
                textExp.setText("Cannot compute discrete logarithm    subgroup="+PrimesGO[indexBase]+"   exponent="+indexExp);
                return;
                }
              Exponent = BigInteger.valueOf(j);
              }
            else {        // Use Pollard's rho method with Brent's modification
              BigNbrToMont(powerPH, nbrPower);
              BigNbrToMont(basePH, nbrBase);
          
              for (j=0; j<NumberLength; j++) {
                nbrR2[j] = nbrBase[j];
                nbrA2[j] = nbrB2[j] = 0;
                }
              nbrB2[0] = 1;
              addA2 = addB2 = 0;
              mult2 = 1;
              brentR = 1;
              brentK = 0;
  PollardBrentRho:
              do {
                for (j=0; j<NumberLength; j++) {
                  nbrR[j] = nbrR2[j];
                  nbrA[j] = nbrA2[j];
                  nbrB[j] = nbrB2[j];
                  }
                addA = addA2;
                addB = addB2;
                mult1 = mult2;
                brentR *= 2;
                do {
                  if (TerminateThread) {
                    return;                /* End thread */
                  }
                  brentK++;
                  magnitude = (nbrR2[mostSignificantDword] << 31) +
                               nbrR2[leastSignificantDword];
                  if (magnitude < firstLimit) {
                    MontgomeryMult(nbrR2, nbrPower, nbrROther);
                    addA2++;
                    }
                  else {
                    if (magnitude < secondLimit) {
                      MontgomeryMult(nbrR2, nbrR2, nbrROther);
                      mult2 *= 2;
                      addA2 *= 2;
                      addB2 *= 2;
                      }
                    else {
                      MontgomeryMult(nbrR2, nbrBase, nbrROther);
                      addB2++;
                      }
                    }
                  long [] nbrTemp = nbrR2;
                  nbrR2 = nbrROther;
                  nbrROther = nbrTemp;
                  if (mult2 > 10000000) {
                    ExchangeMods();              // TestNbr <- subGroupOrder
                    AdjustExponent(nbrA2, mult2, addA2);
                    AdjustExponent(nbrB2, mult2, addB2);
                    ExchangeMods();              // TestNbr <- modulus
                    mult2 = 1;
                    addA2 = addB2 = 0;
                    }
                  for (j=0; j<NumberLength; j++) {
                    if (nbrR[j] != nbrR2[j]) {break;}
                    }
                  if (j==NumberLength) {break PollardBrentRho;}
                  } while (brentK < brentR);
                } while (true);
              ExchangeMods();                  // TestNbr <- subGroupOrder
              AdjustExponent(nbrA, mult1, addA);
              AdjustExponent(nbrB, mult1, addB);
              AdjustExponent(nbrA2, mult2, addA2);
              AdjustExponent(nbrB2, mult2, addB2);
              SubtractBigNbrModN(nbrA, nbrA2, nbrA);
              SubtractBigNbrModN(nbrB2, nbrB, nbrB);
              if (BigNbrIsZero(nbrA)) {
                for (j=0; j<NumberLength; j++) {
                  nbrK[j] = 0;
                  }
                bigNbrA2 = BigInt0;
                bigNbrB2 = BigIntToBigNbr(nbrB);
                d = subGroupOrder.intValue();
                }
              else {                           // gcd is 1.
                ModInvBigNbr(nbrA, nbrB2, TestNbr);
                MultBigNbrModN(nbrB2, nbrB, nbrK);
                bigNbrA2 = BigInt1;
                bigNbrB2 = basePH.modPow(BigIntToBigNbr(nbrK), mod);
                d = 1;
                }
              ExchangeMods();                  // TestNbr <- modulus
              nbrD = BigInteger.valueOf(d);
              for (j=0; j<d; j++) {
                if (powerPH.equals(bigNbrB2)) {break;}
                bigNbrB2 = bigNbrB2.multiply(bigNbrA2).mod(mod);
                }
              if (j==d) {
                textExp.setText("Cannot compute discrete logarithm    subgroup="+PrimesGO[indexBase]+"   exponent="+indexExp);
                return;
                }
              Exponent = BigIntToBigNbr(nbrK).add(subGroupOrder.divide(nbrD).
                         multiply(BigInteger.valueOf(j)).mod(subGroupOrder));
              }
            runningExp = runningExp.add(Exponent.multiply(powSubGroupOrder));
            powSubGroupOrder = powSubGroupOrder.multiply(subGroupOrder);
            }
          nbrV[indexBase] = runningExp;
          for (indexExp=0; indexExp < indexBase; indexExp++) {
            nbrV[indexBase] = nbrV[indexBase].subtract(nbrV[indexExp]).
                              multiply(PrimesGO[indexExp].pow(ExponentsGO[indexExp]).modInverse(powSubGroupOrder));
            }
          nbrV[indexBase] = nbrV[indexBase].mod(powSubGroupOrder);
          logar = logar.add(nbrV[indexBase].multiply(logarMult));
          logarMult = logarMult.multiply(powSubGroupOrder);
          }
  
        // Compute group order.
        BigInteger F = PrimesModBak[index];
        BigInteger G = F.subtract(BigInt1);
        BigInteger P = F;
        for (indexBase = 0; indexBase < NbrFactors; indexBase++) {
          for (indexExp = 0; indexExp < ExponentsGO[indexBase]; indexExp++) {
            if (base.modPow(G.divide(PrimesGO[indexBase]),F).equals(BigInt1)) {
              G = G.divide(PrimesGO[indexBase]);
              }
            }
          }
        logar = logar.mod(G);
        GroupOrder = G;
        for (i=2; i<ExponentsModBak[index]*2; i*=2) {
          BigInteger H = F.pow(2);
          BigInteger K0 = base.modPow(logar, H);
          BigInteger K1 = base.modPow(logar.add(G), H);
          BigInteger Num = power.subtract(K0).divide(F).mod(F);
          BigInteger Den = K1.subtract(K0).divide(F).mod(F);
          if (Den.equals(BigInt0)) {
            if (Num.equals(BigInt0)) {
              textExp.setText("Indetermination 0/0 -> Cannot compute discrete logarithm");
              }
            else {
              textExp.setText("There is no discrete logarithm");
              }
            return;
            }
          logar = logar.add(Num.multiply(Den.modInverse(F)).
                        mod(F).multiply(G));
          G = G.multiply(F);
          F = H;
          }
        GroupOrder = GroupOrder.
                 multiply(PrimesMod[index].pow(ExponentsMod[index]-1));
        logar = logar.mod(GroupOrder);
        if (DiscreteLogPeriod.equals(BigInt1)) {
          DiscreteLogPeriod = GroupOrder;
          DiscreteLog = logar;
          }
        else {
          BigInteger gcd = GroupOrder.gcd(DiscreteLogPeriod);
          if (logar.mod(gcd).equals(DiscreteLog.mod(gcd)) == false) {
            textExp.setText("Cannot compute discrete logarithm");
            return;
            }
          if (GroupOrder.divide(gcd).gcd(gcd).equals(BigInt1) == false) {
            BigInteger tmp = GroupOrder;
            GroupOrder = DiscreteLogPeriod;
            DiscreteLogPeriod = tmp;
            tmp = logar;
            logar = DiscreteLog;
            DiscreteLog = tmp;
            }
          GroupOrder = GroupOrder.divide(gcd);
          logar = logar.mod(GroupOrder);
          DiscreteLog = (logar.subtract(DiscreteLog)).
                  multiply(DiscreteLogPeriod.modInverse(GroupOrder)).
                  mod(GroupOrder).multiply(DiscreteLogPeriod).add(DiscreteLog);
          DiscreteLogPeriod = DiscreteLogPeriod.multiply(GroupOrder);
          }
        }
      textExp.setText(DiscreteLog.toString());
      textPeriod.setText(DiscreteLogPeriod.toString());
      long t=OldTimeElapsed/1000;
      labelStatus.setText("Time elapsed: "+
             t/86400+"d "+(t%86400)/3600+"h "+((t%3600)/60)+"m "+(t%60)+
             "s    mod mult: "+lModularMult);
      }
  
    private void BigNbrToMont(BigInteger bigNbr, long [] nbr) {
      int i;
      long tmp;
      int NumberLengthBak = NumberLength;
      System.arraycopy(TestNbr, 0, CalcAuxGcdU, 0, NLen);
      BigNbrToBigInt(bigNbr);
      for (i=NumberLength; i<NumberLengthBak; i++) {
        TestNbr[i] = 0;
        }
      NumberLength = NumberLengthBak;
      for (i=0; i<NumberLength; i++) {
        tmp = TestNbr[i];
        TestNbr[i] = CalcAuxGcdU[i];
        CalcAuxGcdU[i] = tmp;
        }
      MultBigNbrModN(CalcAuxGcdU, MontgomeryMultR1, nbr);
      }
  
    // nbr = (nbr * mult + add) % TestNbr
    private void AdjustExponent(long [] nbr, long mult, long add) {
      long Pr;
      int j;
  
      Pr = add * DosALa31;
      for (j=0; j<NumberLength; j++) {
        Pr = (Pr >>> 31) + mult*nbr[j];
        nbr[j] = Pr & 0x7FFFFFFFl;
      }
      nbr[j] = (Pr >>> 31);
      AdjustModN(nbr);
      }
  
    private void ExchangeMods() {
      long [] Tmp;
      int Temp;
      double dTemp;
  
      Tmp = TestNbr;
      TestNbr = TestNbrOther;
      TestNbrOther = Tmp;
      Temp = NumberLength;
      NumberLength = NumberLengthOther;
      NumberLengthOther = Temp;
      dTemp = dN;
      dN = dNOther;
      dNOther = dTemp;
      }
  
  }       // End applet class
  
  // </XMP>
  