public class part1
  {

    public static void main(String args[])
    {

      int p,g;
      int pub_key,private_key;
      int temp;
      
      p=24691;

      g=106;

      pub_key=12375;

      temp=1;

      for(private_key=1;private_key<p;private_key++)
      {

        temp *= g;

        temp %= p;

        if(temp == pub_key)
          break;
      }

      System.out.println("Private key : "+private_key);
    }
  }