On exponents of modular subgroups generated by small consecutive integers
Volume 176 / 2016
Abstract
Let $D_B(n)=\lambda(n)/ E_B(n)$ where $\lambda(n)$ is the Carmichael function and $E_B(n)$ denotes the exponent of the subgroup of $\mathbb Z_n^*$ generated by the positive integers coprime to $n$ included in the interval $ [1, B]$. The values $D_B(n)$ play a significant role in primality testing and reduction of factoring $n$ to computing discrete logarithms in $\mathbb Z_n^*$ or to computing the corresponding values of Euler’s function $\phi$. We investigate the relation between $D_B(n)$ to $D_B(p)$ for prime divisors $p\,|\, n$ and the behaviour of $B$-special numbers (satisfying the condition $\operatorname{lcm}_{p\,|\, n} D_B(p)=D_B(n))$ on average. We prove the average bound for $D_B(n)$ over the special numbers. The estimates obtained imply an upper bound for the number of positive integers $ n\le x$ that might not be factored in deterministic subexponential time $\exp(T(x,u))$, where $T(x,u)=(\log x)^{1/u}(\log\log x)^{u-1}$, $3 \lt u \lt \varepsilon \log\log x /\!\log\log\log x$ and $\varepsilon$ is a sufficiently small positive constant.
