1
$\begingroup$

Cryptographic procedures seem to almost exclusively use discrete logarithms rather than continuous logarithms. Hence, I assume there are good and sound reasons for this.

In essence, answers provided here: Why is NON DISCRETE logarithm problem not hard as the DISCRETE logarithm problem (so computationally hard)? state that continuous logarithms, thus, non-discrete logarithms can be computationally fast, while for discrete logarithms no such algorithm is known.

Furthermore, continuous logs can pose the problem of mathematical precision in terms of rounding errors.

For any non-discrete logarithm problem such as:

$$v = \log_{b}e$$

solving for either an unknown base $b$ or an unknown exponent $e$ is trivial when $v$ is known.

So my question is, not considering rounding issues, for now, what about solving for $v$ in the equation above, however when both the base and exponent are unknown, with the base $b$ being prime and $e$ being a random integer greater than 1.

$\endgroup$
  • 3
    $\begingroup$ "Assuming you know essentially nothing, find the correct value" is impossible. $\endgroup$ – SEJPM Dec 30 '18 at 11:31
  • $\begingroup$ Thanks for getting back to me so fast. The result v is always know, and v only. $\endgroup$ – Alex Dec 30 '18 at 11:33
  • $\begingroup$ So you're asking: imagine I give you no information whatsoever, can you guess a random real number? The answer is of course no. $\endgroup$ – Maeher Dec 30 '18 at 11:36
  • $\begingroup$ Thanks Maeher, I would give you a real number and then ask you to find a prime base b and an integer e such that v would be the respective result. $\endgroup$ – Alex Dec 30 '18 at 11:39
  • 1
    $\begingroup$ Take any prime b and raise it to the vth power $e=b^v$. Why would you expect this to be hard? $\endgroup$ – Maeher Dec 30 '18 at 11:46
1
$\begingroup$

By uniqueness of factorisation, this problem is well defined. If $e$ is uniformly distributed as you suggest it must be uniformly distributed in some finite range, say in $(1,2^N)$. Rewrite the equation as $$ v \log_2 b = \log_2 e. $$ Note that the random variable $Z=\log_2 e$ is distributed in $(0,N]$ with a highly nonuniform distribution exponentially biased towards the high end, namely $$ \mathbb{P}(Z\in (s-1,s)) \propto 2^{N-s+1} $$ while the primes from which $b$ is drawn are distributed (by the prime number theorem) result in the distribution $$ \mathbb{P}(W \in (f-1,f)) \propto \frac{\log(f-1)}{\log f} 2^{N-f+1} $$ where $W=\log_2 b.$ Note that $s,f$ are reals not integers.

One can set up a faster than brute force search algorithm given $v$ by first searching for $(f,s)$ pairs with $s=f/v$ starting with $f=N$ and decreasing $f$ while testing the nearest integer to $2^{f/v}$ for primality.

Rewriting the original equation $b^v=e$ as the approximation $$ \left| \frac{1}{b}-\frac{e}{b^{v+1}}\right|<\frac{1}{2 b^{v+1}}, $$ a $v+1$ step continued fraction approximation will be enough to run, prior to primality testing the nearest integer to the approximation.

$\endgroup$
  • $\begingroup$ Thanks a bunch, would you mind elaborating how that would work for a given $v=0.64768$. Unknown are $b=5$ and $e=12$? $\endgroup$ – Alex Dec 30 '18 at 23:21

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.