2
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ Where is this problem from $\endgroup$
    – Mike
    Commented Jul 9, 2022 at 19:11
  • $\begingroup$ +1 : Very interesting question presented with reasonable analysis. I have no idea how to attack this problem. My intuition is that it is hard to imagine a scenario where it would be advantageous, in the middle of your search to specify $b$ equal to anything other than $(0)$. I am curious whether anyone can refute my intuition here. $\endgroup$ Commented Jul 9, 2022 at 19:12
  • $\begingroup$ The one idea that I have is that there doesn't seem to ever be any advantage in not maxing out the exponents associated with any prime that is included with your specification for $(a)$ on a specific guess. For example, taking $T = 2^{30}$, I see no possible disadvantage in having $(a)$ follow the format of $$\prod_{i=1}^r (p_i)^T.$$ $\endgroup$ Commented Jul 9, 2022 at 19:17
  • $\begingroup$ @user2661923 That is indeed true and it would also remove the steps required to get the exponents for each prime. It does rely on a lot of brute force calculation though $\endgroup$ Commented Jul 9, 2022 at 19:25
  • $\begingroup$ Sending $b = 0$ is disallowed by your own rules. $\endgroup$ Commented Jul 10, 2022 at 17:08

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ An approach I thought for the alternate problem was to guess the digits in base $2$ like if $gcd(x,2)$ is $2$ then that bit is $1$ else it's $0$. Similarly for $4,8...$ but I only have $25$ tries and the total number of binary bits may be closer to $30$ so we may have to do some guesswork to get a probabilistic approach. $\endgroup$ Commented Jul 9, 2022 at 19:45
  • $\begingroup$ @SmarikaSingh I don't see how that approach will reveal any information about which primes other than $(2)$ are factors of $(x)$. Am I missing something here? You can obtain full information about the prime $(2)$ simply by specifying $(a = 2^{30}).$ $\endgroup$ Commented Jul 9, 2022 at 19:50
  • $\begingroup$ We can find which bits are $1$ and which are $0$ in the binary representation of $x$. $\endgroup$ Commented Jul 9, 2022 at 19:51
  • $\begingroup$ @SmarikaSingh If $x = 97$, and you send $(a = b = 16)$, you will receive the response $(1)$ as the gcd. How does that help you determine the value of $(x)$? $\endgroup$ Commented Jul 9, 2022 at 19:53
  • $\begingroup$ @SmarikaSingh See the Addendum that I have just added at the end of my answer. $\endgroup$ Commented Jul 9, 2022 at 20:11
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .