# Polytime implementation of Discrete Log using primitive recursive functions

The primitive recursive functions are defined by Godel as:

1. $z() = 0$
2. $s(x) = x+1$
3. $\pi_i(x_1, \dots, x_k) = x_i$

Plus closure under

1. Composition: $h(x_1, \dots, x_m) = f(g_1(x_1, \dots, x_m), \dots, g_k(x_1, \dots, x_m)$
2. Primitive Recursion: $h(0, x_1, \dots, x_m) = f(x_1, \dots, x_m)$ and $h(y+1, x_1, \dots, x_k) = g(y, h(y, x_1, \dots, x_m), x_1, \dots, x_m)$

It is well known that the set of Primitive Recursive functions contains $ELEMENTARY$, so it definitely contains the discrete log function $L(x) = \lfloor \log_2(x) \rfloor$. But it's also not too hard to see that $L$ can't be implemented in a way that intuitively takes polynomial time (that is, $\log_2(x)^{O(1)}$), even though this is possible on a Turing Machine.

My question:

Is there a simple (subjective) function/closure property that we can add to these primitive recursive atoms that will give Discrete Log a polytime PR definition?

Thanks!

• Why can it not be implemented in polynomial time? Take $n$ and find the biggest $k\in\mathbb{N}$ such, that $2^k\leq n$ (of course, $k$ cannot be bigger than $\log_2 n$). Then $\lfloor\log_2(n)\rfloor=k$. This takes linear time. Commented Mar 12, 2014 at 13:51
• I don't think that algorithm can be translated to primitive recursives in a nice way. If you want to run a search over possible $k$, you will need a Primitive Recursion index function that is either $O(1)$ (making the search unsound) or $O(n)$ (making the search exponential time). The ideal loop index is $O(\log n)$, but we can't create an $O(\log n)$ expression without the use of discrete log itself!
– GMB
Commented Mar 12, 2014 at 19:53
• Can you please explain what is an unsound search? If you make a while loop for computing $2^i$ (from $i=1$ and then $i++$) and then comparing it with $n$, and the condition of this while loop is $2^i\leq n$, this algorithm will take you $O(\log n)$ time. So, you can translate this algorithm in a primitive recursive function. Commented Mar 13, 2014 at 15:25
• Well, an expression for this function could be $h(n)=\max\{i: 2^i\leq n\}$. But this expression could be analyzed more with the basic p.r. functions in your post. Commented Mar 13, 2014 at 15:39
• I would have thought that discrete logarithm means this hard to calculate beast? Commented Jun 17, 2014 at 9:49

Your question is about computable functions (primitive recursive) versus computability (or algorithm). A short answer is consider another primitive recursive schema (Known as primitive recursion with parameters in Rosza Peter book on recursive functions). This schema allows to modify the parameter on which we do not make the recursion $f(x+1,y) = h(x, f(x, j(x,y)), y)$. We are still in the class of primitive recursive functions but it has been shown that all "classical methods" can be implemented in this language.