Discrete Logarithm Problem with Base 2

Question

Is there a special case for the discrete logarithm problem with a base of 2?

For example, is it possible to solve for $a$ in the following problem without brute forcing $a$?

(2^a) mod $p$ = $x$

Where $p$ is a large prime, and I have the answer $x$.

If this question has been asked before, please point me in the right direction, I was having trouble searching google for this problem.

Thanks in advance!

Answer 1

In general, $2$ is not easier than any other base. But there are better algorithms than brute force: see here for example.

Answer 2

Since your assumption is that p is prime, then you could look for the exponent a using an algorithm that calculates the square root under mod p.

This website explains how to calculate the square root for a modulo that is prime.

As Jyrki pointed out such an algorithm is still exponential, because each square has 2 square roots and you have to consider both of them to find the exponent. This results in a binary search tree that grows exponentially when the search depth increases. Therefore the algorithm is not polynomial.

The following algorithm illustrates the main idea, but can not be implemented as is, because it assumes that the base has no square root. If the base has a square root, the algorithm has to be adapted to take this into account.

Base Algorithm to Convert the Discrete Logarithm Problem to Finding the Square Root under Modulo

1. base = 2 //or any other base, the assumption is that base has no square root!
2. power = x
3. baseInverse = the multiplicative inverse of base under modulo p
4. exponent = 0
5. exponentMultiple = 1
6. while power is not equal to base
   1. alternativePower = power*baseInverse
   2. if power has a square root
      • power = sqrt(power)
   3. else //either power or alternativePower has a square root
      • exponent = exponent + exponentMultiple
      • power = sqrt(alternativePower)
   4. exponentMultiple = exponentMultiple*2
7. exponent = exponent + exponentMultiple
8. return exponent

Converting a Base to a non Quadratic Residue for a Prime Modulo

For a prime modulo p

• if p mod 4 is equal to 1, then base is a square if and only if p - base is a square. In this case if base is a square, you have to replace base by one of its square roots (not equal to 1) and keep repeating this until both roots are non square. Most of the time, taking any square root would be fine, but sometimes you may encounter a cycle, e.g. in modulo 41:

  • sqrt(16) = 37
  • sqrt(37) = 18
  • sqrt(18) = 10
  • sqrt(10) = 16

  when you encounter a cycle, take the other square root instead. Squares are connected to each other in a pseudoforest. This implies that if a square root is on a cycle, then the additive inverse of the square root cannot be on a cycle, because both square roots belong to the same graph and each graph in the forest has only a single cycle.

• if p mod 4 is equal to 3, then base is a square if and only if p - base is not a square. In this case if base is a square, one of its roots is also a square and the other is not a square. You have to replace base by its non square root.

The General Case when the Modulo is not Prime

More generally, when p is not a prime, no efficient way to find the square root under modulo p is known.