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

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$.

• It's definitely not base 10. ​ The question should've been whether they're base e or 2. ​ ​ ​ ​ – user991 Feb 11 '16 at 19:19
• See this answer starting at "However, note..." – mikeazo Feb 11 '16 at 19:20
• @RickyDemer: nope, they don't, because they're either in a $O(\textit{formula})$ notation, or multiplied by an unspecified constant; either form eats constant factors – poncho Feb 11 '16 at 19:31
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.