Dlogs and Factoring with polynomial number of arithmetic steps

❚ This post is related to a paper of mine, that will get published around the end of October this year in the Journal of Groups, Complexity and Cryptography (GCC). Some people may think, when they read the headline of this post, this must be a post about Shor's quantum factoring/dlog algorithm, because it is well known that dlogs and factoring can not be solved in polynomial number of arithmetic steps otherwise.

 But this is not true.

This sounds very unintuitive, because in cryptography we nearly always work with finite fields, where the bit length is restricted by the size of the modulus and the complexity of an algorithm is hence often measured as the number of arithmetic steps.

But of course you can do this, if you increase the available space. It is not obvious how to do it, but Adi Shamir [1] already showed in 1979 how this could be done, it you allow integers in memory/registers that are of exponential size.

His idea is the following: If we denote with $[n]_2 := n \pmod{2}$, then observe, that you could write the factorial function recursively:
$$\begin{align*} m! & = m^{[n]_2}\binom{m^{1-[n]_2}(m-1)}{\lfloor m/2 \rfloor}(\lfloor m/2 \rfloor!)^2\\ & = m^{[n]_2}\frac{m^{1-[n]_2}(m-1)!}{\lfloor m/2 \rfloor!\lfloor m/2 \rfloor!}(\lfloor m/2 \rfloor!)^2\\ \end{align*}$$ Hence, the computational task to compute $m!$ could be reduced to compute $\lfloor m/2 \rfloor!$, thus, after repeating this $\log_2 m$ times you reach $m=1$:
$$\begin{align*} 18! &= \frac{18!}{9!\cdot 9!}(9!)^2 \\ 9! & = 9\frac{8!}{4!\cdot 4!}(4!)^2 \\ 4! & = \frac{4!}{2!\cdot 2!}(2!)^2 \\ 2! & = \frac{2!}{1!\cdot 1!}(1!)^2 \\ 1! & = 1 \end{align*}$$
However, in order to make this algorithm work, you need an efficient way to compute the intermediate values $\binom{2m'}{m'} = \frac{(2m')!}{m'!\cdot m'!}$ which you multiply with the known values $(m'!)^2$ that you get from the recursion.

Therefore, Shamir used that $$(1+10^m)^m = \sum^{m}_{i=0}\binom{m}{i}10^{im} = \sum_{j=0}c_j10^j$$ and that binomial coefficient $\binom{m}{i}$ is entirely encoded in the base-10 coefficients $c_{mi}$ to $c_{mi+m-1}$. E.g. the binomial coefficients values of $\binom{6}{i}$ for $0 \leq i \leq 6$ are $1,6,15,20,15,6,1$ which can found in the coefficients of:
$$\begin{align*} (1+10^6)^6 & = 1000006000015000020000015000006000001 \\ & = [0000]1\;000006\;000015\;000020\;000015\;000006\;000001 \\ \end{align*}$$ Since $(1+10^m)^m$ could be computed in a number of steps that in polynomial in $\log m$, one could extract the binomial coefficient values out of the base-10 coefficient values using appropriate dividing and rounding methods. Finally, if we execute this procedure with $m \approx \sqrt{N}$ and $N$ is the number to factorize, we get a non-trivial factor via $\gcd(m!,N)$.

An algorithm for discrete logarithm

❚ It is a neat result and I though about this algorithm for quite a long time. I was searching for another (important) cryptographic problem that could be solved similarly. I asked a few people if they were aware of anything in this direction, but nobody knows another explicit example for one of the well known cryptographic problems. Finally, i came up with an idea for the discrete logarithm problem in finite fields $\mathbb{F}^*_q$. I will give here a short overview of the idea:

The main tool of the algorithm, is to use the binary $\&$-operator and write Fermat quotients in a base-p representation and make use of its cyclic properties. There are several related works, which classify complexity classes according to the necessary operations that are needed to solve problems in the class. The operations for this algorithm are $\{+,-,\times,\div,\&\}$, from which it is known that they already cover the entire class $\text{PSPACE}$. Hence the existence of the algorithm is not surprising.

So how does it work?

Well, here i can only give you a slight explanation of the idea by means of a little example, which i also gave in the appendix of the paper:

Suppose you have the prime number $q = 37$ and want to compute the discrete logarithm of $19$ in the group generated by $5$, i.e. you want to compute $x$ from $5^x \equiv 19\pmod{37}$. It is easy to check, that if you know $x_1$ from $p^{x_1} \equiv 19\pmod{37}$ as well as $x_2$ from $p^{x_2} \equiv 5\pmod{37}$ for some integer $p$, then you could compute the solution $x$ of $5^x \equiv 19$. The following example shows the computation of $x_1$. Spoiler Alert! - The solution is $x_1 = 7$.

You start by picking the integer $p = 2^{\lfloor \log_2 q \rfloor} = 32$. Hence, we are going to compute the solution of $32^{x_1} \equiv 19$. Lets compute the Fermat quotient $Q_q(p) = Q_{37}(32)$. It is: $$41418798401780779955631000733792140097803760059016275$$ Nothing to see here, but if you write it in base-$32$ you get:
$$\begin{align*} Q_{37}(32) & = 0\cdot 32^{35} &&+ 27\cdot 32^{34} &&+ 21\cdot 32^{33} &&+19\cdot32^{32} \\ &+28\cdot 32^{31} &&+ 17\cdot 32^{30} &&+ {\color{red}9}\cdot 32^{29} &&+16\cdot32^{28} \\ &+13\cdot 32^{27} &&+ 26\cdot 32^{26} &&+ 25\cdot 32^{25} &&+30\cdot32^{24} \\ &+8\cdot 32^{23} &&+ 20\cdot 32^{22} &&+ 24\cdot 32^{21} &&+6\cdot32^{20} \\ &+29\cdot 32^{19} &&+ 12\cdot 32^{18} &&+ \textbf{31}\cdot 32^{17} &&+4\cdot32^{16} \\ &+10\cdot 32^{15} &&+ 12\cdot 32^{14} &&+ 3\cdot 32^{13} &&+14\cdot32^{12} \\ &+22\cdot 32^{11} &&+ 15\cdot 32^{10} &&+ 18\cdot 32^{9} &&+5\cdot32^{8} \\ &+6\cdot 32^{7} &&+ 1\cdot 32^{6} &&+ 23\cdot 32^{5} &&+11\cdot32^{4} \\ &+7\cdot 32^{3} &&+ 25\cdot 32^{2} &&+ 2\cdot 32^{1} &&+19\cdot32^{0} \\  \end{align*}$$ The coefficient $9$, that i marked red, is the coefficient that is at position $x_1$, starting from the highest monomial (here $32^{35}$) with exponent $q-2$. The coefficient $31$, that i marked bold is the largest among all coefficients, denoted as $\overline{k}$. We proved, that its value can be found in $\log_2 q$ steps using base-$p$ digits sums. Here we have  $\overline{k} = 31$. The largest coefficient has the property, that its position within $Q_q(p)$ can be determined in $\log_2(q)$ steps, using again base-$p$ digit sums combined with a binary search algorithm. However, since the largest coefficient will be at some unrelated position to $x_1$, it seems not that useful on the first sight.

But, the Fermat quotient $Q_q(p)$ is a cyclic number. The means, that its coefficients are cyclically shifted when $Q_q(p)$ is multiplied with integer $< p$. E.g., $Q_{11}(8) = 0564272135_8$ and $3\cdot Q_{11}(8) = 2135056427$. It can be easily seen, that the later is a cyclic shift of the former. The definition of cyclic numbers can be extended. We call them "restricted" cyclic numbers. The coefficients of those integers are cyclically shifted only whenever they are multiplied with some integer $r \in \mathbb{G}_p \subseteq \mathbb{F}^*_q$. We use the cyclic shift to move the largest integer $\overline{k}$ to the position of coefficient $9$, by multiplication of $Q_q(p)$ with a certain factor. We proved that this factor can be found efficiently from $\hat{k}$ and the target group element $19$ only. In our example the factor turns out to be $10$, hence:
$$\begin{align*} 10\cdot Q_{37}(32) & = 8\cdot 32^{35} &&+ 20\cdot 32^{34} &&+ 24\cdot 32^{33} &&+6\cdot32^{32} \\ &+29\cdot 32^{31} &&+ 12\cdot 32^{30} &&+ \textbf{31}\cdot 32^{29} &&+4\cdot32^{28} \\ &+10\cdot 32^{27} &&+ 12\cdot 32^{26} &&+ 3\cdot 32^{25} &&+14\cdot32^{24} \\ &+22\cdot 32^{23} &&+ 15\cdot 32^{22} &&+ 18\cdot 32^{21} &&+5\cdot32^{20} \\ &+6\cdot 32^{19} &&+ 1\cdot 32^{18} &&+ 23\cdot 32^{17} &&+11\cdot32^{16} \\ &+7\cdot 32^{15} &&+ 25\cdot 32^{14} &&+ 2\cdot 32^{13} &&+19\cdot32^{12} \\ &+0\cdot 32^{11} &&+ 27\cdot 32^{10} &&+ 21\cdot 32^{9} &&+19\cdot32^{8} \\ &+28\cdot 32^{7} &&+ 17\cdot 32^{6} &&+ {\color{red}9}\cdot 32^{5} &&+16\cdot32^{4} \\ &+13\cdot 32^{3} &&+ 26\cdot 32^{2} &&+ 25\cdot 32^{1} &&+30\cdot32^{0} \\ \end{align*}$$ The largest coefficient $\overline{k}=31$ is now at the former position of coefficient $9$. The final step is, to compute the position of $\overline{k}$ in the base-$p$ coefficients of $10Q_q(p)$, as already mentioned above. The result yields the solution $x_1=7$.

Of course, i skipped many details but this is the overall idea.

 [1] Adi Shamir, Factoring Numbers in O(logn) arithmetic steps. Information Processing Letters 8 (1979) S. 28–31