Primes $p$ for which $p-1$ has a large prime factor What are the best known density results and conjectures for primes $p$ where $p-1$ has a large prime factor $q$, where by "large" I mean something greater than $\sqrt{p}$.
The most extreme case is that of a safe prime (Wikipedia entry), which is a prime $p$ such that $(p - 1)/2$ is also a prime (the smaller prime is called a Sophie Germain prime). I believe it is conjectured (and not yet proved) that infinitely many safe primes exist, and that the density is roughly $c/\log^2 n$ for some constant $c$ (as it should be from a probabilistic model).
For the more general setting, where we are interested in the density of primes $p$ for which $p-1$ has a large prime factor, the only general approach I am aware of is the prime number theorem for arithmetic progressions, and some of its strengthenings such as the Bombieri-Vinogradov theorem (conditional to the GRH), the (still open) Elliott-Halberstam conjecture, Chowla's conjecture on the first Dirichlet prime, and some partial results related to this conjecture. All of these deal with the existence of primes $p \equiv a \pmod q$ for arbitrary $q$ and arbitrary $a$ that is coprime to $q$.
My question: can we expect qualitatively better results for the situation where $q$ is prime and $a = 1$? Also, I am not interested in specifying $q$ beforehand, so the existence of a $p$ such that there exists any large prime $q$ dividing $p-1$ would be great. References to existing conjectures, conditional results, and unconditional results would be greatly appreciated.
 A: I believe that sieve methods (in particular methods similar to Chen's result on "almost" Goldbach and twin primes) should give infinitely primes $p$ such $(p-1)/2$ is a product of two primes. That's more than what you asked. 
Wikipedia quotes a result of Bombieri-Friedlander-Iwaniec stating that Linnik's constant is $2$ for almost all moduli. If the same is true for infinitely many prime moduli $q$, then you are in business. A prime $p \equiv 1 \mod q, p \ll q^2$ is what you want.
Maybe an analytic number theorist will come along and give precise references.
Wikipedia - Sieve Methods
Wikipedia - Linnik's Theorem
A: Fouvry showed that the relative density is positive of primes $p$ for which the largest prime factor of $p+a$ is $\ge p^{\alpha}$ for $\alpha \approx .6687$.
Etienne Fouvry, Théorème de Brun-Titchmarsh: application au théorème de Fermat, Invent. Math 79 (1985), 383–407. MR0778134 (86g:11052)
A: John A. Gordon introduced the notion of strong primes (try Wikipedia) which, beside other requirements, are primes $p$ satisfying $p \equiv 1 \mod r$ for some large prime $r$ of about the same size as $p$. In the following paper, it has been shown how to construct strong primes of arbitrary bit size efficiently and with high probability:


*

*John A. Gordon: "Strong Primes Are Easy to Find", Proceedings of EUROCRYPT '84, LNCS 209, Springer, 1985.

A: See "On the number of primes $p$ for which $p+a$ has a large prime factor." (Goldfeld, Mathematika 16 1969 23--27.) Using Bombieri-Vinogradov he proves, for a fixed integer $a$, that
$$\sum_{p \leq x} \sum_{\substack{ x^{1/2}< q \leq x  \\ q | p+a}} \ln q = \frac{x}{2} + O\left(\frac{x \ln \ln x}{ \ln x} \right)$$
where the summation is over $p$ and $q$ prime. Note that this implies that the number of primes $p$ less than $x$ such that $p-1$ has a prime factor greater than $p^{1/2}$ is asymptotically at least $\frac{x}{2\ln x}$.
