On exponents of modular subgroups generated by small consecutive integers

Jacek Pomykała¹

¹ Institute of Mathematics Warsaw University Banacha 2 02-097 Warszawa, Poland

Acta Arithmetica, Tome 176 (2016) no. 4, pp. 321-342

Résumé

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.

Détail

DOI : 10.4064/aa8255-8-2016

Keywords: lambda where lambda carmichael function denotes exponent subgroup mathbb * generated positive integers coprime included interval values play significant role primality testing reduction factoring computing discrete logarithms mathbb * computing corresponding values euler function phi investigate relation between prime divisors behaviour b special numbers satisfying condition operatorname lcm average prove average bound special numbers estimates obtained imply upper bound number positive integers might factored deterministic subexponential time exp where log log log u varepsilon log log log log log varepsilon sufficiently small positive constant