4
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ @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?". $\endgroup$
    – Mark Lewko
    Commented May 13, 2013 at 23:44
  • $\begingroup$ What the best result with distribution 1? $\endgroup$
    – user49362
    Commented Apr 8, 2014 at 21:16

1 Answer 1

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Greg Martin
    Commented May 14, 2013 at 6:34
  • $\begingroup$ 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. $\:$ $\endgroup$
    – user5810
    Commented May 14, 2013 at 7:47
  • $\begingroup$ @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. $\endgroup$
    – Mark Lewko
    Commented May 14, 2013 at 8:19

You must log in to answer this question.