1
$\begingroup$

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<x_1,x_2<p-1$$

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<c$$ $$0<a_1<x_1<b_1<p-1$$ $$0<a_2<x_2<b_2<p-1$$

$\endgroup$
9
  • $\begingroup$ $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$? $\endgroup$ Mar 22 at 11:15
  • $\begingroup$ yes thats what I meant. I could have phrased better. $\endgroup$
    – Turbo
    Mar 22 at 11:51
  • 1
    $\begingroup$ This is trivially as hard as the discrete logarithm problem in $\mathbb{F}_p^\times$. $\endgroup$
    – Aurel
    Mar 23 at 9:26
  • $\begingroup$ @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. $\endgroup$ Mar 23 at 22:34
  • 1
    $\begingroup$ @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. $\endgroup$ Mar 24 at 2:42

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.