PDF files of articles are only available for institutions which have paid for the online version upon signing an Institutional User License.

On exponents of modular subgroups generated by small consecutive integers

Volume 176 / 2016

Jacek Pomykała Acta Arithmetica 176 (2016), 321-342 MSC: Primary 11N, 11M; Secondary 14G50. DOI: 10.4064/aa8255-8-2016 Published online: 1 December 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.

Authors

  • Jacek PomykałaInstitute of Mathematics
    Warsaw University
    Banacha 2
    02-097 Warszawa, Poland
    e-mail

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image