# p such that p+1 has a large prime factor, effectively

I was reading the Boneh-Franklin IBE paper, and it seemed rather conspicuous to me that they
didn't address the question of how to find primes $p$ and $q$ satisfying what they need (on page 19).
Since one can efficiently generate factored integers with an almost uniform distribution,
it would be enough for there to exist a noticeable density of primes $p$ satisfying the required
condition, i.e., one does not need to worry about efficiently finding the $q$ given such a $p$.

Is there an effective lower bound on the density of primes $p$ such that $\:p+1\:$ has a "large" prime factor? $\;\;$ (for whatever meaning of "large")

What if one additionally requires that $\;\; p \equiv 2 \pmod 3 \;\;$?

-
@Ricky, I'm having a difficult time parsing your question. Can you rephrase it in a more precise form, such as: "Is the set of primes satisfying X known to have size at least Y?". – Mark Lewko May 13 '13 at 23:44
What the best result with distribution 1? – user49362 Apr 8 '14 at 21:16

Theorem: Let $a \in Z$ and $\theta < .61$. Then there exists effectively computable constants $X_{0}$ and $\delta>0$ such that if $x > X_{0}$ then:
$$\sum_{p\leq x : P(p+a)> x^{\theta} } 1 > \delta \frac{x}{\log(x)}$$
where $P(n)$ is the greatest prime factor of $n$.
We would love to have $\theta$ larger - I don't know how large "large" needs to be in the paper you're citing. Also I'm pretty sure the proof would go through with the additional restriction $p\equiv 2\pmod 3$ if needed. – Greg Martin May 14 '13 at 6:34
I had searched and not found any effective results regarding prime density in arithmetic progressions en.wikipedia.org/wiki/… (i.e., not even without the condition on $p+1$), so such a strengthening presumably would not be extremely easy. $\:$ – Ricky Demer May 14 '13 at 7:47