What is base of $\log$ in Subexponential Algo for DLP?

Question

I am currently going through this paper - "A Subexponential Algorithm for the Discrete Logarithm Problem" by Leonard Adleman.

On page 56, author mentions that Dixon's algorithm - Asymptotically Fast Factorization of Integers, works in $RTIME (O(2^{O{(\log(q)\log\log(q))}^{1/2}}))$ and on page57, mentions that $r_i, s_i$ are smooth with respect to bound $2^{c ({\log(q)\log\log(q)})^{1/2}}$ .

My question is are these logs mentioned in equation, base $e$ or $2$? Because in his paper (on page 255), Dixon has mentioned the complexity equation in $\ln$ which means natural log, i.e. base $e$.

Answer 1

In this case, the base does not matter as the $\log$ terms are wrapped in an $O$ expression. The $O$ expression lets you throw away constant factors and to convert something base $X$ to base $Y$ is simply $\log_X Z = \frac{\log_Y Z}{\log_Y X}$, well, $\log_Y X$ is a constant, so it can be thrown out in the $O$ expression.

The reason the second reference explicitly use $\ln$ is that the $O$ expression includes an exponent that does not also contain an $O$ expression. In this case, the base does matter.