MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
@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
up vote 8 down vote accepted

Yes. G. Harman has proven:

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

share|cite|improve this answer
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… (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
@Ricky, I agree with Greg that this likely can be extended to the arithmetic progression 2 mod 3 without too much difficulty. The reason that constants become ineffective in this area is because one needs to account for hypothetical Siegel zeros. Once we know that there are no Siegel zeros for L functions of a given modulus, then all of the constants in the prime number theorem and its error term (see, for instance CH 20 of Davenport's Multiplicative Number theory) for that modulus become effectively computable. We know there are no Siegel zeroes mod 3. – Mark Lewko May 14 '13 at 8:19

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.