Estimating discrete logarithms via sum of group elements

The discrete logarithm problem is one of the cornerstones of modern asymmetric cryptography. Several algorithms exist and each approaches the problem in different ways. For example, the Pohlig-Hellman algorithm exploits smooth group orders, the index calculus algorithm uses a small set of known discrete logarithms in order to combine them to solve the problem in question and Pollards Rho-Algorithms makes use of the birthday paradox.

I am not aware of any approach that makes use of the fact, that the residues $r_i$ in the group $\mathcal{G} \subseteq \mathbb{F}_p$ generated by the element $g$ are often nearly equal distributed. Ok, this is not always true and there are some deep and highly non-trivial theorems about the distribution of these group elements. But for our purposes we can assume that the average size of a group element is $(p-1)/2$. That means, if we assume that $g$ is a primitive root, hence $\mathcal{G} = \mathbb{F}^*_p$, and $r_i \equiv g^i\pmod{p}$ it holds: $$ \sum^e_{i=1} r_i \approx e\cdot \frac{p-1}{2} $$ And since $e < p$ it in particular holds $$ S := \sum^e_{i=1} r_i = e\cdot \frac{p-1}{2} + \mathcal{O}(p^{1/2}) < p^2 $$ So if we can compute $S$ we get a very good approximation of $e$ since $$ \frac{2\cdot S}{p-1} = e + \mathcal{O}(1) $$

Factoring to SAT

Creating hard instances of computational problems can be easy (e.g., Factoring), cumbersome (e.g, SAT) or hard (e.g. Graph Isomorphism). So using a problem that allows to create instances in an easy way and then transform it into an instance of another problem is often a good idea, as long as the transformation is feasible. In this post i want to show how factoring can be reduced to a boolean formula $\varphi$ such that finding a satisfying assignment of $\varphi$ reveals a factor of the original integer. So if you think you found an algorithm that solves SAT in polynomial time, you should use this approach to convert a 2048-bit RSA instance to a SAT instance and test how it behaves :)

The approach is analogous to the approach of ToughSAT. For a high level overview, the algorithm works like this:

Input: $N = pq$, with unknown primes $p$ and $q$.

1. $n \leftarrow$ bitlength(N)
2. Take $2n$ variables for the binary representation of $p$ and $q$ and write:
   \begin{align*}
   x_{n-1}x_{n-2}...x_1x_0 \cdot y_{n-1}y_{n-2}...y_1y_0
   \end{align*} Then apply the school method for multiplying two integers.
3. This multiplication creates a list of equations that heavily depend on each other.
4. Replace each equation with an equivalent formula that only uses the boolean operators "and" and "or".
5. Transform the boolean formula to a 3CNF

I will present the algorithm by an example: