3
$\begingroup$

Is there an efficient way to compute $x$ in $2^x \equiv b \pmod {p^m}$, where $p$ is a small odd prime and $m$ could be a large integer? I know the solution is of the form $x=\phi(p^m) k + y$ for arbitrary non-negative integer $k$, but I don't know how to compute $y$ efficiently.

For example, solution of $2^x\equiv 28 \pmod {3^5}$ is given by $x=(2 \times 3^4) k + 72$ since $2^{(2 \times 3^4)k}\equiv 1 \pmod{3^5}$ by Euler/Carmichael's theorem and $2^{72}\equiv 28 \pmod{3^5}$. I don't know how to compute that $72$ other than generalized methods for solving discrete logarithm.

PS. By "efficient" I mean an algorithm whose complexity is hopefully polynomial in $p$ and $m$, but I accept answers which are more efficient than generalized methods of solving discrete logarithm.

$\endgroup$
  • 1
    $\begingroup$ If you want to look ahead, the "lifting" scheme is outlined in Section 4 of Discrete Logarithms and Factoring by Eric Bach (1984). I'm working on a concise exposition. $\endgroup$ – hardmath Jul 18 '16 at 15:39
  • $\begingroup$ Thank you for the reference. My question is answered completely in that reference. The reference is very clear and concise. $\endgroup$ – mhp Jul 20 '16 at 10:27
2
$\begingroup$

When $p$ is a small prime, finding a solution to $a^x \equiv b \bmod p$ is correspondingly easy (assuming that $a,b$ are not divisible by $p$). For example, $2^x \equiv 28 \bmod 3$ holds for any even power $x$.

It is also clear that if $a^x \equiv b \bmod p^s$ for some integer power $s\ge 1$, then:

$$ a^x \equiv b \bmod p^s \implies a^x \equiv b \bmod p^{s-1} \implies \ldots \implies a^x \equiv b \bmod p $$

Eric Bach (1984) wrote up a polynomial time algorithm, similar to the ideas of Hensel lifting for polynomials, to work backwards in that chain of implications. His purpose was to compare the difficulty of solving the discrete logarithm problem for a general modulus $n$ with that of factoring $n$, so we here are concerned only with a portion of his work.

As usual $\mathbb{Z}$ is the integers, and $\mathbb{Z}_n$ will denote the ring of integers modulo $n$. The additive group of $\mathbb{Z}_n$ will be written as $\mathbb{Z}_n^+$, while the multiplicative group of its units is written $\mathbb{Z}_n^*$. Note that the additive group is cyclic and has $n$ elements, while the number of elements in the multiplicative group is given by Euler's totient function $\varphi(n)$ (counting the integers $0\lt k \lt n$ which are coprime to $n$).

Taking the case where $n = p^s$ is a prime power $s\ge 1$, the counting is easy:

$$ \varphi(p^s) = (p-1)p^{s-1} $$

Is the multiplicative group $\mathbb{Z}_{p^s}^*$ cyclic of that order? In the case that $p$ is an odd prime, the answer is yes, and a generator for this group is called a primitive root modulo n.

For this reason Bach begins with the case of an odd prime $p$, and thus we know an isomorphism:

$$ \mathbb{Z}_{p^s}^* \cong \mathbb{Z}_p^* \times \mathbb{Z}_{p^{s-1}}^+ $$

It is easy to find the projection of $k \in \mathbb{Z}_{p^s}^*$ onto the first factor: just take the reduction of $k \bmod p$.

It is the essence of the rest of the algorithm to show a polynomial-time computable projection $\theta$ from multiplicative group $\mathbb{Z}_{p^s}^*$ homomorphically onto the second factor, additive group $\mathbb{Z}_{p^{s-1}}^+$:

$$ \theta: \mathbb{Z}_{p^s}^* \to \mathbb{Z}_{p^{s-1}}^+ $$

Once we have this function, the "lifting" of a solution mod $p$:

$$ a^{x_1} \equiv b \bmod p $$

to one in $\mathbb{Z}_{p^s}^*$:

$$ a^{x_s} \equiv b \bmod p^s $$

proceeds in a fairly natural way. Note that $x_s \equiv x_1 \bmod (p-1)$.

Applying the projection $\theta$ to the above "higher order" congruence leads us to this problem in the additive group $\mathbb{Z}_{p^{s-1}}^+$:

$$ c \cdot \theta(a) \equiv \theta(b) \bmod p^{s-1} $$

which can be solved by reciprocating $\theta(a)$ in $\mathbb{Z}_{p^{s-1}}$ via the extended Euclidean algorithm.

If we find an integer $x_s$ by Chinese remainder theorem such that both:

$$ x_s \equiv x_1 \bmod (p-1) $$ $$ x_s \equiv c \bmod p^{s-1} $$

then we are done, because by the isomorphism:

$$ a^{x_s} \equiv b \bmod p^s $$

Bach gives this formula for the homomorphism $\theta:\mathbb{Z}_{p^s}^*\to \mathbb{Z}_{p^{s-1}}^+$:

$$ \theta(k) = \left[ \frac{k^{(p-1)p^{s-1}} - 1}{p^s} \right] \bmod p^{s-1} $$

Details of why this is a homomorphism from the multiplicative group to the additive one are given in Bach's paper. Certainly $\theta(1) = 0$, and as I find time, I'll add further proof.

As Bach notes, the complexity of this function is polynomial in $\log p$ and $s$ if the numerator (of the integer expression inside the square brackets) is evaluated mod $p^{2s-1}$. We need that many radix $p$ places to get the right residue mod $p^{s-1}$ after dividing by $p^s$. The exactness of the division is implied by Euler's generalization of Fermat's Little Theorem.

Example (taken from the Question)

Consider the equation $2^x \equiv 28 \bmod 3^5$. As already remarked above, any even integer $x$ solves the "base case" $2^x \equiv 28 \bmod 3$. Therefore we will get a second congruence to combine with the first one:

$$ x \equiv 0 \bmod (3-1) $$ $$ x \cdot \theta(2) \equiv \theta(28) \bmod 3^4 $$

Recall that computing $\theta(k)$ involves raising to the power $\varphi(3^5) = 2\cdot 3^4 = 162$. A minimal additive chain for exponents leading to $162$ has nine steps. The binary one attains this by repeated squaring, doubling exponent to $128$, followed by multiplications of intermediate values that add to the exponent:

$$ 162 = 128 + 32 + 2 $$

In any case the values are small enough to do by calculator and to check with a spreadsheet:

$$ \theta(2) \equiv \left[ \frac{2^{162}-1}{243} \right] \equiv 16 \bmod 81 $$

$$ \theta(28) \equiv \left[ \frac{28^{162}-1}{243} \right] \equiv 18 \bmod 81 $$

Thus the second congruence amounts to:

$$ 16x \equiv 18 \bmod 81 $$ $$ 80x \equiv 90 \bmod 81 $$ $$ -x \equiv 9 \bmod 81 $$ $$ x \equiv 72 \bmod 81 $$

Since $x=72$ is already even, this is our solution modulo $2\cdot 3^4$.

TO DO: Fill in the details for the exceptional "even prime" case $p=2$.

$\endgroup$
  • $\begingroup$ Let me know if you are still working on this. If not, I can give pseudocode based on the results derived in that paper. $\endgroup$ – mhp Jul 20 '16 at 10:53
  • $\begingroup$ @mhp: If you'd like to post an Answer giving the pseudocode, and perhaps some words about the application or other motivation for your Question, that may benefit future Readers. $\endgroup$ – hardmath Jul 20 '16 at 13:01
  • $\begingroup$ Thank you for completing your answer. I don't think there is any need for a pseudocode at this point. $\endgroup$ – mhp Jul 20 '16 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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