Time-Based Exponentiation Analysis

Heidi is analyzing a peculiar device that computes \(a^d \bmod n\) for an input \(a\) using the pseudocode provided below. The device stores two integers \(d\) and \(n\), and it computes the result using the following algorithm:

modPow(a, d, n) {
  r = 1;
  for (i = 0; i < 60; ++i) {
    if ((d & (1 << i)) != 0) {
      r = r * a % n;
    }
    a = a * a % n;
  }
  return r;
}

Note that only the multiplication modulo \(n\) (in lines 5 and 7) takes measurable time. In fact, multiplying \(x\) by \(y\) modulo \(n\) takes \((\lceil \log_2(x+1) \rceil + 1) \cdot (\lceil \log_2(y+1) \rceil + 1)\) nanoseconds. Here, \(\lceil \log_2(x+1) \rceil\) (denoted as \(\text{bits}(x)\)) is the number of bits in the binary representation of \(x\) without leading zeros.

Heidi knows the integer \(n\) but not \(d\). In order to determine \(d\), she is allowed to interact with the device using the following protocol:

• Issue a query of the form ? a where \(0 \le a < n\). The device will compute \(a^d \bmod n\) and return the time taken (in nanoseconds).
• After at most 30,000 queries, output the result by printing ! d as the final answer.

The numbers \(n\) and \(d\) are generated as follows: First, two 30-bit primes \(p\) and \(q\) (i.e. in the range \([2^{29}, 2^{30}-1]\)) are chosen uniformly at random. Then \(n = p \cdot q\) and \(m = \varphi(n) = (p-1)(q-1)\) are computed. Finally, \(d\) is chosen uniformly at random from \([1, m-1]\) such that \(\gcd(d, m) = 1\).

inputFormat

The testing system first writes an integer (n) (the modulo used by the device) to the standard input. Your program should then interact with the system by issuing queries as described in the protocol. In our offline simulation, the input will contain (n) on the first line and (for testing purposes) the hidden value of (d) on the subsequent line.

outputFormat

Your program must finally output exactly one line in the form ! d where (d) is the determined exponent. In an interactive environment, do not output anything else after this line.

sample

3233
2753

! 2753