For equation $B^e \bmod M = X$, if all values except exponent $e$ are known, can an $e$ value that works be efficiently found?

Question

For equation $B^e \bmod M = X$, if all values except exponent $e$ are known, can an $e$ value that works be efficiently found?

I suppose if a low value of $M$ is used, it might be quite easy. But, what if $M$ could be extremely large? Would there still be an efficient way, to find an $e$ value that satisfies the equation?

Answer 1

Here's how I would go about it:

Definition of mod

$$B^e\equiv X\mod M\iff B^e=Mz+X\tag{1}$$

Now here's the thing you can give other versions of this, that will help later on:

$$B^e\equiv X\mod M\iff B^e-Mz=X\tag{1.1}$$ $$B^e\equiv X\mod M\iff B^e-X=Mz\tag{1.2}$$

Parity arguments show the following:

• $B\equiv X\pmod 2\land M\equiv 1\pmod 2\implies z\equiv 0\pmod 2$
• $B\not\equiv X\pmod 2\land M\equiv 1\pmod 2\implies z\equiv 1\pmod 2$

More generally, mod some value $p$ :

• $B\equiv X\pmod p\land M\not\equiv 0\pmod p\implies z\equiv 0\pmod p$
• $B\equiv M\pmod p\implies \exists n~, Bn\equiv X \pmod p$
• $X\equiv M\pmod p\implies \exists q~,Xq\equiv B\pmod p$

ex.

$\text{RSA 129}=11438162575788886766923577997614661201021829672124236256256184293\\ 5706935245733897830597123563958705058989075147599290026879543541$

without using it's known factorization I'll pick a value to raise to a large exponent :

$B=21806107020153883717 %e=95265861131261374403$ $B^e\equiv\\ 465582739100135667877678674908247905157690272448726064526691925293304506566\\59160707291360021700048766504679931475355766192192353 \pmod {\text{RSA 129}}$

Okay a few things, both $B$ and $X$ are odd, that tells me the $z$ value, is even because $\text{RSA 129}$ is also odd. In fact they are congruent mod 4,3,and 23 under $2^{30}$ so $z$ is divisible by 276. Now one other rule, is that if $X$ isn't a power the normal integers in general, that $e$ is at least the ceiling of the normal logarithm base $B$ of $M$. In that case, it's definitely at least 7; so not much help but some. That together with the previous fact, brings our $z$ to a minimum of 20497140. Not too shabby.

$$X\equiv 1097299953583374764\pmod B$$ $$M\equiv 5996405295634794488\pmod B$$

We can also work from the fact that $B^e$ is $0 \pmod B$ to get $Mz\equiv -X\pmod B$ in PARI GP, that gives us back $z\equiv 8804812713198121952\pmod B$ which only has a factor of 276 if $B$ is multiplied by a number that is $88 \pmod {276}$ so we get $z\equiv 1927742230486739889048 \pmod {6018485537562471905892}$ This is better, to say the least. in fact this raises our minimum to $8$. It's still slow, but we got on the correct track as far as size of $z$ shown is concerned.

Answer 2

if all values except exponent e are known, can an e value that works be efficiently found?

It very much depends.

• Solving the discrete logarithm problem for all instances of a given modulus size is known to be in $\textsf{NP}\cap \textsf{co-NP}$, so the problem is neither NP nor co-NP complete, but it also likely isn't in P (ie efficiently solvable).
• If $e$ and $X$ are chosen uniformly at random and $B$ multiplicatively generates $n$ different values (after reduction), then finding $e$ given everything else is the discrete logarithm problem which is assumed to be not efficiently doable for sufficiently large values of $n$ (for this group, usually $n\approx 2^{2048}$ is chosen for practical purposes).
• If $M$ is sufficiently small, then the General Number Field Sieve can find the discrete logarithm, the current record for this is for $M\approx 2^{795}$.
• If $M$ is of the form $M=r^e\pm s$ for some small values $r,s$, then the Special Number Field Sieve can be used, for which the current record is $M\approx 2^{1024}$.
• If $M$ is large but $n$ is small, then you can use the Baby-Step-Giant-Step or the Pollard-Rho algorithms to find the discrete logarithm, both roughly require $\sqrt n$ operations, so are feasibly until about $2^{120}$.
• If $n$ has a lot of (known) small prime factors (which are allowed to have high multiplicity), then you can use the Pohlig-Hellman algorithm to compute the discrete logarithm in about $\sqrt p$ steps where $p$ is the largest prime factor of $n$.