On exponents of modular subgroups generated by small consecutive integers

Tom 176 / 2016

Jacek Pomykała Acta Arithmetica 176 (2016), 321-342 MSC: Primary 11N, 11M; Secondary 14G50. DOI: 10.4064/aa8255-8-2016 Opublikowany online: 1 December 2016


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.


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

Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

Przepisz kod z obrazka

Odśwież obrazek

Odśwież obrazek