Best strategy to find $x$

Question

We have a machine where we can send numbers $a$ and $b$ where both are $>1$ and then the machine returns $gcd(a,x+b)$ where $x$ is the number we wish to discover. We have $25$ tries to get $x$ which is less than $2^{30}$.

I tried using the fact that $gcd(p,q) = gcd(p-q,q)$ so we can send $b = 0$ and $a =$ some product of primes so that we can discover all the prime factors of $x$. Then we can discover the exponents for each factor by sending a large power of that factor as $a$. But I don't think this is optimal enough.

Any other approaches?

Answer 1

If I am interpreting the problem correctly, the value of $(x)$ can always be determined in exactly $(1)$ step.

Simply specify :

• $\displaystyle a = \prod_{i=r} (p_i)^{T},$

• $b = a.$

• where $\{p_1, p_2, \cdots, p_r\}$ is a complete list of all primes $\leq 2^{30}$

• and $T = 30.$ Here, you have the theoretical refinement that the exponent $a_i$ chosen for the prime $p_i$ should be specified so that $(p_i)^{a_i} \geq 2^{30}.$

Then, $x$ must exactly equal the returned gcd. A similar (alternative) specification is $\displaystyle a = \left[2^{30}\right]!.$

So, you have a theoretical approach that is only bound by some constraint on the number of primes that can be specified for the value $(a)$, along with some constraint on the maximum exponent allowable for each prime.

The alternate problem where you are given a value $N \in \Bbb{Z^+}$ and are also given the constraint that $(a)$ must be $\leq N$ is more interesting. If real world physical computers are to be used, you will be faced with the physical constraint of some value of $N$. Personally, I don't know how to attack this alternate problem.

---

Addendum
Attacking the alternate problem.

I am assuming that the number $(x)$ is randomly chosen from the set $\{1,2,\cdots, 2^{30}\}.$

I am also assuming that you are given $N = 2^{30}$, and are given the specification that $(a)$ and $(b)$ must each always be $\leq N.$

I would order the prime numbers in ascending order, so that $p_1 = 2, p_2 = 3, p_3 = 5, \cdots.$

Then, I would choose $r$ so that

$$\prod_{i=1}^r p_i \leq 2^{30} < \prod_{i=1}^{r+1} p_i.$$

Then, I would set

$$a = b = \prod_{i=1}^r (p_i)^1.$$

I think that this first guess is the one most likely to produce valuable information. Then, the analysis gets tricky.

For example, suppose, on the 2nd round, you have to choose between sending $(p_k)^c$ or $(p_m).$

If you know that $p_k$ divides $x$, then the probability that $(p_k)^2$ divides $x$ is only $~\displaystyle \frac{1}{p_k},$ while the probability that $~\displaystyle (p_k)^3$ divides $(x)$ is $~\displaystyle \frac{1}{(p_k)^2}.$

Personally, because a random number $(x)$ is unlikely to be divisible by any large prime, I would use, in the 2nd guess, the exact same strategy used in the first guess, starting with the primes $p_{r+1}, p_{r+2}, \cdots.$

The sole exception is that for any prime $(p_k)$ discovered in the first guess to be a factor of $(x)$, I would automatically include $(p_k)^2$ within my specification for $(a)$, in the 2nd guess.

Answer 2

As user2661923 mentioned, if you are allowed to to use large integers for $a$ and $b$, then you can do it in 1 oracle call.

However, if you want to make it practical, then you can do the following. Note that if we know $x \bmod N$, where $N > x$, then we know the value of $x \in \mathbb{N}$.

For $N$ we can take the product of the first primes: ${N = \displaystyle \prod_{i=1}^{r} p_i}$. We need $N > 2^{30}$, by direct calculation we see that $r = 10$ suffices (and $p_r = 29$).

Now, for every prime $p_i$, we know that $x \bmod p_i$ has $p_i$ possible values: $0,1, \dots, p_i-1$.

Therefore, we can do the following 29 oracle calls: $(a,b) =$ \begin{equation} (N, N+0), (N, N+1), \dots , (N, N+28). \end{equation} This gives us a list of gcds: $a_0, \dots , a_{28}$. Factor all these $a_i$ as ${a_i = \displaystyle \prod_{i=1}^{r} p_i^{e_i}}$, where $e_i \in \{0,1\}$.

Now, if $p_i \mid a_j$, then $x+N+j = x+j = 0 \bmod p_i$. Hence $x = -j \bmod p_i$. By doing this process for every prime up to 29, we get to know $x$ modulo all primes up to 29.

Now use the Chinese remainder theorem to compute $x \bmod N$. As mentioned before, this reveals $x \in \mathbb{N}$.

You might have noticed that we used 29 oracle calls instead of 25 or fewer. By choosing our $N$ a bit more carefully: $N = \displaystyle \prod_{i=1}^{r} p_i^{b_i}$, where $p_i^{b_i} \leq 25$ for every $i$. Then $r = 19$ suffices and:

\begin{equation} N = 2^4 \cdot 3^2 \cdot 5^2 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19. \end{equation}

Then only $\max(2^4, 3^2, 5^2, 7, 11, 13, 17, 19) = 25$ oracle calls are needed. You can check that the above process still works for prime powers instead of primes.

---

One last note: by taking $N = 2^4 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23$, you only need 23 oracle calls.