Average order in cyclic groups

Asymptotic results on counting functions for algebraic and topological structures (11N45) Other results on the distribution of values or the characterization of arithmetic functions (11N64)

Review text

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.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: Average order in cyclic groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q558183)