I was reading the [Boneh-Franklin IBE paper](http://courses.cs.vt.edu/cs6204/Privacy-Security/Papers/Crypto/IBE-Weil-Pairing.pdf), 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](http://www.cs.uchicago.edu/~kalai/papers/old_papers/factorcryptology.pdf),
  

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 \;\;$?
> 
> 
> 



p such that p+1 has a large prime factor, effectively
Yes. G. Harman [has proven](http://www.ams.org/journals/mcom/2005-74-252/S0025-5718-05-01749-7/):


**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$.


