Let $m$ be a fixed integer. I want to count number of prime triplet $(p,q,r)$ such that $p < q < r < 2p$ with $m$ divides $p-1, q-1$ but not $r-1$ and the product $pqr$ is an $l$ digit integer.
4
-
$\begingroup$ Is $l$ also fixed? $\endgroup$– Qiaochu YuanCommented Dec 29, 2011 at 8:07
-
$\begingroup$ Yes $l$ is fixed. $\endgroup$– user15864Commented Dec 29, 2011 at 8:09
-
$\begingroup$ It would be nice to get some motivation for doing this. Also, you are unlikely to get an exact count for l larger than , say, 30. If you want a rough estimate, the count should have close to l - 3n digits, where n is the number of digits of m. Gerhard "Ask Me About System Design" Paseman, 2011.12.29 $\endgroup$– Gerhard PasemanCommented Dec 29, 2011 at 8:38
-
$\begingroup$ These kinds of integers are used many times for multi prime RSA case. $\endgroup$– user15864Commented Dec 29, 2011 at 9:43
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
Under your assumptions $p,q,r$ are all about size $x= 10^{l/3}$. The congruence conditions are basically independent so you'd get about $(x/\log x)^3(\phi(m)-1)/\phi(m)^3$. There may be a constant in front to account for the inequalities among the primes and the fact that you want exactly $l$ digits. This should be OK when $l$ is large compared to $m$. If that's not the case, it might be trickier.
answered Dec 29, 2011 at 9:26