Smooth values of shifted primes in arithmetic progressions

Let \(\pi_h(x,y;q,a)\) denote the number of primes \(p\leq x\) such that \(p\equiv a\pmod q\) and the largest prime factor of \(p- h\) does not exceed \(y\) (so we say that \(p- h\) is \(y\)-smooth), and denote this number by \(\pi(x,y)\) when \(h= 1= q\). As described in the present paper, various authors have determined bounds for \(\pi(x,y)\), particularly in the case when \({\log x\over\log y}\) is bounded. In [``Smooth orders and cryptographic applications, Algorithmic number theory (Sydney, 2002) (C. Fieker, D. Kohel, eds.), Lect. Notes Comput. Sci. 2369, 338--348 (2002)], \textit{C. Pomerance} and \textit{I. Shparlinski} derived an upper bound for \(\pi(x,y)/\pi(x)\) in the range obtained by replacing \(\varepsilon\) by \(0\) in \((*)\) below. The main theorem of the paper under review provides an upper bound for \(\pi_h(x,y;q,a)/\pi(x)\) under the conditions \(h\neq 0\), \(q\leq(\log y)^A\) for a fixed \(A> 0\), \(\text{gcd}(a,q)= 1\) and \(\exp(\sqrt{\log x(\log\log x)^{1+\varepsilon}})\leq y\leq x\), where \(\varepsilon> 0\) is fixed. The authors explain that such a result has cryptographic consequences. In the proof, results concerning the counting function \(\Psi(x, y)\) of the set of \(y\)-smooth integers not exceeding \(x\), and related functions, are utilized, and so is a sieve result for primes up to \(x\) with certain additional properties. An important tool established by the authors is an asymptotic formula under some given conditions for \(\sum{m\over \varphi(m)}\) where the sum is over \(y\)-smooth integers \(m\leq x\) such that \(m\equiv a\pmod q\).

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Smooth values of shifted primes in arithmetic progressions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1766486)