# Direct algorithm for an integer program

Let $$p$$ be a prime and let $$h_1,h_2\in\{1,2,\dots,p-1\}$$ be integers.

Is there any direct algorithm to solve for following in polynomial in $$\log p$$ time?

$$\min (x_1-x_2)^2$$ $$x_1,x_2,k\in\mathbb Z$$ $$h_1^{x_1}-h_2^{x_2}=kp$$ $$0

Actually if we know how to decide emptiness of following, then it suffices as we can use binary search over $$a_i,b_i,c$$ at $$i\in\{1,2\}$$:

$$x_1,x_2,k\in\mathbb Z$$ $$h_1^{x_1}-h_2^{x_2}=kp$$ $$(x_1-x_2)^2 $$0 $$0

• $x_1 = x_2 = p - 1$ gives $(x_1 - x_2)^2 = 0$. Do you want minimal positive value of $(x_1 - x_2)^2$? Mar 22 at 11:15
• yes thats what I meant. I could have phrased better. Mar 22 at 11:51
• This is trivially as hard as the discrete logarithm problem in $\mathbb{F}_p^\times$. Mar 23 at 9:26
• @Aurel: I doubt that. This problem has a trivial solution for many instances (see my answer below), and I do not see how it can help to solve the discrete logarithm problem. Mar 23 at 22:34
• @Turbo: I did not check the details, but accurately tightening things up it's very well possible that you'd end up with a problem of no less complexity as the discrete logarithm. Personally I do not see much sense in such reformulations of the known hard problems. Mar 24 at 2:42

## 2 Answers

This is an extremely difficult non-linear integer programming problem. The difficulty consists in the restriction $$h_1^{x_1}-h_2^{x_2}=kp$$ which is hardly handled by known methods. I don't know any specialized soft to this end. Mathematica 14 easily solves it for

p = Prime[10^2]; SeedRandom[1234]; h1 = RandomChoice[Range[p - 1]];
h2 = RandomChoice[Range[p - 1]]; NMinimize[{(x1 - x2)^2,
Mod[h1^x1 - h2^x2, p] == 0 && x1 \[Element] Integers &&
x2 \[Element] Integers && 0 < x1 && x1 < p - 1 && x2 > 0 &&
x2 < p - 1}, {x1, x2}] // Timing


{0.671875, {9., {x1 -> 192, x2 -> 195}}}

with $$p =541$$.SeedRandom[1234]; guaranties the reproducibility of randomly chosen $$h_1,h_2$$ . Making use of options, one obtains

p = Prime[2*10^2]; SeedRandom[1234]; h1 = RandomChoice[Range[p - 1]];
h2 = RandomChoice[Range[p - 1]]; NMinimize[{(x1 - x2)^2,
Mod[h1^x1 - h2^x2, p] == 0 && x1 \[Element] Integers &&
x2 \[Element] Integers && 0 < x1 && x1 < p - 1 && x2 > 0 &&
x2 < p - 1}, {x1, x2},  Method -> {"DifferentialEvolution", "ScalingFactor" -> 1,
"SearchPoints" -> 150}, MaxIterations -> 2000] // Timing


{133.375, {23409., {x1 -> 936, x2 -> 783}}}

with $$p=1223$$. My comp is not powerful and fails with p=Prime[10^3](equals $$7919$$). The methods are described in the documentation.

The problem is trivial at least for a half of instances by simply taking $$x_1=x_2=\frac{p-1}2$$. This gives a solution when the orders of $$h_1,h_2$$ modulo $$p$$ divide $$\frac{p-1}2$$; or when both orders equal $$p-1$$.