Find prime $p$ such that $a^x\equiv b\pmod p$ for many $x\in[1,p)$ Given haphazard large integers $a$ and $b$ (like few thousand bits), can we efficiently find (and how) some integer triplet $(p,x,k)$ with


$p$ a large prime (like a thousand bits)
$a^x\equiv b\pmod p$
$k$ sizable (say of 10 bits or more if possible) and dividing $p-1$
$a^{(p-1)/k}\equiv 1\pmod p$


These conditions match the title, since $x_j\gets j\,(p-1)/k+(x\bmod((p-1)/k))$ gives $k$ distinct $x_j\in[1,p)$ with $a^{x_j}\equiv b\pmod p$.



Late addition: in a variant with reduced applicability, one of $a$ or $b$ would be an output instead of a given, with the constraint that it should be unremarkable modulo $p$ (at least not among $0$, $1$, $p-1$) when the other is haphazard.
You asked for my one-in-a-million attack; here is what it looks like:


Step 1: find a large prime factor of $b^i - 1$, for some small $i$.  This can be done by iterating through the various small values of $i$ (starting with $i=1$ naturally), use the known factorizations (e.g. $b^2 - 1 = (b+1)(b-1)$), and then for the various subfactors, scrap off the easy small factors and hope what's remaining is a prime (e.g. $b+1 = hp$, for some small $h$ and prime $p$.


If this step succeeds, then we have $a^{0} \equiv b^i \pmod p$; check to see if this yields an $x$ (i.e.. if $a^{n(p-1)/i} \equiv b \pmod p$ for some $n \in \{0, …, i-1\}$).

An initial estimate is that we will manage for find just an appropriate $p$ (and $x$) about 1 in 1000 arbitrary $b$ values in the "thousand bit" range.


Step 2: find $k$.  To do this, find the small factors of $p-1$, and for various small (not necessarily prime) factors $k$ in the appropriate range, check if $a^{(p-1)/k} \equiv 1 \pmod p$.  If $a$ is random, this happens for a particular $k$ with probability $1/k$ (actually, perhaps a bit less if $i &gt; 1$ in the previous step...)


Again, a very rough guess would be that this may succeed about 1 every 1000 times (that we have a factor $k$ of the appropriate magnitude, and that $a$ happens to be in that subgroup).

If both steps succeed, you have $p, x, k$ as requested (although, looking back at it, perhaps a probability of "one in a million" is a tad optimistic; "one in ten million" might be closer...