// Arup Guha
// 10/31/2023
// Solution to CIS 3362 Homework #6 Question #4 Part A: Find Alice's Secret Value!

import java.util.*;
import java.math.BigInteger;

public class h6q4p1 {

	public static void main(String[] args) {
	
		// From question.
		BigInteger q = new BigInteger("208827064597");
		BigInteger g = new BigInteger("148730885957");
		BigInteger alicePublic = new BigInteger("22100313146");
		
		// Set up the steps by a million.
		HashMap<BigInteger,BigInteger> map = new HashMap<BigInteger,BigInteger>();
		BigInteger step = new BigInteger("1000000");
		BigInteger mult = g.modPow(step,q);
		BigInteger base = new BigInteger("1");
		BigInteger exp = new BigInteger("0");
		
		// Should be good enough for our q.
		for (int i=0; i<210001; i++) {
		
			// Update our value multiplying my mult each time.
			base = base.multiply(mult);
			base = base.mod(q);
			exp = exp.add(step);
			
			// Store result mapped to exponent that created it.
			map.put(base, exp);
			
		}
		
		BigInteger small = new BigInteger("1");
		
		BigInteger res = null;
		
		// This is our search for "y" described in the solution.
		for (int i=0; i<=1000000; i++) {
			
			BigInteger check = small.multiply(alicePublic);
			check = check.mod(q);
			
			// Got a hit!
			if (map.containsKey(check)) {
				BigInteger tmp = map.get(check);
				tmp = tmp.subtract(new BigInteger(""+i));
				res = tmp;
				break;
			}
			
			// small is iterating through each power of g.
			small = small.multiply(g);
			small = small.mod(q);
		}
		
		// Ta da!
		System.out.println(res);
	}
}