0
$\begingroup$

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

|improve this question
$\endgroup$
  • $\begingroup$ It's definitely not base 10. ​ The question should've been whether they're base e or 2. ​ ​ ​ ​ $\endgroup$ – user991 Feb 11 '16 at 19:19
  • 1
    $\begingroup$ See this answer starting at "However, note..." $\endgroup$ – mikeazo Feb 11 '16 at 19:20
  • 2
    $\begingroup$ See also this $\endgroup$ – mikeazo Feb 11 '16 at 19:21
  • 1
    $\begingroup$ @mikeazo : ​ It does matter here, since these logs are in the exponent. ​ ​ ​ ​ $\endgroup$ – user991 Feb 11 '16 at 19:21
  • 5
    $\begingroup$ @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 $\endgroup$ – poncho Feb 11 '16 at 19:31
4
$\begingroup$

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.

|improve this answer
$\endgroup$

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.