Average order in cyclic groups (Q558183)

This work was motivated by the search for cyclic groups of large order in cryptography. Intuition suggests that one should avoid fields whose multiplicative group order is largely made up from small prime factors. The authors place this intuition on a firm basis by investigating the average order \(\alpha(n)\) of the elements in the additive cyclic group \(\mathbb Z_n\) of order \(n\). Because more than half the contribution to \(\alpha(n)\) comes from the \(\varphi(n)\) primitive elements of order \(n\), they introduce \(\beta(n)= \alpha(n)/\varphi(n)\), and show that \[ 1= \liminf_{n\to\infty} \beta(n)< \beta(n)< \limsup_{n\to\infty} \beta(n)= A, \] where \(A= \zeta(2)\zeta(3)/\zeta(6)\). They also determine the mean behavior of \(\alpha\), \(\beta\), and \(1/\beta\), and discuss the average order of elements in the multiplicative groups of finite fields. The lower bounds for \(\beta\) are different for even and for odd characteristic.