import java.util.Calendar;

public class CrackDH
{
    private long p,g;
    private long publicKey;
    
    /** Getter for property publicKey.
     * @return Value of property publicKey.
     *
     */
    public long getPublicKey() {
        return publicKey;
    }
    
    /** Setter for property publicKey.
     * @param publicKey New value of property publicKey.
     *
     */
    public void setPublicKey(long publicKey) {
        this.publicKey = publicKey;
    }
    
    public CrackDH(long p, long g)
    {
        this.p = p;
        this.g = g;
    }
    
    public void crackIt()
    {
        long startTime = Calendar.getInstance().getTimeInMillis();
        long endTime;
        System.out.println("Start Time="+startTime+" milliseconds\n");
        
        boolean cracked = false;
        long discreteLog=1;
        long prevProduct = 1;
        long tempPubKey;
        
        //continue till the discrete log gives a value equal to the public key
        while (!cracked && discreteLog<this.p)
        {
            prevProduct *= this.g;
            tempPubKey = prevProduct % this.p;
            if (tempPubKey==this.publicKey)
            {
                endTime = Calendar.getInstance().getTimeInMillis();
                System.out.println("Found!!!\nEnd Time="+endTime+" milliseconds\n");
                System.out.println("Private Key="+discreteLog+"\n");
                System.out.println("Time taken to crack="+(endTime-startTime)+" milliseconds\n");
                cracked = true;
            }
            else
            {
                prevProduct = tempPubKey;
                discreteLog++;
                if (discreteLog%20==0) System.out.print(discreteLog);
                else System.out.print(".");
            }
        }
        if (discreteLog==this.p) System.out.println("\n\nSolution not found.\n");
    }
    
    public static void main(String [] args)
    {
        CrackDH objCrackDH = new CrackDH(24691, 106);
        objCrackDH.setPublicKey(12375);
        objCrackDH.crackIt();
    }
}