Quick question on mathematical notation (translating to C)

Originally Posted by gardhr

I'm basing it on the heuristic that most papers written about number theory seem to use that convention.

Specifically, it's a lower bound given for the Miller-Rabin primality test, described here.

The expression is in the context of computational complexity, and indeed it is used in "big-O" notation throughout the paper. Basically, the base does not matter since they are considering things "asymptotically".

Originally Posted by laserlight

The expression is in the context of computational complexity, and indeed it is used in "big-O" notation throughout the paper. Basically, the base does not matter since they are considering things "asymptotically".

The equation in question relates to the actual lower bound of trial number bases, not the complexity of the algorithm. Or am I reading it wrongly?

"For an integer n , let G(n) denote the smallest x such that the
primes < x generate the multiplicative group modulo n . We offer heuristic
arguments and numerical data supporting the idea that
G(n) < (log 2)^-1 log n log log n"