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

• Are there restrictions on how large $x$ has to be? I would at least say that $x>0$, correct? May 6 '20 at 11:35
• @AleksanderRas: I clarified how we count $x$ in the title. While $x$ remains unrestricted in the body of the question, what really matters is $x\bmod((p-1)/k)$ which is the smallest positive solution, and determines the $k-1$ others.
– fgrieu
May 6 '20 at 11:55
• I have a method that works for circa one in a million $(a, b)$ pairs. While this is obviously not a practical solution for this problem, it is enough to show that the problem can't be used as the 'hard problem' for a cryptographical system... May 6 '20 at 13:23
• @poncho: I'm thinking about an attack on an out-of-my-head security property of signatures, that usual RSA signatures do not pretend to have, but EdDSA has: I call it misappropriation resistance, and tried to discuss it there. Applied to OpenPGP signatures, what I ask in the present question would markedly reduce the complexity of most of $2^{64}$ steps required for the attack, or $2^{33}$ steps required for a passable mockup of an attack.
– fgrieu
May 6 '20 at 13:53

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

• Thanks! I'd have one of $a$ or $b$ (my choice) constrained to be nearly twice the width of $p$ and randomized by a hash, and the other 1) in a "real" attack, a random given nearly twice the width of $p$; 2) in a "mockup" attack, almost unconstrained. It seems that your idea would help with the mockup.
– fgrieu
May 6 '20 at 15:13