# Publishing house / Journals and Serials / Acta Arithmetica / All issues

## Acta Arithmetica

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

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 